时间戳

首页 > 解决方案 > 快速排序不排序输入 [-1, 2, -8, -10]

java - 快速排序不排序输入 [-1, 2, -8, -10]

问题描述

这是代码：

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. Sort an Array）：https ://leetcode.com/problems/sort-an-array/

枢轴始终在界限内，我也看不出其余代码有任何问题。

代码有什么问题吗？

标签： javainputquicksort

解决方案

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

 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.

推荐阅读