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

Question

我一直在尝试实现一个普通的非混合快速排序算法，它适用于大小不超过 100 个字段的数组。我得到的异常 "stack-overflow" 大多数人可能都很熟悉。这是我的源代码：

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

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

Quicksort does not work with array bigger than 100

java

stack-overflow

quicksort