快速排序

快速排序 ​

• 通过交换的方法，完成将一个乱序的数组排序成：

[全都小于基准值的数] 基准值 [全都大于基准值的数]

• 然后使用分治法的思想分别对左边 [全部小于基于基准值的数] 和右边 [全部大于基准值的数] 应用同样的策略
• 左右两个的长度都是 1 为止
• 最后，获得的数组即为有序数组

一次交换的过程 ​

• 对于一个无序的数组，首先拿第一个元素作为基准值，将它从原来的位置取出，从数组的高位开始比较：

key=[12] [ ], 135, 23, 234, 123, 0, 14, 8
          ↑ low                         ↑ high

• 因为 8 小于 12 应当移动到低位去，把它放到 low 的位置，然后从低位开始比较：

key=[12] 8, 135, 23, 234, 123, 0, 14, [ ]
         ↑ low                         ↑ high

• 因为 8 是小于 12 的，让 low++ 查找下一个：

key=[12] 8, 135, 23, 234, 123, 0, 14, [ ]
             ↑ low                     ↑ high

• 因为 135 是大于 12 的，把它放到 high 的位置，然后再返回高位开始比较：

key=[12] 8, [ ], 23, 234, 123, 0, 14, 135
             ↑ low                     ↑ high

• 因为 135 大于 12 符合高位，让 high--，下一个 14 也符合，继续 high--，此时：

key=[12] 8, [ ], 23, 234, 123, 0, 14, 135
             ↑ low             ↑ high

• 0 小于 12，交换到 low 位置，返回从 low 开始比较：

key=[12] 8,  0, 23, 234, 123, [ ], 14, 135
             ↑ low             ↑ high

• 0 符合，low++，此时：

key=[12] 8,  0, 23, 234, 123, [ ], 14, 135
                 ↑ low         ↑ high

• 23 大于 12，交换，切换到 high：

key=[12] 8,  0, [ ], 234, 123, 23, 14, 135
                 ↑ low         ↑ high

• 123 大于 12，234 也大于 12，于是 high 进行了两次 high--，此时：

key=[12] 8,  0, [ ], 234, 123, 23, 14, 135
                 ↑ low/high

• low 和 high 达到同一个位置，把 12 放进这个位置

8,  0, 12, 234, 123, 23, 14, 135

• 最终形成了一个 12 左边的数字都小于 12，右边数字都大于 12 的数组。

一次交换的代码 ​

int one_time(int a[], int low, int high) {
  int key = a[low];
  while (low < high) {
    while (low < high && a[high] >= key)
      high--;
    a[low] = a[high];
    while (low < high && a[low] <= key)
      low++;
    a[high] = a[low];
  }
  /* 此时 low 等于 high */
  a[low] = key;
  return low;
}

• 因为从上面过程中我们已经知道交换结束的条件是 low == high，所以可以设置循环的条件为 low < high。
• 先从高位开始查找，没找到就 high--，但如果，key 本身就是最大的数字，可能会找不到导致程序挂死，所以设置 low < high，防止越界。
• 高位查找的循环在找到时停止，此时交换位置上的数据，并切换到 low 开始查找，查找的方法和 high 处是一样的。
• 如果还没有满足 low == high 的条件，循环继续，会再次跳回 high 处查找。
• 最后记得把基准值放到 low/high 的位置。
• 函数返回这个基准值的位置，方便给快速排序传入子数组的范围。

完整代码 ​

• quicksort.c