- 快速排序算法（Quick Sort）
- 1. 算法基本思想和流程（期望时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) ，最坏情况 O ( n 2 ) O(n^2) O(n2) ）
- 2. 难点/关键点：步骤二的区间调整方法
- 3. 快排模板（背诵）
快速排序（Quick sort），使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。它是一种 分而治之思想 在排序算法上的典型应用。本质上来看，快速排序是对冒泡排序算法的一种改进，是在冒泡排序基础上的 递归分治法。
快速排序算法的优点在于 快，而且效率高 ！它是处理大数据最快的排序算法之一了。
1. 算法基本思想和流程（期望时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) ，最坏情况 O ( n 2 ) O(n^2) O(n2) ）- Step1——确定分界点x（三种常用的方法）：q[l]、q[(l+r)/2]、q[r]，或者随机确定。
- Step2——将待排序列调整成两个区间，使得满足以下两个原则（具体方法后面介绍）：
- 原则一：第一个区间里的所有数都 ≤x；
- 原则二：第二个区间里的所有数都 ≥x；
注意：要注意此处写代码的逻辑。并不是把所有小于等于x的数放在左边，所有大于等于x的数放在右边。 因为等于x的数可能在左边也可能在右边。
- Step3——递归处理左、右两端，将左边和右边都排好序，Finish！
（1）暴力做法： 用两个额外的空间（增加了空间复杂度，但时间复杂度不变：O(n)）
- 定义两个额外的数组 a[] 和 b[] ，其中数组 a[] 用来存放 ≤x 的所有数、数组 b[] 用来存放 >x 的所有数。
- 方法：遍历序列q，再写一个判断if-else分支语句即可。
- 然后，将 a 放前面， b 放后面组成的新数组 q* 即实现了区间调整。
（2）优美做法： 无需开辟额外空间（时间复杂度：O(n)）
- 定义两个指针：i = l 以及 j = r，即指针的初始值一个在最左边，一个在最右边。
- 两指针分别往中间移动，并进行以下判断：
- 如果 q[i] < x ，则满足原则一，i++，直到某个数 q[i] ≥ x ，停下来，开始移动 j ；
- 如果 q[j] > x ，则满足原则二，j-- ，直到某个数 q[j] ≤ x ，停下来；
- 交换两个指针指向的数： swap(q[i], q[j]) 。
- 返回第一步，继续移动 i 、 j ，直到相遇为止。
模板题：AcWing 785. 快速排序
注意：此题数据较大且多，输入输出建议使用 scanf 和 printf ，要使用C++的 cin 和 cout 需要进行速度优化，参考另一篇博文：C++ 输入输出（cin & cout）加速/效率优化 。
模板一
void quick_sort(int q[], int l, int r)
{
// 1.判边界
if (l >= r) return;
// 2.区间调整：双指针法，指针边界往外扩了一格偏移量
// 原因是每次判断前无论是否满足两个原则，两指针都会提前往中间移动一格
// 注意：x 为下取整，递归时的边界是 j 和 j + 1.
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
//3.递归处理左、右两端
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
模板二
void quick_sort(int q[], int l, int r)
{
// 1.判边界
if (l >= r) return;
// 2.区间调整：双指针法，指针边界往外扩了一格偏移量
// 原因是每次判断前无论是否满足两个原则，两指针都会提前往中间移动一格
// 注意：x 为上取整，递归时的边界是 i - 1 和 i.
int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
//3.递归处理左、右两端
quick_sort(q, l, i - 1);
quick_sort(q, i, r);
}
【分析避免边界问题】
- 当递归边界取的 i，即 quick_sort(q, l, i - 1); quick_sort(q, i, r);，则为了避免陷入死循环：
- 边界点 x 一定不能等于 q[l]，且如果取中间值，需要上取整 x = q[l + r + 1 >> 1]
- 当递归边界取的 j，即 quick_sort(q, l, j); quick_sort(q, j + 1, r);，则为了避免陷入死循环：
- 边界点 x 一定不能等于 q[r]，且如果取中间值，需要下取整 x = q[l + r >> 1]
