为什么此算法不能正确排序最后一个索引?

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]，内部循环最大值 =0，最小值 = 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;
}

Answer 2

在外循环的每次迭代中，从第一个索引 (i( 作为初始最小索引开始，最后一个索引 (a.length-1-i( 作为初始最大索引。然后，将这两个索引与范围 i+1 到 a.length-i-1 中的所有索引进行比较。但是，如果第一个索引 (i( 实际上包含最大值，则永远不会将其与 a[max] 进行比较，因此 a[max] 永远不会在内部循环的末尾包含正确的值。

下面是一个建议的修复方法：

public static void dualSelectionSort(int[]a) {
for(int i = 0; i < a.length - i - 1; i++) {
if (a[i] > a[(a.length - 1) - i]) {
int temp = a[i];
a[i] = a[(a.length - 1) - i];
a[(a.length - 1) - i] = temp;
}
int min = i;
int max = (a.length - 1) - i;
for (int j = i + 1; j < (a.length -1 ) - 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;
}
}

我改变的三件事：

1. 外部循环的结束时间可能比你结束它快得多——一旦i >= a.length-i-1——因为在每次迭代中，你都会找到最小值和最大值，所以你把剩余的未排序数组减少了 2。

2. 初始化min和max索引时，请确保min索引实际上包含小于max索引的值。如果a[i] > a[(a.length-1)-i]，请在将min设置为i并将max设置为(a.length-1)-i之前交换它们。

3. 内部循环应从i+1迭代j到(a.length-1)-i-1。