❤分治思想

  1. 边界处理
  2. 分成子问题，在快排中即将当前部分以某个数为对标分成左右两部分，左半部分小于等于该对标，右半部分大于等于该对标
  3. 递，即两次调用自己，分别处理左右两部分
  4. 归，无需操作，递完就已经排好序了。

先上代码：

  1. void quickSort(int[] q, int l, int r)
  2. {
  3.      //l 和 r 分别为数组两端下标，递归时分别为两部分的左右下标
  4.     if (l >= r) return;
  6.     int i = l - 1, j = r + 1;
  7.     //这里取该部分数组的中间值，如果只有两个元素，取的是左边
  8.     int x = q[l + (r - l >> 1)];
  9.     while (i < j) {
  10.         do i++; while (q[i] < x);
  11.         do j--; while (q[j] > x);
  12.         if (i < j) swap(q, i, j);
  13.     }
  14.     quickSort(q, l, j);
  15.     quickSort(q, j+1, r);
  16. }
  17. void swap(int[] q, int a, int b)
  18. {
  19.     int temp = q[a];
  20.     q[a] = q[b];
  21.     q[b] = temp;
  22. }

问题

  1. 证while循环结束后，q[l..j] <= x,q[j+1..r] >= x和q[l..i-1] <= x, q[i..r] >= x

证明：
初始化，i = l - 1, j = r + 1, 有q[l..i] <= x, q[j..r] >= x成立。
因为i左边和j右边此时都为空

保持，假设某轮循环开始前q[l..i] <= x, q[j..r] >= x成立。
进入循环后执行循环体
do i++; while (q[i] < x); 当q[i] >= x 时退出循环
do j--; while (q[j] > x); 当 q[j] <= x时退出循环
此时，若

  • i < j, q[l..i] <= x, q[j..r] >= x成立

最后一轮
进入循环后执行循环体
do i++; while (q[i] < x); 当q[i] >= x 时退出循环
do j--; while (q[j] > x); 当 q[j] <= x时退出循环

  • i == j, q[i] == q[j] = x, q[l..i] <= x, q[j..r] >= x成立。
  • i > j, q[l..i-1] <= x && q[i] >= x, q[j] <= x && q[j+1..r] >=x成立

i > j==>i - 1 > j - 1==>q[l..j - 1] <= x && q[j]<=x==>q[l..j] <= x && q[j+1..r] >=x
同理i > j==>i + 1 > j + 1==>q[i + 1..r] >= x && q[i] >=x==>q[l..i-1] <= x && q[i..r] >= x
得证！
所以递的两部分边界分别是(l, j), (j + 1, r) 或者 (l, i - 1), (i, r)

注意:循环结束时要记得检查是否存在数组越界/无限递归的情况
所以还需要证明j最终的取值范围是[l..r-1](即不存在n划分成0和n的无限递归情况),即j不能取到r
同理，若选i作为划分，i最终的取值范围是[l+1..r], 即i不能取到l。

  1. 证明：选择以j作为划分，x不能取q[r], 或者 选择以i作为划分， x 不能取q[l]

举个反例：取x == q[r]若数组当前是这样的：q[l..r-1] < x, q[r]=x结束循环时i和j都指向r。
两部分变成(l, r), (r+1, r)显然陷入无限递归中。

换个思路想以下，我们的目的是使得划分合理，即(l, j), (j + 1, r)不会出现无线递归情况，j需要满足j∈[l, r-1]。如果x不取q[r]是不是j出循环后一定位于[l,r-1]中呢？
答案是一定的。

证明:
假设 j 最终的值为 r ,说明只有一轮循环(两轮的话 j 至少会自减两次
说明q[r] <= x (因为要跳出do-while循环)
说明 i >= r(while循环的结束条件), i 为 r 或 r + 1(必不可能成立)
说明 i 自增到了 r , 说明 q[r] >= x 和 q[l..r-1] < x,
得出 q[r] = x 和 q[l..r-1] < x的结论,但这与 x = q[l + r >> 1]矛盾
“这里也是为什么x不能取q[r]的原因”
反证法得出 j < r

假设 j 可能小于 l 说明 q[l..r] > x ,矛盾
反证法得出 j >= l

所以 j的取值范围为[l..r-1],不会造成无限划分和数组越界

其它模板

  1. //用i作划分
  2. void quickSort(int[] q, int l, int r)
  3. {
  4.      //l 和 r 分别为数组两端下标，递归时分别为两部分的左右下标
  5.     if (l >= r) return;
  7.     int i = l - 1, j = r + 1;
  8.     //这里取该部分数组的中间值，如果只有两个元素，取的是左边
  9.     int x = q[l + (r - l + 1 >> 1)];
  10.     while (i < j) {
  11.         do i++; while (q[i] < x);
  12.         do j--; while (q[j] > x);
  13.         if (i < j) swap(q, i, j);
  14.     }
  15.     quickSort(q, l, i-1);
  16.     quickSort(q, i, r);
  17. }
  18. void swap(int[] q, int a, int b)
  19. {
  20.     int temp = q[a];
  21.     q[a] = q[b];
  22.     q[b] = temp;
  23. }
  1. //从大往小排序
  2. void quickSort(int[] q, int l, int r)
  3. {
  4.      //l 和 r 分别为数组两端下标，递归时分别为两部分的左右下标
  5.     if (l >= r) return;
  7.     int i = l - 1, j = r + 1;
  8.     //这里取该部分数组的中间值，如果只有两个元素，取的是左边
  9.     int x = q[l + (r - l >> 1)];
  10.     while (i < j) {
  11.         do i++; while (q[i] > x);
  12.         do j--; while (q[j] < x);        //只需要改变这两个while中的关系符即可
  13.         if (i < j) swap(q, i, j);
  14.     }
  15.     quickSort(q, l, j);
  16.     quickSort(q, j+1, r);
  17. }
  18. void swap(int[] q, int a, int b)
  19. {
  20.     int temp = q[a];
  21.     q[a] = q[b];
  22.     q[b] = temp;
  23. }