代码如下:
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/
枢轴总是在边界内，我也看不出其他代码有什么问题。
代码有什么问题吗?
你的算法完全正确!你只需要替换这一行:
int pivot = (left + right) / 2;
:
int pivot = arr[(left + right) / 2];
，然后相应地更新比较:
- 用
arr[left] < pivot代替arr[left] < arr[pivot]， - 用
arr[right] > pivot代替arr[right] > arr[pivot]
你的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;
}