Acwing 排序

1.快速排序

主要思想：基于分治思想。通过选择一个基准元素，将数组分为两部分，左边部分元素都小于等于基准，右边部分元素都大于等于基准。然后对这两部分分别递归地进行排序。

分区逻辑：双指针算法

• 左指针i从左往右找到第一个大于等于基准的元素
• 右指针从右往左找到第一个小于等于基准的元素
• 交换两个元素，使得左侧部分小于等于基准，右侧部分大于等于基准

设l是待排序区间的左边界，r是右边界

1. 确定分界点x（基准），可以取左边界的值q[l]，或右边界的值q[r]，或者中间位置的值q[(l + r)/2]
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

3. 递归处理左右两段，
   • 若用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。最坏情况（例如数组已经有序的情况下），时间复杂度为 $O(n^2)$，但通过选择中间值作为基准，可以减少最坏情况的发生。

这里给出一个快排的板子：

// 快速排序函数，q[] 是待排序的数组，l 是左边界，r 是右边界
void quick_sort(int q[], int l, int r) {if (l >= r) return;  // 递归终止条件：当左边界大于或等于右边界时停止递归// 选择中间元素作为基准数，并初始化左右指针 i 和 jint 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 和 jint 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数组。

归并排序的时间复杂度为 $O(nlogn)$，即使在最坏的情况下也是如此。它的性能较为稳定，适用于大规模数据的排序任务

归并排序的板子：

const int N = 1e6 + 10;  // 定义数组容量为 10^6 + 10int 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 + 10int 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的存储范围(-2^31~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;
}

以上就是两种经典常考的排序算法，快排的思想是选择基准点，然后进行分区；而归并排序是选择一个位置，将原序列划分为两个序列，再分别进行排序，最后合并为一个有序数组。可以看到各有优缺点，下面进行一个简答的总结：