排序算法

第一节：普遍排序算法

1.计数排序

核心思想：开一个带含义的数组，下标为待排序的数x，下标对应的数值表示元素x出现的数量。由于数组下标是有序的，因此在统计过程中就将输入的元素x进行了排序。

优缺点：计数排序只适用于值域不是很大但数量可以很多的情况；另外，计数排序只适用于正整数排序，不能排序浮点型或字符串类型。

时间复杂度$O(n+k)$

空间复杂度$O(k)$

#include <iostream>
using namespace std;
int a[1000] = {0}, n, x; //开1000的数组，那么x的值域限制在0~999
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		a[x]++;
	}
	for (int i = 0; i <= 999; i++)//开1000的数组，那么x的值域限制在0~999
		if (a[i])
			for (int j = 1; j <= a[i]; j++)
				cout << i << ' ';
	return 0;
}

空间复杂度计算： int类型数组最大开到多大要根据题目的限制，比如有的题目限制512MB, 那么int类型数组最多开到134217728（大约1e8）。

计算过程：512MB = 512 * 1024 *1024B = 536870912B，1个int类型占4B，因此最多存储536870912/4 = 134217728（1e8）个int类型变量

时间复杂度计算：也是根据题目，大多数题目限制是1s，计算机在1s最多能执行1e8条指令， 也就是说我自己写的代码的时间复杂度在1s能处理的规模不能超过1e8，对应关系请看下表：

时间复杂度	1s能处理的数据规模
$O(1)$	$\infty$
$O(n)$	$10^7$
$O(n^2)$	$5000$
$O(n^3)$	$200$
$O(2^n)$	$20$
$O(n!)$	$11$
$O(\sqrt{n})$	$10^{15}$
$O(n \log n)$	$2 \times 10^6$

2.选择排序

核心思想：基于比较思想，以升序为例，每次在待排序序列中找到最小的数，将其放在最前面。如果有n个数，那么只要做n-1次这样的操作就可以将这个序列排好序。

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

#include <iostream>
using namespace std;
const int N = 1e5 + 10; //限制数量不找过1e5+10个
int a[N], n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n - 1; i++)
	{
		int t = i;
		for (int j = i + 1; j <= n; j++)
			if (a[j] < a[t])
				t = j;
		if (t != i)
			swap(a[t], a[i]);
	}
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

3.冒泡排序

核心思想：同样是基于交换的思想，以升序为例，每次将相邻两个数比较，如果前一个数比后一个数小，那就将这两个数交换位置，一轮下来，最小的数就交换到了最后。

时间复杂度：$O(n^2)$

空间复杂度:$O(1)$

#include <iostream>
using namespace std;
const int N = 1e5 + 10; //限制数量不找过1e5+10个
int a[N], n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n - 1; i++)
		for (int j = i; j <= n - i; j++)
				if (a[j + 1] < a[j])
					swap(a[j], a[j + 1]);
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

4.插入排序

核心思想：基于比较思想，以升序为例，每次将待排序中的数插入到已排序列中，如果有n个数，那么只需要执行n-1轮这个操作就可以完成排序（因为单个数有序）。

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

#include <iostream>
using namespace std;
const int N = 1e5 + 10; //限制数量不找过1e5+10个
int a[N], n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 2; i <= n; i++)
	{
		int x = a[i], j = i - 1;
		while (j >= 1 && x < a[j])
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = x;
	}
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

5.shell希尔排序（快速插入排序）

基本思想：由于插入排序在元素本来就有序情况下速度非常快，所以思考能否先将序列先粗糙排序然后在进行插入排序。假设序列长度为n，以升序为例。

1：每次选择一个间距step，第一次是step = n/2，以后每排完一轮将step /= 2。

2：枚举同一间距的不同起点k，例如step=2,k=0时1,3,5和step=2,k=1时2,4,6间距相同但起点不同。

3：插入排序。

时间复杂度：$O(n^{1.3})$ ~ $O(n^{1.5})$

空间复杂度：$O(1)$

#include <iostream>
using namespace std;
const int N = 1e5 + 10; //限制数量不找过1e5+10个
int a[N], n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int step = n / 2; step >= 1; step /= 2)//控制间距
	{
		for (int k = 0; k < step; k++)//遍历不同起点
		{
			for (int i = step + k; i <= n; i += step)//对每个分组进行插入排序
			{
				int x = a[i], j = i - step;
				while (j >= step && x < a[j])
				{
					a[j + step] = a[j];
					j -= step;
				}
				a[j + step] = x;
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

第二节：高效排序算法

1.快速排序

基本思想：用到了分治、递归、双指针的思想，以从小到大排序为例。

1：找到一个基准值x，通常是中间数、第一个数、最后一个数或是随机位置的数。

2：将比x小的数放在x左边，比x大的数放在x的右边。（双指针算法）

3：以x为中心拆分成左右两个序列，对于左序列和右序列，分别不断重复1、2两个步骤，直到序列中的数不可再分位置。（分治、递归算法）

时间复杂度：$O(n \log n)$

空间复杂度：$O(n \log n)$ ~ $O(n)$

#include <iostream>
using namespace std;
const int N = 1e5 + 10; //限制数量不找过1e5+10个
int a[N], n;
void quick_sort(int *a, int l, int r)
{
	if (l >= r) //如果序列只有一个数就不需要再排序了
		return;
	int i = l, j = r, mid = a[(l + r) / 2];//找中间数作为基准数-->1
	//双指针-->2
	while (i <= j)//小于等于是为了让两个递归区间正好相邻不重复
	{
		while (a[i] < mid) i++;//对于[2, 2, 2, 2, 2]
		while (a[j] > mid) j--;//如果加上等号会导致ij指针越界
		if (i <= j)
		{
			swap(a[i], a[j]);
			i++, j--; //不增加会导致死循环，因为ij指针会一直停在这
		}
	}
	//递归两个区间-->3
	if (l < j) quick_sort(a, l, j); //判断条件可以不要，因为函数一开始有终止条件
	if (i < r) quick_sort(a, i, r);
}
int main()
{
	ios::sync_with_stdio(0);//关闭流同步，使得输入输出更快
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	quick_sort(a, 1, n);//调用快速排序函数
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

2.归并排序

基本思想：类似快速排序，用到了分治、递归、双指针的思想，以从小到大排序为例：

1：划分区间，将一个区间化为两部分， 直到序列长度为1。（递归， 分治）

2：每两个子序列进行归并，使其成为有序序列。不断这个操作，使得整个序列有序。（双指针）

时间复杂度：$O(n \log n)$

空间复杂度：$O(n)$

#include <iostream>
using namespace std;
const int N = 1e5 + 10; //限制数量不找过1e5+10个
int n;
int a[N], b[N];
void merge_sort(int *a, int l, int r)
{
	if (l >= r) //如果序列只有一个数就不需要再排序了
		return;
	//划分区间-->1
	int mid = l + (r - l) / 2;
	merge_sort(a, l, mid);
	merge_sort(a, mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	//归并部分-->2
	while (i <= mid && j <= r)
		if (a[i] < a[j])
			b[++k] = a[i++];
		else
			b[++k] = a[j++];
	while (i <= mid)
		b[++k] = a[i++];
	while (j <= r)
		b[++k] = a[j++];
	for (int i = 1; i <= k; i++)
		a[l + i - 1] = b[i];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	merge_sort(a, 1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	return 0;
}

第三节 排序算法复杂度表

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度(辅助存储)	是否稳定	排序方式
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定	内部
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	内部
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定	内部
希尔排序	O(n log n) ~ O(n²)	O(n²)	O(n log n)	O(1)	不稳定	内部
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	外部
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n) ~ O(n)	不稳定	内部
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	内部
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	稳定	外部
桶排序	O(n + k)	O(n²)	O(n + k)	O(n + k)	稳定	外部
基数排序	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	稳定	外部