快速排序

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


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

然后使用分治法的思想分别对左边 [全部小于基于基准值的数] 和右边 [全部大于基准值的数] 应用同样的策略

左右两个的长度都是 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 的位置。

函数返回这个基准值的位置，方便给快速排序传入子数组的范围。

实例代码


#include <stdio.h>
#include <stdlib.h>

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;
}

void quick_sort(int a[], int low, int high) {
  if (low < high) {
    int mid = one_time(a, low, high);
    quick_sort(a, low, mid - 1);
    quick_sort(a, mid + 1, high);
  }
}

int main() {
  int a[] = {12, 135, 23, 234, 123,
			 0, 12, 8, 56, 1};
  int len = sizeof(a) / sizeof(a[0]);
  quick_sort(a, 0, len - 1);
  for (int i = 0; i < 10; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;