选择排序

. . . . . .

定义

归并排序（merge sort）是高效的基于比较的稳定排序算法。

性质

归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 O(n log n)，空间复杂度为 O(n)。

归并排序可以只使用 O(1) 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。

过程

归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。

从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。

为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）而非小于时（a[i] < b[j]）就要作为最小值放入 c[k]。

分治法实现归并排序

1.当数组长度为 1 时，该数组就已经是有序的，不用再分解。

2.当数组长度大于 1 时，该数组很可能不是有序的。此时将该数组分为两段，再分别检查两个数组是否有序（用第 1 条）。如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 2 条，再合并。

用数学归纳法可以证明该流程可以将一个数组转变为有序数组。

为保证排序的复杂度，通常将数组分为尽量等长的两段（mid = l + r >> 1）。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,a[100010];
int tmp[100010];
void merge_sort(int l, int r)
{
	if (l >= r) return;
	
	int mid = l + r >> 1;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	
	int k = 0,i = l,j = mid + 1;
	while (i <= mid && j <= r)
		if (a[i] <= a[j]) tmp[k++] = a[i++];
	else tmp[k++] = a[j++];
	
	while (i <= mid) tmp[k++] = a[i++];
	while (j <= r) tmp[k++] = a[j++];
	
	for (i = l,j = 0;i <= r;i++,j++) a[i] = tmp[j];
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	merge_sort(1,n);
	for(int i = 1;i <= n;i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

. . . . . .