算法	时间复杂度（最好）	时间复杂度（平均）	时间复杂度（最差）	空间复杂度
插入排序	O(n）	O(n^2)	O(n^2)	1
希尔排序	O(n)	O(n^1.3)	O(n^2)	1

1.插入排序

    玩牌时，每得到一张，就要把它插入到之前的牌中，插入排序也是如此，每次都有一个有序的区间，每次都要选取无序区间的第一个元素，把他插入到合适的位置，这时，有序区间的长度+1，直到和序列长度相等为止

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, a[10000];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		int s = i;
		while (a[s] < a[s - 1] && (s > 0)) {
			swap(a[s], a[s - 1]);
			s --;
		}
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ';
	}
	return 0;
}

复杂度分析：平均情况：每个元素都要进行插入，要进行n次插入，时间复杂度为O(n*n)

最好情况：近乎有序序列，插入的时间可以忽略不计，时间复杂度：O(n) 

 2.希尔排序

    由他的发明者希尔命名，它会进行多次预排序，使其整体接近有序，每次都是插入排序里的1替换成gap，而gap先从n/2开始，以一定的规律递减，直到一。效率跟增量的序列有关。

时间复杂度：最好，最坏和插入排序一样。

为什么要这么做

        因为gap大时，每一组数据量少，效率高，gap小时，整体接近有序，效率也高。所以整体效率比插入排序高！

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a[10000],gap;
	cin>>n;
	gap=n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	while(gap>=1){
		gap*=0.6;//找不到其它序列了qwq。。。
		for(int i=0;i<=n-gap;i++){
			int s=i;
			while(a[s]<a[s-gap]&&(s-gap>=0)){
                a[s]^=a[s-gap];
                a[s-gap]^=a[s];
                a[s]^=a[s-gap];
				s-=gap;
			}
		}
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<' ';
	}
	return 0;
}