快速排序不对长度为 2 的数组进行排序

Question

我正在尝试实现快速排序的一部分，我在其中调用了一个名为 splitPoint 的方法。 SplitPoint 将使用数组的第一个索引作为枢轴值，枢轴将移动到数组的中心。它将 return 枢轴新索引的索引。但是，如果我有一个长度为 2 的数组并且它是降序排列的，例如 [2, 1]，它无法排序。不过，该方法适用于其他一切。我认为如果这不起作用，我的快速排序作为一个整体将不起作用。

 public int splitPoint(int[] a, int first, int last){

    int splitPoint = a[first];
    int low = first + 1;
    int high = last - 1;

    int temp; //holds the temp val for swapping values

    while(low < high){
        while(a[low] <= splitPoint && low != last && high > low){    
            low++;  
            //System.out.println("While loop 1 tracer");
            }
        while(a[high] > splitPoint && high >= first && high >= low){
            high--;
            //System.out.println("While loop 2 tracer");
        }

        if(low <= high){
            temp = a[low];
            a[low] = a[high];
            a[high] = temp;
            low++;
            high++;
        }

        System.out.println(Arrays.toString(a)); // tracer

    }

    a[first] = a[high];
    a[high] = splitPoint;

    return high;
}

Answer 1

简单的答案是遍历您的代码。

假设您的电话是这样的：

splitPoint({2, 1}, 0, 1);

int splitPoint = a[first];  // Will hold a value of 2.
int low = first + 1;   //low = 0 + 1 = 1.
int high = last - 1;  // high = 1 - 1 = 0.

int temp; //holds the temp val for swapping values

while(low < high)  //<== here. low = 1.  high = 0.  low > high, test is false--loop is NOT performed.

a[first] = a[high];  // a[0] = a[0] = 2.
a[high] = splitPoint;  //a[0] = 2

return high;  //returns 0.

所以，简而言之，你的问题出在你对 low 和 high 的初始化上。

Answer 2

如果您检查，您会看到对于 [5, 0, 3] 这样的输入，它 returns [0, 5, 3]。所以即使是更大的阵列也有问题。

稍微修改过的代码应该可以正常工作：

static int split(int[] array, final int first, final int last) {
    int low = first;
    int high = last;

    int splitPoint = first;
    while (low < high) {
        while (array[high] > array[low] && high > low) {
            high--;
        }
        while (array[low] <= array[high] && high > low) {
            low++;
        }
        if (low < high) {
            int tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
            if (low == splitPoint) {
                low++;
                splitPoint = high;
            } else {
                high--;
                splitPoint = low;
            }
        }
    }
    return splitPoint;
}

示例：

public static void main(String[] args) {
    int[] array = new int[]{5, 0, 3};
    System.out.println(split(array, 0, array.length - 1));
    System.out.println(Arrays.toString(array));
}

输出：

2
[3, 0, 5]

快速排序不对长度为 2 的数组进行排序

Quicksort not sorting arrays with length 2

java

sorting

quicksort