我编写了选择排序的修改版本,其中我考虑数组的最小值和最大值并将它们放在两端
该算法的工作原理如下
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++;
}
EDIT这是我的代码的交换部分,它是唯一与算法交互的部分。我认为这不会有任何区别,但无论如何我都会将其包括在内
private static void swap(int[] arr, int oldIndex, int newIndex){
int temp=arr[oldIndex];
arr[oldIndex]=arr[newIndex];
arr[newIndex]=temp;
}