java - 快速排序不适用于大于 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;
    }

<小时/>

基于传统霍尔分区的快速排序的示例。它还仅在较小(或相等大小)的分区上使用递归，然后迭代回到较大(或相等大小)分区的循环顶部:

    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;
            }
        }
    }