总所周知，插入排序的效率并不高。

但我有个问题

为什么插入排序效率不高呢？

乌龟

乌龟，既在数组后面相对比较小的数

虽然对插入排序的影响没有对冒泡排序的影响那么大

但却直接让插入排序的时间复杂度飙升到了o(n^2)

TLE

说白点

就是在很乱的时候插入比较次数太多

导致时间复杂度太高

但我们也知道了

当数组保持大体有序，其实插入排序的效率挺高的

我突发奇想

让数组变得大体有序，我用o(n)的时间复杂度就能让数组大体有序

优化如下：

for (int i = 1 ; i <= n / 2 ; i++)
	if (a[i] > a[n - i + 1])
		swap(a[i], a[n - i + 1]);
int key = n / 3;
for (int i = 1 ; i + key <= n ; i++)
	if (a[i] > a[i + key])
		swap(a[i], a[i + key]);
key = n / 4;
for (int i = 1 ; i + key <= n ; i++)
	if (a[i] > a[i + key])
		swap(a[i], a[i + key]);

原理：

第一组代码让逆序对比较大的数组变得很小。

第二组和第三组运用了梳排序的思想，避免了乌龟。

最终，P1177时间

795ms

https://www.luogu.com.cn/record/176106393

测评网址如上

AC

完整代码

#include "bits/stdc++.h"
using namespace std;
int n, a[10000005];
main()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1 ; i <= n ; i++)
		cin >> a[i];
	for (int i = 1 ; i <= n / 2 ; i++)
		if (a[i] > a[n - i + 1])
			swap(a[i], a[n - i + 1]);
	int key = n / 3;
	for (int i = 1 ; i + key <= n ; i++)
		if (a[i] > a[i + key])
			swap(a[i], a[i + key]);
	key = n / 4;
	for (int i = 1 ; i + key <= n ; i++)
		if (a[i] > a[i + key])
			swap(a[i], a[i + key]);
	for (int i = 2 ; i <= n ; i++)
	{
		int j = i;
		while (a[j] < a[j - 1] && j > 1)
		{
			swap(a[j], a[j - 1]);
			j--;
		}
	}
	for (int i = 1 ; i <= n ; i++)
		cout << a[i] << " ";
	return 0;
}