Quicksort算法（Cormen）提供Stackoverflow [英] Quicksort Algorithm (Cormen) gives Stackoverflow

问题描述

我实现了快速排序算法，该算法在算法简介（Cormen，第三版）7.1中给出了伪代码。

i implemented the Quick Sort Algorithm which given pseudo code in Introduction to Algorithms (Cormen, 3rd Edition) 7.1

当我尝试使用小尺寸数组的算法时，结果是真正。但是当我尝试使用N = 50000时，数组已经像这样排序了；
N = {1,2,3，...，50000};

When i tried algorithm with small sized arrays, result is true. But when i tried with N=50000 and array is already sorted like this; N = {1, 2, 3, ..., 50000};

它给出了StackOverflowError。我认为这是因为函数自身递归了50000次。
QuickSort（A，0，49999）=> QuickSort（A，0，49998）=> QuickSort（A，0，49997）...等等。

It gives StackOverflowError. I think it's happening because the function recurse itself 50000 times. QuickSort(A, 0, 49999) => QuickSort(A, 0, 49998) => QuickSort(A, 0, 49997)... so go on.

我可以解决这个问题吗？还是我应该使用不同的枢轴位置？

Can i solve this problem? Or should i use different pivot position?

这是我的代码；

public void sort(int[] arr){ QuickSort(arr, 0, arr.length - 1); }

private void QuickSort(int[] A, int left, int right){
    if(left < right){
        int index = Partition(A, left, right);
        QuickSort(A, left, index - 1);
        QuickSort(A, index + 1, right);
    }
}

private int Partition(int[] A, int left, int right){
    int pivot = A[right];
    int wall = left-1;
    for(int i=left; i<right; i++){
        if(A[i] <= pivot){
            Swap(A, ++wall, i);
        }
    }
    Swap(A, wall + 1, right);
    return wall + 1;
}

private void Swap(int[] A, int x, int y){
    int keeper = A[x];
    A[x] = A[y];
    A[y] = keeper;
}

推荐答案

是的，此关键方案是排序数组的不正确选择。正如您所注意到的，它会导致非常不平衡的分区，导致O（N ^ 2）复杂性和非常深的递归级别。

有一些方法可以改善此行为。
例如，您可以对数据透视使用随机索引，例如 pivotIdx = start + rand（）％（end-start + 1）; ，或选择-三种方法（索引范围内第一个，最后一个和中间元素的中位数）。

Yes, this pivot scheme is not right choice for sorted array. It causes very unbalanced partition, leads to O(N^2) complexity and very deep recursion level, as you noticed.
There are some approaches to improve this behavior. For example, you can use random index for pivot like pivotIdx = start + rand() % (end-start+1);, or choose median-of-three method (median of the first, last and middle elements in index range).

PS一种避免堆栈溢出的选项-首先调用递归较短的段，然后调用较长的段。

P.S. An option to avoid stack overflow - call recursion for shorter segment at first, then for longer one.

https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

这篇关于Quicksort算法（Cormen）提供Stackoverflow的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！