PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Fw: [問題] Quick Sort

看板Prob_Solve (計算數學 Problem Solving)作者Kenny444 (死後會復活的阿尼)時間6年前 (2018/11/12 16:55)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串1/1

最近整理資料,發現以前的問題好像比較適合在這問順便修改一下 ※ [本文轉錄自 java 看板 #1OMSNOdD ] 作者: Kenny444 (死後會復活的阿尼) 看板: java 標題: [問題] Quick Sort 時間: Wed Dec 21 07:59:03 2016 看了一些快速排序法的程式碼, 有一些疑問以這個程式碼為例 private static void sort(int[] number, int left, int right) { if(left < right) { int s = number[(left+right)/2]; int i = left - 1; int j = right + 1; while(true) { // 向右找 while(number[++i] < s) ; // 向左找 while(number[--j] > s) ; if(i >= j) break; swap(number, i, j); } sort(number, left, i-1); // 對左邊進行遞迴 sort(number, j+1, right); // 對右邊進行遞迴 } } 跳出 while 條件為 i >= j,而左數列的最後一個元素是 i-1 而不是 j+1 左邊遞迴的子數列和右邊遞迴的子數列會不會重疊 ? -------------------------------------------------------------------- 下面是另外一個 public void quicksort(int[] a, int left, int right) { int i, j, t, temp; if (left > right) return; temp = a[left]; // temp 中存的就是基準數 i = left; j = right; while (i != j) { // 順序很重要，要先從右邊開始找 while (a[j] >= temp && i < j) j--; // 再找左邊的 while (a[i] <= temp && i < j) i++; // 交換 if (i < j) { t = a[i]; a[i] = a[j]; a[j] = t; } } // 最終將基準數歸位 a[left] = a[i]; a[i] = temp; quicksort(a, left, i - 1); // 繼續處理左邊的，這裡是一個遞迴的過程 quicksort(a, i + 1, right); // 繼續處理右邊的，這裡是一個遞迴的過程 } 先從右邊找起或是從左邊找起感覺沒差,只要調整後面基準數和誰互換 ? 例如:最後面的將 a[i] 和 a[left] 交換在先 i++ 的情況下,應該改成 a[j] 和 a[left] 交換 ? ------------------------------------------------------------------------- public void quick_sort1(int[] s, int l, int r) { if (l < r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) i++; if(i < j) s[j--] = s[i]; } s[i] = x; // 遞迴調用 quick_sort1(s, l, i - 1); quick_sort1(s, i + 1, r); } } 在先執行 i++ 和 s[j--] 的情況下 s[i] = x 是不是也可以改成 s[j] = x ? -- ● ▆▆▆▆ ● 幹你媽的! ◢███◣ ████ ◢████◣ ◢███◣ 停撥黑棒! ▂▂▂▂▂ ◢████◣ ██████ █◤ ◥█ 還我南方! ⊙ ⊙ █ ⊙ ⊙ █ ⊙ ⊙ █ ⊙⊙ 炸你全家! ◥ 皿 ◢ ◥ 皿 ◤ 皿 ◥◣皿◢◢ ◢▇▇▇◣ ◢███◥ ◥ ︶ ◢ ◢ ◥ ψdiabloq13 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.95.52.50 ※ 文章網址: https://www.ptt.cc/bbs/java/M.1482278360.A.9CD.html ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: Kenny444 (47.148.248.45), 11/12/2018 16:55:56 ※ 編輯: Kenny444 (47.148.248.45), 11/12/2018 17:09:39