提示：男儿立志出乡关，学不成名誓不还

---

前言

这一个专题将写关于排序的一些算法
插入排序分为直接插入排序、折半插入排序、希尔排序（shell sort，后两种是在直接插入排序的改进上而来。 这篇文章主要写这三种

一、直接插入排序

1.1、思想

其实就是将数组分成两个部分，前一部分有序，后一部分无序，后一部分使用一个指针来标记，标记之前的数组都是有序的， 每一次都是从后部分无序中选取一个放在前面有序的序列中，其实就是一个比较交换的过程，假如这里是升序的，此时要插入的数 一直不停的与前面的数比较，若是比前一个小则交换，直到最后一个元素也处理好则是有序的

1.2、代码

void DirectInsertSort(vector<int> V){
	//如果前面的值大于后面的值就交换 
	 for(int i=1;i<V.size();i++){
	 	int cur=i;
	 	while(cur!=0&&V[cur]<V[cur-1]){//向前一直交换，直到找到一个比它小的停止交换
			cout<<"此时交换的是"<<V[cur]<<"yu"<<V[cur-1]<<endl; 
			swap(V[cur],V[cur-1]);
			cur-=1;	 
		}
	 } 
	 for(int i=0;i<V.size();i++){
	 	cout<<V[i]<<" ";
	 }
	 cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

运行截图

二、折半插入排序

既然是对 直接插入排序的优化，我们通过上述我们可以看到，主要缺点是每一次只能移动一个位置，然后比较一次，但是我们划分两个部分 前部分是有序的呀，有序的我们要找它的坑位 当然可以使用折半查找，一下可以走许多步 而不是一步一步走

2.1、代码

int HelfSearch(vector<int> V,int from,int to,int cur){
	if(to==from){
		return from;
	}
	if(cur>V[(from+to)/2]){
		 return HelfSearch(V,from+(to-from)/2+1,to,cur);
	}
	else if(cur<V[(from+to)/2]){
		return HelfSearch(V,from,from+(to-from)/2,cur);
	}	
}
void HalfInsertSort(vector<int> V){
	for(int i=1;i<V.size();i++){
		int cur=i; int oldcur=V[i];
		cout<<"此是找到的位置是"<<HelfSearch(V,0,i,cur)<<endl; 
		int temp=HelfSearch(V,0,i,V[i]);
		//数组从temp位置向后移动向后移动一个位置 将temp这个位置空出来 
		while(cur>temp){ 
			V[cur]=V[cur-1];
			cur-=1; 
		}
		V[temp]=oldcur;
	}
	for(int i=0;i<V.size();i++){
		cout<<V[i]<<" "; 
	} ![请添加图片描述](https://img-blog.csdnimg.cn/df1f4b6a3d6f4b9cbaf53c0deb62aadc.png)

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.2、运行截图

三、希尔排序

这个算法难理解一点
直接插入排序在什么情况下效率比较高？
1、直接插入排序在基本有序时，效率较高
2、在待排序的记录个数较少时，效率较高
直接插入慢的原因是比较一次，移动一次，但是能不能比较一次，移动一大步
希尔排序的思想出发点也就是基于此，

3.1、基本思想

先将整个待排记录序列分割成若干个子序列，分别进行直接插入排序，待整个序列中记录"基本有序" 时，再对全体记录进行一次直接插入排序，
分成若干子序列的原因:这样每一个部分元素个数就比较少 少不是关键 关键是若是想知道为什么时间复杂度有所提高，我们就需要知道排序的本质，排序的本质是消除逆序对， 直接插入排序与冒泡排序每一次都是比较相邻元素，所以每一次都只能消除一个逆序对 所以总的时间复杂度是N的平方 若是想突破N的平方 每一次必须要移动一大步，难道移动一大步消除的就不是一个逆序对吗？这里告诉你最少逆序对会较少一
假设从小到大排序，简单起见设数组元素两两不等
现在发现了a[i]>a[j]，i<j，考虑下标闭区间[i,j]这个范围的j-i+1个元素，对任意i<k<j，考虑a[k]
若a[k]<a[j]，交换a[i]和a[j]后，三者的逆序数从2变为1（例如3 1 2变成2 1 3）
若a[k]>a[i]，交换a[j]和a[i]后，三者的逆序数从2变为1（例如2 3 1变成1 3 2）
若a[i]>a[k]>a[j]，交换a[i]和a[j]后，三者的逆序数从3变为0（例如3 2 1变成1 2 3）

说完上述理论 你可能还是不懂为什么逆序对会最少减少一 或者可以这样理解 每一次分组之后组中的值的交换，都更加接近这个值最终应该待的位置，不是一步一步的接近它应该待的位置，所以逆序减少最少是为一，因为完全有序的逆序对是0

3.2、希尔排序特点

1、一次移动，移动位置较大，跳跃式的接近排序后的最终位置
2、最后一次只需要少量移动
3、增量序列必须是递减的，最后一个必须是1
4、增量序列应该是互质的

3.3、代码分析

首先我们需要一个增量序列 ，每一次遍历增量序列中的每一个值 注意外面需要多一层循环，因为将数据分成了step组 内层每一组的元素个数 处理的形式跟上面的插入几乎相同

void ShellInsert(vector<int> &V,int step){//其实就是插入排序  不过与之前不同的是步长不是1 
	for(int i=0;i<step;i++){//分成组 每一组进行一次插入排序 
		for(int j=1;j<V.size()/step+1;j++){//每一组中元素的个数 用来控制 
			int cur=i+step*j;
			while(cur-step>=0&&cur<V.size()&&V[cur]<V[cur-step]){//这里注意可以等于零
				cout<<"此时交换的是"<<V[cur]<<"与"<<V[cur-step]<<endl; 
				swap(V[cur],V[cur-step]);
				cur=cur-step;
			}	
		}
	} 
	cout<<"此时序列是"<<endl;
	for(int i=0;i<V.size();i++){
		cout<<V[i]<<" "; 
	} 
	cout<<endl;
}
void ShellSort(vector<int> V,vector<int> dict){
	//按照增量序列对数组进行希尔排序 
	for(int i=0;i<dict.size();i++){
		ShellInsert(V,dict[i]);
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.4、运行截图

四、代码汇总

#include<bits/stdc++.h>
using namespace std;
void swap(int &a,int &b){
	a^=b;
	b^=a;
	a^=b;
} 

void DirectInsertSort(vector<int> V){
	//如果前面的值大于后面的值就交换 
	 for(int i=1;i<V.size();i++){
	 	int cur=i;
	 	while(cur!=0&&V[cur]<V[cur-1]){//向前一直交换，直到找到一个比它小的停止交换
			cout<<"此时交换的是"<<V[cur]<<"yu"<<V[cur-1]<<endl; 
			swap(V[cur],V[cur-1]);
			cur-=1;	 
		}
	 } 
	 for(int i=0;i<V.size();i++){
	 	cout<<V[i]<<" ";
	 }
	 cout<<endl;
}
int HelfSearch(vector<int> V,int from,int to,int cur){
	if(to==from){
		return from;
	}
	if(cur>V[(from+to)/2]){
		 return HelfSearch(V,from+(to-from)/2+1,to,cur);
	}
	else if(cur<V[(from+to)/2]){
		return HelfSearch(V,from,from+(to-from)/2,cur);
	}	
}
void HalfInsertSort(vector<int> V){
	for(int i=1;i<V.size();i++){
		int cur=i; int oldcur=V[i];
		cout<<"此是找到的位置是"<<HelfSearch(V,0,i,cur)<<endl; 
		int temp=HelfSearch(V,0,i,V[i]);
		//数组从temp位置向后移动向后移动一个位置 将temp这个位置空出来 
		while(cur>temp){ 
			V[cur]=V[cur-1];
			cur-=1; 
		}
		V[temp]=oldcur;
	}
	for(int i=0;i<V.size();i++){
		cout<<V[i]<<" "; 
	} 
}
void ShellInsert(vector<int> &V,int step){//其实就是插入排序  不过与之前不同的是步长不是1 
	for(int i=0;i<step;i++){//分成组 每一组进行一次插入排序 
		for(int j=1;j<V.size()/step+1;j++){//每一组中元素的个数 用来控制 
			int cur=i+step*j;
			while(cur-step>=0&&cur<V.size()&&V[cur]<V[cur-step]){
				cout<<"此时交换的是"<<V[cur]<<"与"<<V[cur-step]<<endl; 
				swap(V[cur],V[cur-step]);
				cur=cur-step;
			}	
		}
	} 
	cout<<"此时序列是"<<endl;
	for(int i=0;i<V.size();i++){
		cout<<V[i]<<" "; 
	} 
	cout<<endl;
}
void ShellSort(vector<int> V,vector<int> dict){
	//按照增量序列对数组进行希尔排序 
	for(int i=0;i<dict.size();i++){
		ShellInsert(V,dict[i]);
	} 
}
int main(){
	int choice;int a;
	vector<int> V;
	cout<<"请输入你要排序的值"<<endl;
	while(scanf("%d",&a)!=EOF) V.push_back(a);
	cout<<"请选择你要进行时的排序方式"<<endl;
	cout<<"1、直接插入排序"<<endl;
	cout<<"2、折半插入排序"<<endl;
	cout<<"3、希尔排序"<<endl; 
	cin>>choice;
	switch(choice){
		case 1:{
			DirectInsertSort(V);
			break;
		}
		case 2:{
			HalfInsertSort(V);
			break;
		}
		case 3:{
			vector<int> dict;
			cout<<"请输输入一个步长序列"<<endl;
			while(scanf("%d",&a)!=EOF) dict.push_back(a);
			ShellSort(V,dict);	
			break;
		}
		default:{
			cout<<"你输入的不正确"<<endl;
			break;
		}
	}
	
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

总结

希望大家自己打一下，百看不如打一打 感觉不错点个赞呗