[算法学习]模板-排序(快排、归并排序)

两种算法都用到了递归|分治的思想

1.快速排序（双指针法）

原理刨析：

采用分治的思想，随意选取一个数组中的中间值，以他为基准，将数组分为左右两部分，基准左侧的值均小于等于基准值，而基准右侧的值均大于等于基准值，以此类推，采用递归的方法，不断缩小数据处理范围，最终实现排序。

所以该方法的重点在于如何将数组分为这两部分能够更快。如此我们便可引用两个变量作为指针，同时移动在各自的区域，来不断的将不满足条件的数移到合适的区域中。如何实现这一操作呢？我们可以通过不断让两端的指针找到第一个不符合该区域条件的数组下标，接着让这两个数组下标的值交换一下，便可粗略的实现排序（即左边右边区分开来了）接下来看代码。

代码示例：

#include<bits/stdc++.h>
#define debug(x) cout << #x << ":" << x << endl
using namespace std;
using ll = long long;
const int N = 1e6+10;
// 数组q用于存储待排序的元素
int q[N];
// 快速排序函数quick_sort，参数为数组q，以及待排序区间的左右边界l和r
void quick_sort(int q[], int l, int r);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//读取操作
	int n;
	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] << " ";
}
void quick_sort(int q[], int l, int r) {
	// 如果左边界l大于等于右边界r，说明区间内元素个数等于1或者0，无需排序，直接返回
	if (l >= r)return;
	// 选择数组中间元素q[l+r/2]作为基准元素x，初始化左指针i为l-1，右指针j为r+1
	//左指针之所以为l-1，右指针之所以为r+1，是为了便利后续操作，因为后续操作为++i，++j，是先移动指针i和j，然后再和基准元素x做比较
	int x = q[(l+r)>>1], i = l - 1, j = r + 1;
	// 当左指针i小于右指针j时，继续循环，进行元素交换和指针移动
	while (i < j) {
		// 从左向右移动左指针i，直到找到一个大于等于基准元素x的元素才停止
		while (q[++i] < x);
		// 从右向左移动右指针j，直到找到一个小于等于基准元素x的元素才停止
		while (q[--j] > x);
		// 如果i小于j，说明找到了一对需要交换位置的元素，交换它们
		if (i < j) swap(q[i], q[j]);
	}
	// 递归调用快速排序函数，对左子数组（即基准元素x左边的子数组）进行排序
	quick_sort(q, l, j);
	// 递归调用快速排序函数，对右子数组（即基准元素x右边的子数组）进行排序
	quick_sort(q, j + 1, r);
}

注意事项：

易出错的地方在于左右指针的初始化、指针移动的操作。

2.归并排序

原理刨析：

依旧是将待排数组分为两部分，但与快排不同的是，这两部分均是有序的，然后我们再通过对两部分数组元素的比较（同时遍历左右两个有序区间 每次取较小的元素放入 temp 中），将两个有序数组归并为一个有序数组，即完成排序。

代码示例：

#include<bits/stdc++.h>
#define debug(x) cout << #x << ":" << x << endl
using namespace std;
using ll = long long;
const int N = 1e6+10;
int q[N];
int temp[N];
void merge_sort(int q[], int l, int r)
{
	// 递归终止条件：当区间中只有 0 或 1 个元素时，已经有序
	if (l >= r) return;
	// 计算当前区间 [l, r] 的中点
	// 使用 >>1 等价于 (l + r) / 2
	int mid = (l + r) >> 1;
	// 递归排序左半区间 [l, mid]
	merge_sort(q, l, mid);
	// 递归排序右半区间 [mid + 1, r]
	merge_sort(q, mid + 1, r);
	// k：临时数组 temp 的下标
	// i：指向左半区间的起始位置
	// j：指向右半区间的起始位置
	int k = 0, i = l, j = mid + 1;
	// 同时遍历左右两个有序区间
	// 每次取较小的元素放入 temp 中
	while (i <= mid && j <= r)
	{
		// 如果左边元素更小（或相等），先放左边
		if (q[i] <= q[j])temp[k++] = q[i++];
		// 否则放右边元素
		else temp[k++] = q[j++];
	}
	// 如果左半区间还有剩余元素，全部拷贝到 temp
	while (i <= mid)temp[k++] = q[i++];
	// 如果右半区间还有剩余元素，全部拷贝到 temp
	while (j <= r)temp[k++] = q[j++];
	// 将排好序的 temp 数组拷贝回原数组 q 的 [l, r] 区间
	// i 从 l 开始，对应原数组位置
	// j 从 0 开始，对应 temp 数组位置
	for (int i = l, j = 0; i <= r; i++, j++)q[i] = temp[j];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	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]<<" ";
}

注意事项：

不要忘记对剩余元素的处理和将排好序的数组拷贝到原数组。