作者tkcn (小安)
看板java
标题Re: [J2SE] 测试quickSort
时间Sun Mar 11 13:07:26 2012
※ 引述《sing10407 (阿U)》之铭言：
: public static void quickSort(int[] data,int l,int r){
: int i, j, tmp, v;
: if (r > l) {
: v = data[l];//l=left,r=right,v=标竿
: i = l;//i和j则是移动与交换的点
: j = r + 1;
因为是已经排序好的阵列，
而你又都是拿最左边(最小)的 data[l] 当作 pivot，
也就是说每次将阵列切成两半时，其中一半都没有元素。
这个例子正巧是这种 Quicksort 实作的 worst case，
有多少元素就要递回几层，然後 method stack 就爆掉了。
解法有二:
1. 增加 stack size，好像前面几篇正好讨论过。
2. 更换 Quicksort 选取 pivot 的方式，
有些版本会用随机取 pivot，有的会用第 (l+r)/2 个元素当作 pivot，
这些都能解决你的问题。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.231
1F：推 sing10407:感谢神人解决问题!!!! 03/11 14:03