java - 选择排序从两端增长有序范围

Question

我写了一个选择排序的修改版本，其中我考虑了数组的最小值和最大值并将它们放在两端

算法是这样工作的

1. Find the minimum and the maximum value in the list.
2. Swap the minimum value with the value in the first position.
3. Swap the maximum value with the value in the last position.
4. Repeat the steps above for the remainder of the list 
(starting at the second position and ending at the second to 
 last position and narrowing the range of positions examined 
 from both ends of the array each time).

不幸的是，上面显示了具有重复值的数组的意外结果。

例如，

[9, 37, 12, 1, 13, 31, 5, 37, 36, 29, 19, 22, 20, 15, -1, 23]

被排序为

[-1, 1, 5, 9, 12, 13, 15, 19, 20, 22, 23, 29, 31, 37, 36, 37]

事实上，这里的主要问题是算法通常没有对数组后半部分的元素进行适当的排序，除了简单的重复项。

这是我的伪代码

    int i=0;
    while(i<=(arr.length-i-1)) {
      int minIndex = i;
      int maxIndex=arr.length-i-1; 
      for (int j = i+1; j <=arr.length-i-1; j++) {

       if (arr[j] <=arr[minIndex]) {
         minIndex = j;      
         } 
       if(arr[j]>=arr[maxIndex]){
          maxIndex = j; 
         }
      }
      swap(arr, i, minIndex);
      swap(arr, (arr.length-i-1), maxIndex); 
    i++;
    }

编辑 这是我代码的交换部分，它是唯一与算法交互的部分。我不认为它会产生任何区别，但无论如何我都会包括它

 private static void swap(int[] arr, int oldIndex, int newIndex){

    int temp=arr[oldIndex];
    arr[oldIndex]=arr[newIndex];
    arr[newIndex]=temp;
 }

Answer 1

问题发生在 i 时恰好是 maxIndex .要解决该问题，您需要添加:

swap(arr, i, minIndex);
if(i == maxIndex) {
     maxIndex = minIndex;
}
swap(arr, (arr.length-i-1), maxIndex);

See it @work