快排

快排与归并属于分治算法，分治算法都有三步：

1. 分成子问题
2. 递归处理子问题
3. 子问题合并
   快排：（默认为升序）
   快速排序模板题
   我针对这一题浅谈一下我对快排的理解：

先取分界值X 再将区域划分为左右两边 我们的分解条件是左半边数字小于X
右半边数字大于X

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
void quick_sort(int l, int r)
{
    
	if (l >= r)
		return;
	int i = l - 1, j = r + 1, x = arr[l + r >> 1];//分界点x也需要阐述边界
	while (i < j)
	{
    
		do i++; while (arr[i] < x);
		do j--; while (arr[j] > x);
		if (i < j) swap(arr[i], arr[j]);
	} 
	quick_sort(l, j);//边界问题需要阐述
	quick_sort(j + 1, r);
}
int main()
{
    
	int n = 0;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	quick_sort(0, n - 1);
	for (int i = 0; i < n; i++) cout << arr[i];
	cout << endl;
	return 0;

}

举个例子（i为左半边端点 j为右半边端点 ）
2 10 3 4 5
第一次左右端点分别是（0，4）
第一次取x = 2 i = 0，j = 4
则当第一次交换时 i = 0，j = 2 此时数字的排序： 2 10 3 4 5
继续循环发现 j = 0 i = 1；
此时递归发现 左半部分是（0，0） 右半部分是（1，4 ）
左半部分跳出递归 但是右半部分继续递归 以此类推
这样看我的例子也许很好理解 但是这里面有几个需要注意的边界问题
首先是X的取值问题 因为这个关系到下面递归区域的划分

x = arr[l + r >> 1]//这是我的代码 但
x = arr[l]//
x = arr[r]
//这三者都可以 但是对应的递归的分界点是不一样的
//首先针对的是x = arr[l]
此时边界只能是（l,j)(j+1,r)
//而当x = arr[r]时边界只能时(l,i-1)(i,j)
//x = arr[l]时，因为计算机是向下取整的 我们取两个特殊值 1,2
//这里记一下 第一次进函数的边界是(0,1)
//假设此时需要排序的就是这两个值 取x = 1；当达到第一次交换条件时
//i = 0，j = 0；这个时候向下递归 如果边界是(l,i-1)(i,r)时 对应的便是
//（0,-1）(0,1) 我们可以发现这时候和刚开始进函数的边界取值是一样的 所以
//便会无线递归下去 同理 当x = arr[r]的时候道理也是一样的

这边需要注意的时候 即使针对上面的x = arr[r],x = arr[l] 即使取对了边界 但还是很有可能遇到超时问题 因为思考一下 当你的x分解值取的是最左边的时候 题目给你一个升序的序列 但是你确实要将它们排成降序 那么？时间复杂度是O（n^2)所以我自己取的是(l+r>>1)取中间值 但我的递归边界确实需要和x = arr[l]一样的 因为当需要排序的数字只是简单的1，2 那么由于向下取整 面临的分解问题将是和上述提到的一样。

这是一个大佬的关于分解问题的具体阐述
快速排序算法的证明与边界分析

以上仅是我这个小白对快排的简单理解 不足之处还望各位纠正

归并排序

下面我来简单阐述一下归并排序
也是分治的思想 只不过 多了一个归并的过程
同理我根据这道模板：归并排序模板题
提浅谈一下我对归并排序的理解
思路
因为是先递归的 所以我们得到的两边都是排好序的

左边l 到mid 都是从小到大排好的
右边也是如此
这个时候我们创建一个数组，位于l的数字和位于mid+1上的数字比较 较小的可以放在我们创建的数组中 当某一部分全部放入数组时 即l = mid+1或者j = r+1时 我们将另外一边的数字全部存入数组 至于为什么？
例如：
当左边的数字全部存入数组时候，因为两边的数字都是保序的 都是从小到大的 这个时候右半边剩下的数字肯定是全部都大于左半部分的 因此接下来便把剩下的数字全部存入数组中
这便是思路
代码如下

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N],s[N];
void merger_sort(int l, int r)
{
    
	if (l >= r)
		return;
	int mid = l + r >> 1;
	merger_sort(l, mid), merger_sort(mid + 1, r);
	int i = l, j = mid + 1,k = 0;
	while (i <= mid && j <= r)//这里需要注意 是两个条件都得满足 缺一不可
	{
    
		if (arr[i] < arr[j])
			s[k++] = arr[i++];
		else
			s[k++] = arr[j++];
	}
	while (i <= mid) s[k++] = arr[i++];
	while (j <= r) s[k++] = arr[j++];
	for (i = l, k = 0; i <= r; i++, k++)
// 我个人而言这句话是最容易错的 这边需要记住i<=r因为我们传的参数是n-1
		arr[i] = s[k];
}
int main()
{
    
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	merger_sort(0, n - 1);
	for (int i = 0; i < n; i++) cout << arr[i];
	cout << endl;
	return 0;
}

以上便是个人对这两种排序的简单理解
看了那么久来两道题吧！
快排

归并排序