1.快速排序
主要思想：基于分治思想。通过选择一个基准元素，将数组分为两部分，左边部分元素都小于等于基准，右边部分元素都大于等于基准。然后对这两部分分别递归地进行排序。
分区逻辑：双指针算法
- 左指针i从左往右找到第一个大于等于基准的元素
- 右指针从右往左找到第一个小于等于基准的元素
- 交换两个元素，使得左侧部分小于等于基准，右侧部分大于等于基准
设l是待排序区间的左边界，r是右边界
- 确定分界点x（基准），可以取左边界的值
q[l]，或右边界的值q[r]，或者中间位置的值q[(l + r)/2] - 根据基准值，调整区间，使得左半边区间的值全都
≤ x，右半边区间的值全都≥ x.
采用双指针：左指针i从左边界l-1开始，往右扫描，右指针j从右边界r+1开始，往左扫描
为什么初始是l-1，r+1？
因为后续的不管执行交换与否，首先都先将i，j向内移动一位，所以一开始的两个指针都设置为超出边界一个位置
当满足条件q[i] < x时，i右移；直到不满足条件时，即q[i] >= x，i停下;
然后移动右指针j，j 当满足条件q[j] > x时，j左移；直到不满足条件时，即q[j] <= x，j停下；
交换q[i]和q[j] 将i右移一位，j左移一位，重复上面的操作，直到i和j相遇(最终i和j的位置为：i==j或i=j+1)。 此时左半区间的数都满足≤x，且左半区间的最后一个数的下标为j，右半区间的数都满足≥ x,且右半区间的第一个数的下标为i
- 递归处理左右两段，
- 若用
j来作为区间的分界，则[l, j]都是≤x，[j + 1, r]都是≥x - 若用
i来作为区间的分界，则[l, i - 1]都是≤x，[i, r]都是≥x
- 若用
注意：
递归取[l, j]，[j + 1, r]区间时，基准值不能取右边界x=q[r]，不然会出现死循环问题，此时常取左边界x=q[l]或中间值 （eg:1,2 会出现死循环）
同理当递归取[l, i - 1]，[i,r]区间时，基准值不能取左边界x=q[l]，不然会出现死循环问题，此时常取左边界x=q[r] 或中间值 （eg:1,2 会出现死循环）
快排不稳定，平均时间复杂度nlogn。最坏情况（例如数组已经有序的情况下），时间复杂度为 𝑂 ( 𝑛 2 ) 𝑂(𝑛^2) O(n2)，但通过选择中间值作为基准，可以减少最坏情况的发生。
这里给出一个快排的板子：
// 快速排序函数，q[] 是待排序的数组，l 是左边界，r 是右边界
void quick_sort(int q[], int l, int r) {
if (l >= r) return; // 递归终止条件：当左边界大于或等于右边界时停止递归
// 选择中间元素作为基准数，并初始化左右指针 i 和 j
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
// 使用双指针法进行分区
while (i < j) {
// 从左边开始找到第一个大于等于基准数的元素
do i++; while (q[i] < x);
// 从右边开始找到第一个小于等于基准数的元素
do j--; while (q[j] > x);
// 如果 i 和 j 没有相遇，交换 q[i] 和 q[j]，确保左边都比基准数小，右边都比基准数大
if (i < j) swap(q[i], q[j]);
}
// 递归处理左半部分
quick_sort(q, l, j);
// 递归处理右半部分
quick_sort(q, j + 1, r);
}
Acwing 785.快速排序
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N]; // 存储待排序的数组
// 快速排序函数，q[] 是待排序的数组，l 是左边界，r 是右边界
void quick_sort(int q[], int l, int r) {
if (l >= r) return; // 递归终止条件：当左边界大于或等于右边界时停止递归
// 选择中间元素作为基准数，并初始化左右指针 i 和 j
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
// 使用双指针法进行分区
while (i < j) {
// 从左边开始找到第一个大于等于基准数的元素
do i++; while (q[i] < x);
// 从右边开始找到第一个小于等于基准数的元素
do j--; while (q[j] > x);
// 如果 i 和 j 没有相遇，交换 q[i] 和 q[j]，确保左边都比基准数小，右边都比基准数大
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] << ' ';
cout << endl;
return 0;
}
Acwing 786.第k个数
实现思路：直接进行快排，然后注意第k个数的数组下标是k-1,即答案就是q[ k - 1].
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n , k;
int q[N];
//快速排序
void quick_sort(int q[],int l , int r){
if(l >= r) return ;
int x = q[(l + r) / 2], i = l - 1, j = 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);
}
int main(){
cin >> n >> k ;
for(int i = 0 ; i < n ; i ++) cin >> q[i];
quick_sort(q, 0 , n - 1);
//第k个数
cout << q[k - 1] << endl;
return 0;
}
2.归并排序
主要思想：也是基于分治思想
- 先确认分界点（下标）：一般取中间点（l + r) /2;
- 对左右两个子数组分别进行递归排序
- 将两个排好序的子数组合二为一
实现思路：设置左右指针和一个临时数组temp，左指针指向左区间的的第一个元素，右指针指向右区间的第一个元素，循环比较左右指针所指元素，两者较小的元素放入temp数组中，指针后移继续比较。直至某一指针到达末尾，将其中一个未放置完的区间的数再都放入temp数组。
归并排序的时间复杂度为 𝑂 ( 𝑛 l o g 𝑛 ) 𝑂(𝑛log𝑛) O(nlogn)，即使在最坏的情况下也是如此。它的性能较为稳定，适用于大规模数据的排序任务
归并排序的板子：
const int N = 1e6 + 10; // 定义数组容量为 10^6 + 10
int n;
int q[N], temp[N]; // q[] 存储待排序的数组，temp[] 是归并时的临时数组
// 归并排序函数，q[] 是待排序的数组，l 是左边界，r 是右边界
void merge_sort(int q[], int l, int r) {
if (l >= r) return; // 递归终止条件：如果只有一个元素，直接返回
int mid = (l + r) / 2; // 取中间点，将数组分成两部分
// 递归处理左半部分
merge_sort(q, l, mid);
// 递归处理右半部分
merge_sort(q, mid + 1, r);
// 合并两个有序的部分
int i = l, j = mid + 1, k = 0; // i 追踪左半部分，j 追踪右半部分，k 追踪临时数组
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 (i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
}
Acwing 787.归并排序
具体实现代码（详解版）：
#include <iostream>
using namespace std;
const int N = 1e6 + 10; // 定义数组容量为 10^6 + 10
int n;
int q[N], temp[N]; // q[] 存储待排序的数组，temp[] 是归并时的临时数组
// 归并排序函数，q[] 是待排序的数组，l 是左边界，r 是右边界
void merge_sort(int q[], int l, int r) {
if (l >= r) return; // 递归终止条件：如果只有一个元素，直接返回
int mid = (l + r) / 2; // 取中间点，将数组分成两部分
// 递归处理左半部分
merge_sort(q, l, mid);
// 递归处理右半部分
merge_sort(q, mid + 1, r);
// 合并两个有序的部分
int i = l, j = mid + 1, k = 0; // i 追踪左半部分，j 追踪右半部分，k 追踪临时数组
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 (i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
}
int main() {
cin >> n; // 输入数组长度
// 读取 n 个元素存入数组 q 中
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] << ' ';
cout << endl; // 换行
return 0; // 程序结束
}
Acwing.788求逆序对的数量
实现思路：
- 根据归并排序的思想，将数组分为各自有序的左右两个区间
[l,mid],[mid+1,r]，采用双指针开始分别指向两个区间的第一个元素，相互比较选出较小的那个元素，然后后移，不断循环，直到一个区间遍历完。 - 在比较过程中，设
i指向左区间，j指向右区间，由于两个区间各自有序，逆序对只会出现一种情况，即左区间存在大于右区间元素的元素。 - 若
a[i]>a[j]，则左区间中从i开始到mid的元素都大于a[j]，与a[j]组成逆序对，数量为mid-i+1
注意：对于给定n个数，最坏的情况为逆序，则逆序对数为n(n-1)/2个，题中数据个数范围为100000，则最大结果会超出int的存储范围(-231~231-1)，所以虽好使用long long来存储最终结果
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
int q[N], temp[N]; // q[] 用于存储输入数组，temp[] 用于合并时的临时数组
// 归并排序函数，返回区间 [l, r] 的逆序对数量
LL merge_sort(int l, int r) {
if (l >= r) return 0; // 如果区间内只有一个元素，返回 0，表示没有逆序对
int mid = (l + r) / 2; // 找到中间位置
// 递归处理左半部分和右半部分，并计算各自的逆序对数量
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
// 合并两个有序区间，同时统计逆序对
int i = l, j = mid + 1, k = 0; // i 指向左区间，j 指向右区间，k 是 temp 的索引
while (i <= mid && j <= r) {
if (q[i] <= q[j]) {
temp[k++] = q[i++]; // 如果左区间的元素小于等于右区间，取左区间的元素
} else {
temp[k++] = q[j++]; // 否则取右区间的元素
res += mid - i + 1; // 统计逆序对的数量，mid - i + 1 表示当前左区间剩余的元素个数
}
}
// 如果左区间还有剩余元素，直接加入 temp[]
while (i <= mid) temp[k++] = q[i++];
// 如果右区间还有剩余元素，直接加入 temp[]
while (j <= r) temp[k++] = q[j++];
// 将 temp[] 中的元素复制回原数组 q[]
for (int i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
return res; // 返回逆序对的数量
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
// 输出逆序对的数量
cout << merge_sort(0, n - 1) << endl;
return 0;
}
以上就是两种经典常考的排序算法，快排的思想是选择基准点，然后进行分区；而归并排序是选择一个位置，将原序列划分为两个序列，再分别进行排序，最后合并为一个有序数组。可以看到各有优缺点，下面进行一个简答的总结：
