最近整理资料,发现以前的问题好像比较适合在这问 顺便修改一下 ※ [本文转录自 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://webptt.com/cn.aspx?n=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