一、快速排序：
快速排序算法模板
void quick_sort(int q[], int l, int r) { //递归的终止情况 if (l >= r) return; //第一步：分成子问题 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]); } //第二步：递归处理子问题 quick_sort(q, l, j), quick_sort(q, j + 1, r); //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤 }
思路：
(1).有数组 q, 左端点 l, 右端点r
(2).确定划分边界 x.（这里可以是r，l，(l+r)/2，都可以）
(3).将 q 分为 <=x 和 >=x 的两个小数组
(4).i 的含义: i 之前的元素都 ≤x, 即 q[l..i−1] ≤x
(5).j的含义: j 之后的元素都 ≥x, 即 qq[j+1..r] ≥x
(6).结论: while 循环结束后, q[l..j] ≤x,q[j+1..r]≥x q[j+1..r] ≥x
(7).简单不严谨证明:
while 循环结束时, i≥j
若 i>j, 显然成立
若 i=j
∵ 最后一轮循环中两个 do−while 循环条件都不成立
∴ q[i]≥x,q[j]≤x
∴ q[i]=q[j]=x
∴ 结论成立
(8).递归处理两个数组
过程
循环不变式：q[l..i] <= x q[j..r] >= x
1. 初始化
循环开始之前i = l - 1, j = r + 1
则q[l..i],q[j..r]为空，循环不变式显然成立
2. 循环
假设某轮循环开始前循环不变式成立，即q[l..i] <= x, q[j..r] >= x
执行循环体
do i++; while(q[i] < x);
会使得 q[l..i-1] <= x, q[i] >= x
do j--; while(q[j] > x);
会使得 q[j+1..r] >= x, q[j] <= x
if(i < j) swap(q[i], q[j]);
会使得 q[l..i] <= x, q[j..r] >= x
注意:由于使用do-while循环,所以i和j一定会自增,使得循环会继续下去,但是如果采用while循环(i和j的初始化做出对应的变更),i和j在特殊情况下不自增的话,循环就会卡死
例如:
while(q[i] < x) i++;
while(q[j] > x) j--;
当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环
3.终止
循环结束时，i >= j
二、归并排序
归并排序算法模板
void merge_sort(int q[], int l, int r) { //递归的终止情况 if (l >= r) return; int mid = l + r >> 1; //第二步：递归处理子问题 merge_sort(q, l, mid); merge_sort(q, mid + 1, r); //第三步：合并子问题 int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
思路：
(1).有数组 q, 左端点 l, 右端点 r
(2).确定划分边界 mid
(3).递归处理子问题 q[l..mid], q[mid+1..r]
(4).合并子问题
a.主体合并
至少有一个小数组添加到 tmp 数组中
b.收尾
可能存在的剩下的一个小数组的尾部直接添加到 tmp 数组中
c.复制回来
tmp 数组覆盖原数组
过程：
1.初始化
k = 0, tmp[0..k-1] 为空，显然成立
2.循环
假设某轮循环开始之前，循环不变式成立
若 q[i] <= q[j], 则 tmp[k] = q[i]
其中, q[i] <= q[i+1..mid], q[i] <= q[j] <= q[j+1..r]
∴ q[i] 是剩下的所有数中最小的一个
当 q[i] > q[j] 时，同理可以得到 tmp[k] = q[j] 是剩下数中最小的一个
∴ tmp[k] 是剩下数中最小的一个
∴ k自增之后，下轮循环开始之前，tmp[0..k-1]保存从小到大排序的最小k个数
3.终止
i > mid 或 j > r
则 q[l..mid] 和 q[mid+1..r] 其中一个数组的数都已遍历
tmp[0..k-1]保存从小到大排序的最小k个数
三、算法排序
sort(q,q+n);
例题：
给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
快速排序：
1. 2. #include <bits/stdc++.h> 3. #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n; int q[N]; void quick_sort(int q[] , int l , int r) { if(l >= r) return ; int i = l - 1 , j = r + 1; int mid = q[l + r >> 1]; while(i < j) { do i ++; while (q[i] < mid); do j --; while (q[j] > mid); if(i < j) swap(q[i] , q[j]); } quick_sort(q , l , j); quick_sort(q , j + 1 , r); } int main() { cin >> n; for(int i = 0; i < n; i ++) cin >> q[i]; quick_sort(q , 0 , n - 1); for(int i = 0; i < n; i ++) cout << q[i] << " "; return 0; } 6. const int N = 1e6 + 10; 7. 8. int n; 9. int q[N]; 10. 11. void quick_sort(int q[] , int l , int r) 12. { 13. if(l >= r) return ; 14. 15. int i = l - 1 , j = r + 1; 16. int mid = q[l + r >> 1]; 17. 18. while(i < j) 19. { 20. do i ++; while (q[i] < mid); 21. do j --; while (q[j] > mid); 22. if(i < j) swap(q[i] , q[j]); 23. } 24. quick_sort(q , l , j); 25. quick_sort(q , j + 1 , r); 26. } 27. int main() 28. { 29. cin >> n; 30. for(int i = 0; i < n; i ++) 31. cin >> q[i]; 32. 33. quick_sort(q , 0 , n - 1); 34. 35. for(int i = 0; i < n; i ++) 36. cout << q[i] << " "; 37. 38. return 0; 39. }
归并排序
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n; int q[N] , temp[N]; void merge_sort(int q[] , int l , int r) { //第一步：递归的终止情况 if(l >= r) return ; int mid = l + r >> 1; //第二步：递归处理子问题 merge_sort(q , l , mid); merge_sort(q , mid + 1 , r); //第三步：合并子问题 int k = 0; int i = l , j = mid + 1; while(i <= mid && j <= r) { if(q[i] < q[j]) temp[k ++] = q[i ++];//这里<就是升序，>就是降序 else temp[k ++] = q[j ++]; } while(i <= mid) temp[k ++] = q[i ++]; while(j <= r) temp[k ++] = q[j ++]; for(int i = l, k = 0; i <= r; i ++, k ++) q[i] = temp[k]; } int main() { cin >> n; for(int i = 0; i < n; i ++) cin >> q[i]; merge_sort(q , 0 , n - 1); for(int i = 0; i < n; i ++) cout << q[i] << " "; return 0; }
算法库函数：
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n; int q[N]; int main() { cin >> n; for(int i = 0; i < n; i ++) cin >> q[i]; sort(q , q + n); for(int i = 0; i < n; i ++) cout << q[i] << " "; return 0; }
