java - 为什么这个算法不能正确排序最后一个索引？

Question

我应该编写一个版本的选择排序算法，将最小的数字移动到数组的前面，同时将最大的数字移动到数组的末尾。我知道它基本上是从两端工作的，所以有两个排序的子数组，但是我的代码似乎放错了数组中的最后一个数字。我的代码:

public static void dualSelectionSort(int[]a) {
    for(int i=0; i<a.length-1;i++) {
        int min=i;
        int max=(a.length-1)-i;
        for (int j=i+1;j<a.length-i;j++) {
            if(a[j]<a[min]) {
                min=j;
            }
            if(a[j]>a[max]) {
                max=j;
            }
        }
        int temp1=a[min];
        int temp2=a[max];
        a[min]=a[i];
        a[max]=a[(a.length-1)-i];
        a[i]=temp1;
        a[(a.length-1)-i]=temp2;
    }
}

如果给定输入 [5,4,3,2,1]，则输出 [1,2,5,3,4] 而不是 [1,2,3,4,5]。我缺少什么？

Answer 1

问题出在内部循环。

从 i+1 开始。所以比较max的代码实际上就是比较a[1]和a[4]。

你可以将其更改为 for (int j=i;j<a.length-i;j++)

此外，正如您在评论中看到的那样，在某些情况下，经过上述更改，代码仍然无法工作。会发生这种情况是因为 i == max因此现有的交换方法将行不通。例如:假设数组=[6,4,5]，内循环max=0，min=1。现有的交换将使其成为[4,6,6]。因此，交换应该以不同的方式处理。

      if(i==max) {
            swap(a,max,a.length-1-i);
            swap(a,min,i);
        }else {
            swap(a,min,i);
            swap(a,max,(a.length-1)-i);
        }  

完整代码如下:

public static void dualSelectionSort(int[]a) {
    for(int i=0; i<a.length-1;i++) {
        int min=i;
        int max=(a.length-1)-i;

        for (int j=i;j<a.length-i;j++) {
            if(a[j]<a[min]) {
                min=j;
            }
            if(a[j]>a[max]) {
                max=j;
            }
        }
        if(i==max) {
            swap(a,max,a.length-1-i);
            swap(a,min,i);
        }else {
            swap(a,min,i);
            swap(a,max,(a.length-1)-i);
        }       
    }
}

public static void swap(int[] a,int i,int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}