我写了一封信 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;
}
3条答案
按热度按时间dz6r00yl1#
我对你的算法做了一些分析(和我的一样),它们都表现出相同的行为。我写了自己的数据生成器,一切正常。这意味着较低数组的数据分布不适合所选数据透视。
所以我放了一些计数器来计算递归过程中达到的最大深度。对于1\u 000\u 000值数组,深度处于低100(低于1000)。对于100000范围值,深度接近15000,并导致堆栈溢出。这样做的原因是不同大小数组的数据分布。
我一直使用的算法是这里推荐使用最左边的值作为轴心的算法。
这段摘自维基百科的内容谈到了轴心点的选择。
枢轴的选择
在quicksort的早期版本中,分区最左边的元素通常被选为pivot元素。不幸的是,这会导致已经排序的数组出现最坏情况,这是一个相当常见的用例。选择一个随机索引作为轴心,选择分区的中间索引,或者(特别是对于较长的分区)选择第一个索引的中位数,这个问题很容易解决,轴心分区的中间和最后一个元素(由sedgewick推荐)。[18]这个“三个中位数”规则针对排序(或反向排序)输入的情况,在不知道输入顺序信息的情况下,给出比选择任何单个元素更好的最佳轴心(真实中位数)估计。
通过将轴更改为
arr[(p + r)/2]
一切都很顺利。这也是安德烈亚斯在这里回答的最后建议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):同样,如果对数据进行反向排序,例如,我们对数组进行排序
{9,8,7,6,5,4,3,2,1,0}
,我们还得到一个非常深的调用堆栈(maxcalldepth=9):相比之下,如果我们将pivot更改为范围的中间值,则max call stack depth(即max indentation)将大大减少(maxcalldepth=3,在这两种情况下):
结论:更改代码以使用:
g6ll5ycj3#
我也可以复制它。当然,你有一个
StackOverflowError
因为次数太多了quickSort(...);
以递归方式调用,这与数组中的元素数不直接相关。不过,数组越大,这种方法的可能性就越大quickSort(...);
更频繁地得到呼叫。但是,在数组中如何分布元素方面还有更多的工作要做。例如:
将产生
java.lang.StackOverflowError
鉴于不会的,即使是一系列的
new int [1000000];
.