每天一道面试题（1）：快速排序

0. 快速排序设计思想

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复（1，2），直到各区间只有一个数。

1. 源码及测试结果

1.1 源码如下：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 
 5 template <typename T>
 6 void swap(T &x, T &y) {
 7   T temp;
 8   temp = x;
 9   x = y;
10   y = temp;
11 }
12 
13 // quick_sort 调用 place 保证 left<right
14 int place(int *a, const int left, const int right) {
15   int select = left;
16   int i = select + 1;
17   int j = right;
18 
19   // 基准数将整个数列分成左右两个区间
20   while (true) {
21     for (; i < j && a[i] < a[select]; ++i);
22     // 注意 select < j 确保后面的 swap(a[select], a[j]); 正确
23     // 即对 1,2 这种情况也正确
24     for (; select < j && a[j] > a[select]; --j);
25     if (i < j) {
26       swap(a[i], a[j]);
27     } else {
28       break;
29     }
30   }
31   // 将基准数放到指定位置
32   swap(a[select], a[j]);
33 
34   // 基准数位置
35   return j;
36 }
37 
38 // 分治法实现快速排序
39 void quick_sort(int *a, const int left, const int right) {
40   // 注意：left < right 必须加上
41   if(left < right) {
42     int mid = place(a, left, right);
43     quick_sort(a, left, mid-1);
44     quick_sort(a, mid+1, right);
45   }
46 }
47 
48 // 测试用例
49 int main(int argc, char** argv) {
50   int a[10] = {3,2,5,1,7,8,6,9,4,0};
51   int end = atoi(argv[1]);
52 
53   printf("before: ");
54   for(int i = 0; i <= end; ++i) {
55     printf("%d ", a[i]);
56   }
57   printf("
");
58 
59   quick_sort(a, 0, end);
60 
61   printf("after: ");
62   for(int i = 0; i <= end; ++i) {
63     printf("%d ", a[i]);
64   }
65   printf("
");
66 
67   return 0;
68 }

1.2 测试结果如下：

2. 面试注意事项

（1）考查代码实现一般注重代码的正确性，即一般情况和极值情况下算法都正确

（2）在测试时，至少要测试数组大小为1,2,3三种情况

（3）以非递归的形式改写该算法

（4）快速排序算法复杂度：O(nlogn)，是不稳定的排序算法（即3a,3b,3c,可能得出3b,3c,3a的结果）

3. 小结

快速排序是面试中经常出现的算法题。一般面试官会要求在纸上写代码，所以我们平常不要漠视常见算法的实现，因为这能考查编程基本功。