推 sing10407:感謝神人解決問題!!!! 03/11 14:03
※ 引述《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