快速排序失败,项目较少,在降序良好排序的数组中处理更多项目

s5a0g9ez  于 2021-07-06  发布在  Java
关注(0)|答案(3)|浏览(382)

我写了一封信 quickSort 方法,我使用该方法尝试对已接近排序的数组进行排序-反向排序。因此,快速排序尝试按升序排序,而数组几乎已按降序排序:

private static void switchPlaces(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void quickSort(int[] a, int low, int high)  {
        int i = low;
        int j = high;
        int pivot = a[low];

        while (i <= j) {

            while (a[i] < pivot) {
                i++;
            }
            while (a[j] > pivot) {
                j--;
            }

            if (i <= j) {
                switchPlaces(a, i, j);
                i++;
                j--;
            }
        }

        if (low < j) {
            quickSort(a, low, j);
        }
        if (i < high) {
            quickSort(a, i, high);
        }
    }

我使用我的自定义方法生成这样一个数组-20%的元素比它们以前的元素大。
但是当我打开qucksort时 100,000 长数组i get stackoverflow错误:

int[] a = generateArray(100_000);

quickSort(a, 0 , a.length - 1); //stackoverflow

不会发生的事情 1,000,000 长数组:

int[] a = generateArray(1_000_000);

quickSort(a, 0 , a.length - 1); //quickly works: all elements inside a are sorted


之后 1_000_000 排序:
a 一开始 100_000 排序:
a 一开始 1_000_000 排序:

我不明白为什么它适用于较大的数组,但不适用于较小的数组。
编辑:

public static void main(String[] args) {
        int[] a = generateArray(1_000_000);
        quickSort(a, 0 , a.length - 1);
        System.out.println();
    }

    public static int[] generateArray(int N) {
        Random random = new Random();
        int max = 1_000_000;
        int[] result = new int[N];

        int prev =  max - random.nextInt(100);
        result[0] = prev;
        for (int i = 1; i < N; i++) {
            boolean toSort = random.nextInt(10) < 8;

            int number;
            if (toSort) {
                number = Math.max(0, prev - random(5, 10));
                prev = number;
            } else {
                number = prev + random(5, 10);
            }

            result[i] = number;
        }

        return result;
    }
dz6r00yl

dz6r00yl1#

我对你的算法做了一些分析(和我的一样),它们都表现出相同的行为。我写了自己的数据生成器,一切正常。这意味着较低数组的数据分布不适合所选数据透视。
所以我放了一些计数器来计算递归过程中达到的最大深度。对于1\u 000\u 000值数组,深度处于低100(低于1000)。对于100000范围值,深度接近15000,并导致堆栈溢出。这样做的原因是不同大小数组的数据分布。
我一直使用的算法是这里推荐使用最左边的值作为轴心的算法。

这段摘自维基百科的内容谈到了轴心点的选择。
枢轴的选择
在quicksort的早期版本中,分区最左边的元素通常被选为pivot元素。不幸的是,这会导致已经排序的数组出现最坏情况,这是一个相当常见的用例。选择一个随机索引作为轴心,选择分区的中间索引,或者(特别是对于较长的分区)选择第一个索引的中位数,这个问题很容易解决,轴心分区的中间和最后一个元素(由sedgewick推荐)。[18]这个“三个中位数”规则针对排序(或反向排序)输入的情况,在不知道输入顺序信息的情况下,给出比选择任何单个元素更好的最佳轴心(真实中位数)估计。
通过将轴更改为 arr[(p + r)/2] 一切都很顺利。这也是安德烈亚斯在这里回答的最后建议

kqhtkvqz

kqhtkvqz2#

不要使用范围中的第一个值作为轴心,请使用中间值。
如果数据已经完全排序,结果是 quickSort(a, start, end) 递归调用 quickSort(a, start + 1, end) ,因此得到的递归调用堆栈深度等于数组大小,这肯定会导致 StackOverflowError 在更大的数据集上。
为了举例说明,我们可以添加 print 要显示的语句 start 以及 end 调用方法时。为了提供更多帮助,我们可以使用缩进让print语句显示调用深度。如果我们这样做,例如排序数组 {0,1,2,3,4,5,6,7,8,9} ,我们得到(maxcalldepth=9):

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
0, 9
 1, 9
  2, 9
   3, 9
    4, 9
     5, 9
      6, 9
       7, 9
        8, 9

同样,如果对数据进行反向排序,例如,我们对数组进行排序 {9,8,7,6,5,4,3,2,1,0} ,我们还得到一个非常深的调用堆栈(maxcalldepth=9):

{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
0, 9
 0, 8
  1, 8
   1, 7
    2, 7
     2, 6
      3, 6
       3, 5
        4, 5

相比之下,如果我们将pivot更改为范围的中间值,则max call stack depth(即max indentation)将大大减少(maxcalldepth=3,在这两种情况下):

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
0, 9
 0, 3
  2, 3
 5, 9
  5, 6
  8, 9
{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
0, 9
 0, 4
  0, 1
  3, 4
 5, 9
  5, 6
  8, 9

结论:更改代码以使用:

int pivot = a[(start + end) / 2];
g6ll5ycj

g6ll5ycj3#

我也可以复制它。当然,你有一个 StackOverflowError 因为次数太多了 quickSort(...); 以递归方式调用,这与数组中的元素数不直接相关。不过,数组越大,这种方法的可能性就越大 quickSort(...); 更频繁地得到呼叫。但是,在数组中如何分布元素方面还有更多的工作要做。
例如:

int[] a = new int [100_000];
    for(int i = 0; i < a.length; i++)
        a[i] = i;

    quickSort(a, 0 , a.length - 1); //stackoverflow

将产生 java.lang.StackOverflowError 鉴于

int[] a = new int [100_000];
for(int i = 0; i < a.length; i+=2) {
    a[i] = i;
    a[i + 1] = 0;
}

quickSort(a, 0 , a.length - 1);

不会的,即使是一系列的 new int [1000000]; .

相关问题