为什么这个算法不能正确排序最后一个索引?
Why does this algorithm not sort the last index correctly?
我应该编写一个版本的选择排序算法,将最小的数字移到数组的前面,同时将最大的数字移到数组的末尾。我知道它基本上是从两端工作的,所以有两个排序的子数组,但是我的代码似乎放错了数组中的最后一个数字。我的代码:
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]。
我错过了什么?
在外循环的每次迭代中,您以第一个索引 (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;
}
}
我改变的三件事:
外层循环结束的时间可能比你结束的时间早得多——一次i >= a.length-i-1
——因为在每次迭代中你都会找到最小值和最大值,所以你将剩余的未排序数组减少了 2 .
初始化min
和max
索引时,确保min
索引实际包含的值小于max
索引。如果 a[i] > a[(a.length-1)-i]
,请在将 min
设置为 i
并将 max
设置为 (a.length-1)-i
之前交换它们。
内部循环应该从 i+1
迭代 j
到 (a.length-1)-i-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.Existing 交换将使它成为 [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;
}
我应该编写一个版本的选择排序算法,将最小的数字移到数组的前面,同时将最大的数字移到数组的末尾。我知道它基本上是从两端工作的,所以有两个排序的子数组,但是我的代码似乎放错了数组中的最后一个数字。我的代码:
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]。 我错过了什么?
在外循环的每次迭代中,您以第一个索引 (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;
}
}
我改变的三件事:
外层循环结束的时间可能比你结束的时间早得多——一次
i >= a.length-i-1
——因为在每次迭代中你都会找到最小值和最大值,所以你将剩余的未排序数组减少了 2 .初始化
min
和max
索引时,确保min
索引实际包含的值小于max
索引。如果a[i] > a[(a.length-1)-i]
,请在将min
设置为i
并将max
设置为(a.length-1)-i
之前交换它们。内部循环应该从
i+1
迭代j
到(a.length-1)-i-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.Existing 交换将使它成为 [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;
}