下面的選擇排序代碼是否正確？

我正在學習關於數據結構的課程，並且教師給出了以下用於選擇排序的代碼。但我認爲這是不正確的，因爲在選擇排序中，我們掃描整個數組並在每次迭代中查找最小元素，用它的正確位置交換它。但是在下面的代碼中，我們每次都交換，我們發現一個比當前元素小的元素。所以請讓我知道這是否正確。下面的選擇排序代碼是否正確？

public static void selectionsort(int[] listtosort) 
{ 
    for (int i=0; i<listToSort.length; i++) 
    { 
     for (int j=i+1; j<listToSort.length; j++) 
     { 
      if (listToSort[i] > listToSort[j]) 
      { 
       swap(listToSort, i, j); 
       print(listToSort); 
      } 
     } 
    } 
}

來源

2016-06-22 Sai Sankalp

但我們一定會被其最壞的情況下測量算法的演出]吧？互換的數量將是O（N^2）在最壞的情況下scenario.Also它帶走的是選擇排序有較少數量的事實與插入排序進行比較時的交換。 –

我的意思是在我剛纔提到的代碼中，在最壞的情況下，交換次數是0（N^2）？ –

是的，他們不改變'大O'的表現但是，如果在內存寫入比讀取像比如說閃存更昂貴的交換數量變得重要的權利？ –

你說得對。每次遇到較小數字時，您可以存儲較小數字的索引，而在內部迭代結束時，您可以將當前數字與最小數字進行交換，而不是每次換一次。但是這種方法不影響這種算法的複雜性。兩者都是O（n^2）。如果一個數字較小交換它是O（1）。如果一個數字更小，保持其索引又是O（1）。

public static void SelectionSort (int [ ] num) { 
int i, j, first, temp; 
for (i = num.length - 1; i > 0; i - -) { 
    first = 0; //initialize to subscript of first element 
    for(j = 1; j <= i; j ++) { 
    if(num[ j ] < num[ first ])   
     first = j; 
    } 
    temp = num[ first ]; //swap smallest found with element in position i. 
    num[ first ] = num[ i ]; 
    num[ i ] = temp; 
}

來源

2016-06-22 12:11:32

是的，但是掉期的數量會增加。對於我所提到的代碼，在最壞的情況下交換的數量將是O（N^2）。因此，它取消了選擇排序的優點之一與其他排序算法相比，掉換次數是否更少？ –

選擇排序恰恰相反，最糟糕的情況實質上是最好的情況。看看[這個鏈接]（http://bigocheatsheet.com/），它顯示了不同的複雜性。只需谷歌「排序複雜性」和有用的信息即時彈出。 – mojo1mojo2

@SaiSankalp這是正確的，大部分時間內掉期數量都會增加。然而，這只是複雜性的不斷倍增。（交換成本與儲蓄指數成本） –

下面的選擇排序代碼是否正確？

回答

相關問題