下面的选择排序代码是否正确？

我正在学习关于数据结构的课程，并且教师给出了以下用于选择排序的代码。但我认为这是不正确的，因为在选择排序中，我们扫描整个数组并在每次迭代中查找最小元素，用它的正确位置交换它。但是在下面的代码中，我们每次都交换，我们发现一个比当前元素小的元素。所以请让我知道这是否正确。下面的选择排序代码是否正确？

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这是正确的，大部分时间内掉期数量都会增加。然而，这只是复杂性的不断倍增。（交换成本与储蓄指数成本） –

下面的选择排序代码是否正确？

回答

相关问题