快速排序方法会给我一个堆叠错误吗

Question

我有一个快速排序方法，它按升序对元素进行排序，但似乎总是出现stackoverlower错误。

出于某种原因，当逻辑对我来说有意义时，它会在while循环中显示错误。这是快速排序类的代码：

public T[] sort(T[] arr, int left, int right)
{
int l = left;
int r = right;
if (right <= left)
return null;
//Find the pivot in the middle
T pivot = arr[(left + (right - left)) / 2];
T temp;

while (l <= r)
{
// check values on left are bigger than the pivot
while (arr[l].compareTo(pivot) < 0)
{
l++;
}
// check if values are smaller than the pivot
while (arr[r].compareTo(pivot) > 0)
{
r--;
}
// l and r have gone past each other swap them
if (l <= r)
{
//swap process
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// left pointer goes up 1
// right pointer goes down 1
l++;
r--;
}
}
if (left < r)
sort(arr, left, r);
if (l < right)
sort(arr, l, right);
return arr;
}

错误似乎指向

//Find the pivot in the middle
T pivot = arr[(left + (right - left)) / 2];

然后我似乎遇到了很多错误。

Answer 1

我认为您计算Pivot不正确您应该使用T pivot=arr[left+(right-left(/2]；以下是使用中间元素作为轴心的快速排序程序：

public void quickSort(T arr[],int left, int right){
int low =left, high = right;
int pivot = arr[left + (right - left) / 2];
while(low<=high){
while (arr[low] < pivot) {
low++;
}
while (arr[high] > pivot) {
high--;
}
if (low <= high) {
int  temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
low++;
high--;
}
if (left < high) {
quickSort(arr,left, high);
}
if (low < high) {
quickSort(arr,low, right);
}
}
}

希望它能有所帮助！！

Answer 2

流API方式：

T[] result = Arrays.stream(a)
.skip(left)
.limit(right - left)
.sorted((o1, o2) -> {{you logic of comparing}})
.toArray(String[]::new);

得到的差异只是数组的一部分。因此，如果有必要，您应该在之后将它们连接起来。

Answer 3

这一行有一个拼写错误，是的。T pivot = arr[(left + (right - left)) / 2];
由于有多余的括号，所有内容都除以2。应该是

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

几句风格评论：

• 因为这是一个就地排序，所以返回T[]并不是真正必要的
• T temp可以移动到交换块中

把它放在一起：

import java.util.Arrays;
public class QuickSort<T extends Comparable<? super T>> {
public void sort (T[] arr)
{
if (arr == null || arr.length <= 1)
return;
sort(arr, 0, arr.length - 1);
}
public void sort(T[] arr, int left, int right)
{
int l = left;
int r = right;
if (right <= left)
return;
//Find the pivot in the middle
T pivot = arr[(left + (right - left)/2)];
while (l <= r)
{
// check values on left are bigger than the pivot
while (arr[l].compareTo(pivot) < 0)
{
l++;
}
// check if values are smaller than the pivot
while (arr[r].compareTo(pivot) > 0)
{
r--;
}
// l and r have gone past each other swap them
if (l <= r)
{
//swap process
T temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// left pointer goes up 1
// right pointer goes down 1
l++;
r--;
}
}
if (left < r)
sort(arr, left, r);
if (l < right)
sort(arr, l, right);
}
public static void main(String args[])
{
Integer[] numbers=new Integer[] {3,2,5,4,1};
System.out.println(Arrays.asList(numbers));
new QuickSort<Integer>().sort(numbers);
System.out.println(Arrays.asList(numbers));
}
}

输出：

[3, 2, 5, 4, 1]
[1, 2, 3, 4, 5]