如何修复 n 值较大的快速排序算法？（当数组不是随机的）

Question

我的快速排序算法对于较大的 n 值失败，并且仅当数组不是随机的。我尝试过在各种数组上使用该算法。当我使用随机数字数组（对于n的任何值）时，它可以正常工作，但是对于包含相同值或按升序或降序排列的值的数组，它失败了。这也只有在n大约是abov 6000时。（当n为<5000时，它可以完美地工作）我已经尝试过使用不同版本的快速排序。一个使用while循环而不是递归，并且它工作得很好。就像我说过的，只有当n对于非随机化数组大于6000时，我的算法才会失败，对于5000或更低，它的效果很好。void quicksort(int a[], int low, int high) {        if (low < high) {            int index = partition(a, low, high); // error             quicksort(a, low, index - 1);  // error            quicksort(a, index + 1, high);        }    }int partition(int arr[], int low, int high) {        int pivot = arr[high];        int i = low - 1;        //int j = low;        for (int j = low; j < high; j++) {            // If current element is smaller than or             // equal to pivot             if (arr[j] <= pivot) {                i++;                // swap arr[i] and arr[j]                 int temp = arr[i];                arr[i] = arr[j];                arr[j] = temp;            }        }        int temp = arr[i + 1];        arr[i + 1] = arr[high];        arr[high] = temp;        return (i + 1);    }上面我有我的快速排序算法。对于 n>6000（以及数组不是随机的）而失败的那个。下面是适用于 n 的所有值和任何类型的数组的代码。     public void quicksort(int[] data, int low, int high)   {  // 1 or 0 items are sorted by default      if(high - low < 1)         return;      int left = low;      int right = high;      int pivot = data[low + (high - low) / 2];        while(left <= right)      {  // Increment left pointer until left >= pivot         while(data[left] < pivot)            left++;         // Increment right pointer until right <= pivot         while(data[right] > pivot)            right--;         // If left < right; swap values         if(left <= right)         {  int temp = data[left];            data[left] = data[right];            data[right] = temp;            left++;            right--;         }      }      // quick_sort 'lesser values'      quicksort(data, low, right);      // quick_sort 'greater values'      quicksort(data, left, high);   }终端专门在两行中显示错误。（我在第一个快速排序方法中标记为错误的行）。

Answer 1

如果数据已经按顺序排列，则使用 arr[high]（或 arr[low]）会导致最坏情况下的堆栈空间开销为 O（n），这会溢出堆栈。第二个示例使用中间元素 （arr[low +（高-低）/2]），它将为已排序的数据或已反向排序的数据提供最佳大小写堆栈空间开销。

将堆栈空间开销限制为O（log（n））的解决方法是在进行分区后，检查哪个部分更小，并且只在较小的部分上使用递归，然后循环回去处理较大的部分（根据需要更新低或高以排除现在排序的较小部分，然后再循环回去）。

public static void quicksort(int[] arr, int low, int high)

{

    while (low < high) {

        int index = partition(arr, low, high);

        if((index-low) <= (high-index)){       // avoid stack overflow

            quicksort(arr, low, index - 1);    //

            low = index+1;                     //

        }else{                                 //

            quicksort(arr, index + 1, high);   //

            high = index-1;                    //

        }                                      //

    }

}

public static int partition(int[] arr, int low, int high)

{

    int pivot = arr[high];

    int i = low - 1;

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {

            i++;

            int tmp = arr[i];

            arr[i] = arr[j];

            arr[j] = tmp;

        }

    }

    int tmp = arr[i + 1];

    arr[i + 1] = arr[high];

    arr[high] = tmp;

    return (i + 1);

}

如果有兴趣，Hoare分区方案更快：

public static void qsort(int[] a, int lo, int hi)

{

    while(lo < hi){

        int md = lo+(hi-lo)/2;

        int ll = lo-1;

        int hh = hi+1;

        int p = a[md];

        int t;

        while(true){

            while(a[++ll] < p);

            while(a[--hh] > p);

            if(ll >= hh)

                break;

            t     = a[ll];

            a[ll] = a[hh];

            a[hh] = t;

        }

        ll = hh++;

        if((ll - lo) <= (hi - hh)){

            qsort(a, lo, ll);

            lo = hh;

        } else {

            qsort(a, hh, hi);

            hi = ll;

        }

    }

}