java - 选择排序变体不起作用

Question

我必须根据这些参数在 Java 中实现选择排序:

Implement a variation to the SelectionSort that locates both the smallest and largest elements while scanning the list and positions them at the beginning and the end of the list, respectively. On pass number one, elements x0,...,xn-1 are scanned; on pass number two, elements x1,...,xn-2 are scanned; and so on.

我向该方法传递了一个大小为 32 的数组，当我打印该数组时，它没有排序。我的代码出了什么问题？

static void selectionSort() {
    scramble();
    int smallIndex = 0;  //index of smallest to test
    int largeIndex = array.length - 1;  //index of largest to test
    int small = 0;  //smallest
    int large;  //largest
    int smallLimit = 0;  //starts from here
    int largeLimit = array.length - 1;  //ends here
    int store;  //temp stored here
    int store2;

    for(int i = 0; i < array.length/2; i++) {  //TODO not working...
        small = array[smallLimit];
        large = array[largeLimit];
        for(int j = smallLimit; j <= largeLimit; j++) {
            if(array[j] < small) {
                smallIndex = j;
                small = array[j];
            }
            else if(array[j] > large) {
                largeIndex = j;
                large = array[j];
            }
        }
        store = array[smallLimit];
        store2 = array[smallIndex];
        array[smallLimit] = store2;
        array[smallIndex] = store;
        store = array[largeLimit];
        array[largeLimit] = array[largeIndex];
        array[largeIndex] = store;
        smallLimit++;
        largeLimit--;
    }
    print();    
}

Answer 1

考虑极端情况:当在 smallLimit 或 largeLimit 处找到最大或最小项时会发生什么。当这种情况发生时，你会遇到两个问题:

1. largeIndex 和 smallIndex 未设置。它们保留上一次迭代的值。
2. 将最小的项目交换到正确的位置会移动最大的项目。第二次交换将最小的项目移动到最大的项目所在的位置，而最大的项目最终出现在随机位置。如果您发现很难可视化，请单步执行纸上或调试器中的代码。

这些问题很容易解决。您可以遵循一些准则来避免该问题:

• 使用更少的移动部件。您始终可以使用 smallIndex 获取 small 的值，如果您只使用 smallIndex，就不会有不同变量失步的危险。
• 在尽可能小的范围内声明变量。如果 smallIndex 是在循环体中声明的，而不是在外部声明的，编译器会告诉您它可能在交换之前没有设置。
• 像这里的第一次交换这样的破坏性更新总是会让之前的计算变得过时。当您无法避免这种情况发生时，请寻找两个更新可以互相干扰的方法。