直接折半希尔排序

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

• 前言
• 一、直接插入排序
• • 1.1、思想
  • 1.2、代码
  • 运行截图
• 二、折半插入排序
• • 2.1、代码
  • 2.2、运行截图
• 三、希尔排序
• • 3.1、基本思想
  • 3.2、希尔排序特点
  • 3.3、代码分析
  • 3.4、运行截图
• 四、代码汇总
• 总结

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

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

void DirectInsertSort(vector V){
	//如果前面的值大于后面的值就交换 
	 for(int i=1;i
	 	int cur=i;
	 	while(cur!=0&&V[cur]//向前一直交换，直到找到一个比它小的停止交换
			cout<<"此时交换的是"<
	 	cout< 
运行截图 
 
二、折半插入排序 
既然是对 直接插入排序的优化，我们通过上述我们可以看到，主要缺点是每一次只能移动一个位置，然后比较一次，但是我们划分两个部分 前部分是有序的呀，有序的我们要找它的坑位 当然可以使用折半查找，一下可以走许多步 而不是一步一步走
 
2.1、代码 
int HelfSearch(vector 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
		return HelfSearch(V,from,from+(to-from)/2,cur);
	}	
}
void HalfInsertSort(vector V){
	for(int i=1;i
		int cur=i; int oldcur=V[i];
		cout<<"此是找到的位置是"<temp){ 
			V[cur]=V[cur-1];
			cur-=1; 
		}
		V[temp]=oldcur;
	}
	for(int i=0;i
		cout< 
2.2、运行截图 
 
三、希尔排序 
这个算法难理解一点
 直接插入排序在什么情况下效率比较高？
 1、直接插入排序在基本有序时，效率较高
 2、在待排序的记录个数较少时，效率较高
 直接插入慢的原因是比较一次，移动一次，但是能不能比较一次，移动一大步
 希尔排序的思想出发点也就是基于此，
 
3.1、基本思想 
先将整个待排记录序列分割成若干个子序列，分别进行直接插入排序，待整个序列中记录"基本有序" 时，再对全体记录进行一次直接插入排序，
 分成若干子序列的原因:这样每一个部分元素个数就比较少 少不是关键 关键是若是想知道为什么时间复杂度有所提高，我们就需要知道排序的本质，排序的本质是消除逆序对， 直接插入排序与冒泡排序每一次都是比较相邻元素，所以每一次都只能消除一个逆序对 所以总的时间复杂度是N的平方 若是想突破N的平方 每一次必须要移动一大步，难道移动一大步消除的就不是一个逆序对吗？这里告诉你最少逆序对会较少一
 假设从小到大排序，简单起见设数组元素两两不等
 现在发现了a[i]>a[j]，i 若a[k] 若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 &V,int step){//其实就是插入排序  不过与之前不同的是步长不是1 
	for(int i=0;i//分成组 每一组进行一次插入排序 
		for(int j=1;j//每一组中元素的个数 用来控制 
			int cur=i+step*j;
			while(cur-step>=0&&cur//这里注意可以等于零
				cout<<"此时交换的是"<
		cout< V,vector dict){
	//按照增量序列对数组进行希尔排序 
	for(int i=0;i
		ShellInsert(V,dict[i]);
	} 
}
 
3.4、运行截图 
 
四、代码汇总 
#include
using namespace std;
void swap(int &a,int &b){
	a^=b;
	b^=a;
	a^=b;
} 

void DirectInsertSort(vector V){
	//如果前面的值大于后面的值就交换 
	 for(int i=1;i
	 	int cur=i;
	 	while(cur!=0&&V[cur]//向前一直交换，直到找到一个比它小的停止交换
			cout<<"此时交换的是"<
	 	cout< 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
		return HelfSearch(V,from,from+(to-from)/2,cur);
	}	
}
void HalfInsertSort(vector V){
	for(int i=1;i
		int cur=i; int oldcur=V[i];
		cout<<"此是找到的位置是"<temp){ 
			V[cur]=V[cur-1];
			cur-=1; 
		}
		V[temp]=oldcur;
	}
	for(int i=0;i
		cout< &V,int step){//其实就是插入排序  不过与之前不同的是步长不是1 
	for(int i=0;i//分成组 每一组进行一次插入排序 
		for(int j=1;j//每一组中元素的个数 用来控制 
			int cur=i+step*j;
			while(cur-step>=0&&cur
				cout<<"此时交换的是"<
		cout< V,vector dict){
	//按照增量序列对数组进行希尔排序 
	for(int i=0;i
		ShellInsert(V,dict[i]);
	} 
}
int main(){
	int choice;int a;
	vector V;
	cout<<"请输入你要排序的值"<>choice;
	switch(choice){
		case 1:{
			DirectInsertSort(V);
			break;
		}
		case 2:{
			HalfInsertSort(V);
			break;
		}
		case 3:{
			vector dict;
			cout<<"请输输入一个步长序列"<
			cout<<"你输入的不正确"< 
总结 
希望大家自己打一下，百看不如打一打 感觉不错点个赞呗