快速排序能栈溢出吗
快速排序会栈溢出吗?
下面这段快速排序代码(java写的),在排序过程中会调用方法本身,如果这样的话,那数据量特别大的时候就需要很深层次的调用,那会发生栈溢出吗?
------解决方案--------------------
一般来说用Random来划分的话不会,此外还需要专门处理一下等于的情况,否则容易构造出让快排退化到n^2的数据。
------解决方案--------------------
《计算机程序设计的艺术》一书提到,如果采用随机分割值,对于随机生成的数据,
出现退化的概率低于 一千万分之一
(退化定义为程序的时间复杂度是超过 20*N*logN,这其实依然是一个可以接受的结果,不算灾难性后果。
不过另一方面
快速排序也有许多优化技巧的,并不仅仅是一个防止退化的问题
可以参看《程序员实用算法》一书,优化后大概可以比基本快速排序提速20%
------解决方案--------------------
看你数据规模,如果是海量数据就必须做处理。
------解决方案--------------------
最坏情况下空间复杂度是O(N)的,也就是递归的层数是O(N)的。
对于取确定元素作为pivot的qsort,都可以构造出这种数据。
就比如说你的qsort,只要一个递增的数列就够了。
所以qsort有时要随机化。。。
------解决方案--------------------
这个应该不是算法上面应该考虑的内容了。快排本身应该假设内存是无限的。
假如是海量数据,肯定不能用快排啊,用归并排序这类外排序吧。
貌似现在的操作系统会自动扩大栈空间的,应该不会溢出。
------解决方案--------------------
我昨天试了下快排,数据量大一点就OOM了
------解决方案--------------------
同意4楼,我们上算法课时,老师就直接给演示了一把,大概对几十万个数快排,最坏情况(每次都分成1个和x-1个)就会堆栈溢出。
当前的编译器一般堆栈大小都是固定的,即使调了编译选项或者系统选项,也终究是个固定值。不会动态增长的,否则就不叫堆栈,而是堆了。
------解决方案--------------------
系统的存储空间还是有限的,虚拟空间也还是有限,大数据量的处理,如果空间不够,想应该会产生溢出吧。
下面这段快速排序代码(java写的),在排序过程中会调用方法本身,如果这样的话,那数据量特别大的时候就需要很深层次的调用,那会发生栈溢出吗?
- Java code
private static class QuickSortor extends Sortor { protected <E> void sort(E[] a, boolean isAsc) { quickSort(a, 0, a.length - 1, isAsc); } private <E> void quickSort(E[] a, int left, int right, boolean isAsc) { if (left >= right) return; int middle = left; Comparable<E> cmp = (Comparable<E>) a[left]; for (int i = left + 1; i <= right; i++) { int result = cmp.compareTo(a[i]); if (!isAsc) result = -result; if (result >= 0) swap(a, ++middle, i); } swap(a, left, middle); quickSort(a, left, middle - 1, isAsc); quickSort(a, middle + 1, right, isAsc); } }
------解决方案--------------------
一般来说用Random来划分的话不会,此外还需要专门处理一下等于的情况,否则容易构造出让快排退化到n^2的数据。
------解决方案--------------------
《计算机程序设计的艺术》一书提到,如果采用随机分割值,对于随机生成的数据,
出现退化的概率低于 一千万分之一
(退化定义为程序的时间复杂度是超过 20*N*logN,这其实依然是一个可以接受的结果,不算灾难性后果。
不过另一方面
快速排序也有许多优化技巧的,并不仅仅是一个防止退化的问题
可以参看《程序员实用算法》一书,优化后大概可以比基本快速排序提速20%
------解决方案--------------------
看你数据规模,如果是海量数据就必须做处理。
------解决方案--------------------
最坏情况下空间复杂度是O(N)的,也就是递归的层数是O(N)的。
对于取确定元素作为pivot的qsort,都可以构造出这种数据。
就比如说你的qsort,只要一个递增的数列就够了。
所以qsort有时要随机化。。。
------解决方案--------------------
这个应该不是算法上面应该考虑的内容了。快排本身应该假设内存是无限的。
假如是海量数据,肯定不能用快排啊,用归并排序这类外排序吧。
貌似现在的操作系统会自动扩大栈空间的,应该不会溢出。
------解决方案--------------------
我昨天试了下快排,数据量大一点就OOM了
------解决方案--------------------
同意4楼,我们上算法课时,老师就直接给演示了一把,大概对几十万个数快排,最坏情况(每次都分成1个和x-1个)就会堆栈溢出。
当前的编译器一般堆栈大小都是固定的,即使调了编译选项或者系统选项,也终究是个固定值。不会动态增长的,否则就不叫堆栈,而是堆了。
------解决方案--------------------
系统的存储空间还是有限的,虚拟空间也还是有限,大数据量的处理,如果空间不够,想应该会产生溢出吧。