前言
快速排序（Quick Sort）以及归并排序（Merge Sort）都是时间复杂度为O(nlogn)的排序算法，它们都用到了分治的思想，一般的分治算法都有三步：
- 大问题分成小问题
- 递归处理小问题
- 合并小问题
分治分治，先分后治，devide and conquer，而其中最重要的就是递归，要理解快排以及归并排序，就要记住一句话：分治后最小项可以满足，那递归完最大项也可以满足！
而递归大概也有三步：
- 明确函数功能
- 确定结束条件
- 缩小参数范围
快排
给你一个无序序列，让它成为升序序列。
而快排就是：
- 选定一个枢纽元素
- 分成两块，其左边的元素都比它小，右边的都比它大
- 继续划分，重复1，2步骤
void quick_sort(int l, int r) { // left, right if (l == r) return; // 递归结束条件 int x = a[(l+r)/2]; // 1.枢纽元素 // 2.分成两块 int i = l-1, j= r+1; while (i < j) { while (a[++i] < x); // 找到左边比x大的元素 while (a[--j] > x); // 找到右边比x小的元素 if (i < j) swap(a[i], a[j]); // 互换 } // 3.重复递归 quick_sort(l, j); quick_sort(j+1, r); } 复制代码
可以看到我们逐步把大问题分成了小问题，快排也没有用到分治的第三步“合并”，而快排最怕的是边界问题，也就是把n划分成0和n或者划分成n和0，这样会造成无限划分，所以我们最好选择中间值(l+r)/2。
第k个数
给你一个无序序列，找到升序排列的第k个数
这道题放到这里肯定是让你用快排做的，但是要怎么做呢？难道要整个快排一遍？当然不是。
我们只需要在每次重复递归的时候只递归第k个数所在的部分即可：
int kth (int l, int r, int k) { if (l == r) return a[l]; // a[l]与a[r]都可 int x = a[(l+r)/2], i = l-1, j= r+1; while (i < j) { while (a[++i] < x); while (a[--j] > x); if (i < j) swap(a[i], a[j]); } int sl = j - l + 1; // 1.计算左边部分的数量 if (k > sl) { // 2.k>sl证明第k个数在右边，所以只递归右边 return kth(l, j, sl-k); // 3.同时这个数就变成了右边的第sl-k个数 } else { return kth(j+1, r, k); // 4.左边同理 } } 复制代码
