快速排序不适用于大于 100 的数组

Question

我一直在尝试实现一种普通的非混合快速排序算法，它适用于大小不超过 100 个字段的数组。我得到例外"堆栈溢出"，你们大多数人可能都很熟悉。这是我的源代码：

import java.util.Arrays;
public class Quicksort {
    public int[] zahlenliste;
    public Quicksort(int[] zahlenliste) {
        sort(zahlenliste);
    }
    public void sort(int[] zahlenliste) {
        if (zahlenliste == null || zahlenliste.length == 0) {
            return;
        }
        this.zahlenliste = zahlenliste;
        quickSort(0, zahlenliste.length - 1);
    }
    public void quickSort(int begin, int end) {
        if (begin >= end) {
            return;
        }
        int lower = begin;
        int higher = end;
        // Choose a pivot
        // int pivot = zahlenliste[lower + (higher - lower) / 2];
        int pivot = zahlenliste[lower + (higher - lower) / 2];
        while (lower <= higher) {
            while (zahlenliste[lower] < pivot) {
                lower++;
            }
            while (zahlenliste[higher] > pivot) {
                higher--;
            }
            if (lower < higher) {
                swap(zahlenliste, lower, higher);
            }
            lower++;
            higher--;
        }
        if (begin < higher) {
            quickSort(begin, lower);
        }
        if (lower < end) {
            quickSort(lower, end);
        }
    }
    public static int[] swap(int[] zahlenliste, int begin, int end) {
        int temp = zahlenliste[begin];
        zahlenliste[begin] = zahlenliste[end];
        zahlenliste[end] = temp;
        return zahlenliste;
    }
}

我知道有一些快速排序实现，您可以通过中位数三方法选择更合适的枢轴，或者使用小于 10 的列表的插入排序。但是，我想实现所有这些并在巨大的数组上比较它们。因此，如果有人有一个解决方案来获得简单的快速排序来对更大的数组进行排序，那就太好了。

Answer 1

注释中注明的修复

    public void quickSort(int begin, int end) {
        if (begin >= end) {
            return;
        }
        int lower = begin;
        int higher = end;
        int pivot = zahlenliste[lower + (higher - lower) / 2];
        while (lower <= higher) {
            while (zahlenliste[lower] < pivot) {
                lower++;
            }
            while (zahlenliste[higher] > pivot) {
                higher--;
            }
            if (lower <= higher) {                  // fix
                swap(zahlenliste, lower, higher);
                lower++;                            // fix
                higher--;                           // fix
            }
        }
        if (begin < lower-1) {                      // fix
            quickSort(begin, lower-1);              // fix
        }
        if (lower < end) {
            quickSort(lower, end);
        }
    }
    // fix (void)
    public void swap(int[] zahlenliste, int begin, int end) {
        int temp = zahlenliste[begin];
        zahlenliste[begin] = zahlenliste[end];
        zahlenliste[end] = temp;
    }

---

基于常规Hoare分区的快速排序示例。它还仅在较小(或大小相等(的分区上使用递归，然后迭代回较大(或大小相等(分区的循环顶部：

    public static void qsort(long[] a, int lo, int hi)
    {
        while(lo < hi){
            int  md = lo+(hi-lo)/2;
            int  ll = lo-1;
            int  hh = hi+1;
            long p = a[md];
            long 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++;
            // only use recursion on smaller partition,
            // then loop back for larger partition
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }