时间戳

首页 > 解决方案 > 为什么这个算法不能正确排序最后一个索引？

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

问题描述

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

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]。我错过了什么？

标签： javaarrayssortingselection-sort

解决方案

问题出在内部循环中。

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

你可以把它改成 for (int j=i;j<a.length-i;j++)

此外，正如您在评论中看到的那样，在进行上述更改后，代码仍然无法正常工作。这将发生，因为i == max现有的交换方法将不起作用。例如：假设数组 =[6,4,5]，内循环最大值 =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;
}

推荐阅读