選擇排序實現，我堅持計算交換次數的時間複雜度

Question

static int count = 0; 
for (int i = 0; i < arr.length; i++) { 
    for (int j = i + 1; j < arr.length; j++) { 
     if (arr[i] > arr[j]) { 
      swap(arr, i, j); 
      count++; 
     } 
    } 
} 

這是選擇排序的正確實現嗎？這個實現我沒有得到O（n-1）交換的複雜性。

Answer 1

這是選擇排序的正確實施嗎？

它在邏輯上取決於你在做什麼是正確的。它使用「查找數組中的最大/最小值」進行排序。但是，在選擇排序中，通常在一次迭代中不需要多次交換。掉期

你剛纔保存的最大/最小值數組中，然後在最後你的第i個元素

我沒有得到Ø掉它（N-1）的複雜性你的意思是n-1次交換？是的，這是因爲你每次交換都會發現一個更大的價值，而不僅僅是最大的價值。你可以嘗試重寫你這樣的代碼：

static int count=0; 
static int maximum=0; 
for(int i=0;i<arr.length-1;i++){ 
    maximum = i; 
    for(int j=i+1;j<arr.length;j++){ 
     if(arr[j] > arr[maximum]){ 
      maximum = j; 
     } 
    } 
    swap(arr[maximum],arr[i]); 
    count++; 
} 

另外，如果你想精確N-1次交換，你的迭代，我應該也發生了變化。