快速排序

快速排序的思想：

1、选基数（从数列中选取一个数为基准数）

2、分区（将比基准数大的都放到基准数右边，小的放在基准数左边）

3、递归（对基准数左分区、右分区重复以上步骤）

当递归到单个元素时，数组就已经有序了。其中的难点在于第二步分区。

i j

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

我们就以第一个元素为基准数X，来分析如何分区。

我们设置i、j两个索引，初始时i = 0、j = 9 X = a[i] = 72

具体的合并过程如下：

1、j由后向前找比基准数小的数，找到后替换a[i]

2、i由前向后找比基准数大的数，找到后替换a[j]

3、重复以上步骤，直到i == j，此时用基准数替换a[i]

分区的代码：

 1 int partition(int a[], int first, int last)
 2 {
 3     int i = first;
 4     int j = last;
 5     int x = a[i];
 6     while (i < j)
 7     {
 8         while (a[j] >= x) --j;　　　　  // 从后向前找比x小的数
 9         if (i < j) a[i++] = a[j];      // 找到后判断并替换a[i]的值
10 
11         while (i < j && a[i] < x) ++i; // 从前向后找比x大的数
12         if (i < j) a[j--] = a[i];      // 找到后判断并替换a[j]的值
13     }
14     a[i] = x;　　// 将基准值插入
15     return i;   // 返回基准值的下标
16 }

分治的代码：

1 void quickSort(int a[], int first, int last)
2 {
3     if (first < last)
4     {
5         int i = partition(a, first, last);
6         quickSort(a, first, i - 1);
7         quickSort(a, i + 1, last);
8     }
9 }

合并之后的代码：

 1 int quickSort(int a[], int first, int last)
 2 {
 3     if (first < last)
 4     {
 5         int i = first;
 6         int j = last;
 7         int x = a[i];
 8         while (i < j)
 9         {
10             while (a[j] >= x) --j;
11             if (i < j) a[i++] = a[j];
12 
13             while (i < j && a[i] < x) ++i;
14             if (i < j) a[j--] = a[i];
15         }
16         a[i] = x;
17         quickSort(a, first, i - 1);　　　　
18         quickSort(a, i + 1, last);
19     }
20 }