快速排序未对输入进行排序 [-1, 2, -8, -10]

Question

这是代码：

public int[] sortArray(int[] arr) {
    // sort array using quicksort
    sort(arr, 0, arr.length - 1);
    return arr;
}

private void sort(int[] arr, int low, int high) {
    int pi = partition(arr, low, high);

    if (low < pi - 1) { // sort left half
        sort(arr, low, pi - 1);
    }
    if (pi < high) { // sort right half
        sort(arr, pi, high);
    }
}

// partitiion an array by selecting a pivot 
private int partition(int[] arr, int left, int right) {
    // get random index as the pivot
    int pivot = (left + right) / 2;

    while (left <= right) {
        while (arr[left] < arr[pivot]) {
            left++; // increment left index if left index is less than the pivot 
        }
        while (arr[right] > arr[pivot]) {
            right--; // decrement right index if right index is greater than the pivot 
        }
        if (left <= right) {
            swap(arr, left, right); // elements into using pivot 
            left++;
            right--;
        }
    }

    return left;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

由于某种原因，此快速排序代码不会对数组进行排序。

给定输入：

[-1, 2, -8, -10]

，输出如下：

[-10, -1, -8, 2]

。

这里是 Leetcode 上问题的链接（912.对数组进行排序）：https://leetcode.com/problems/sort-an-array/

枢轴始终在范围内，我也看不出代码的其余部分有任何问题。

代码有问题吗？

Answer 1

你的算法完全正确！你只需更换这一行：

 int pivot = (left + right) / 2;

与：

int pivot = arr[(left + right) / 2];

然后相应地更新您的比较：

• 将

  arr[left] < arr[pivot]

  替换为

  arr[left] < pivot

  ,
• 将

  arr[right] > arr[pivot]

  替换为

  arr[right] > pivot

  。

Answer 2

你

partition

方法可能应该是这样的（必须承认我已经很长一段时间没有写快速排序了）

 // partitiion an array by selecting a pivot
private static int partition(int[] arr, int left, int right) {
    // get random index as the pivot
    int pivot = (left + right) / 2;
    while (left <= right) {
        while (arr[left] < arr[pivot]) {
            left++; // increment left index if left index is less than the pivot
        }
        while (arr[right] > arr[pivot]) {
            right--; // decrement right index if right index is greater than the pivot
        }
        if (left < right) {
            swap(arr, left, right); // elements into using pivot
        }
        left++;
        right--;
    }
    return left;
}