20-数据结构-内部排序-插入排序

简介：插入排序基本有两步，先是通过比较，得到插入位置，随后移动给需要插入的位置处腾空，最后进行值的插入。

目录

一、直接插入排序

1.1简介：

1.2代码

二、折半插入排序

2.1简介：

2.2代码：

三、希尔排序

3.1简介：

3.2.代码：

四、总代码

一、直接插入排序

1.1简介：

        直接插入排序，主要两步，先找到需要插入的位置，随后进行移动，给位置腾空，最后赋值。其主要思想都在注释里，

        直接插入排序适合：顺序存储和链式存储

        稳定性：稳定，因为是根据位置直接插入的，所以前后位置不会变。（口令：稳稳的幸福，鸡毛插龟壳-（基数排序，冒泡排序，直接插入和折半插入，归并排序））

        时间复杂度：最好的情况为O(n),已经排好序列了，最坏情况为O(),从头到尾每一个数都需要移动判断，

        空间复杂度：O(1)

1.2代码

void InsertSort(int *a,int n)
{
	//传进数组和实际数据个数 
	int i,j;
	for(i=2;i<=n;++i)
	{
		//查找实际需要插入的位置i 
		if(a[i]<a[i-1])//因为按照递增顺序排，因此发现后面比前面小的情况就需要排序否则跳过，换下一个数据判断 
		{
			a[0]=a[i];//哨兵处放实际需要排的值，方便后面比较 
			
			for(j=i-1;a[j]>a[0];--j)//因为需要插入数据进行排序，因此需要从后往前后移，给插入的位置腾空移位置 
			{
				//给需要存放位置前的位置处，往后移动，腾空位置，当j所指的数据小于等于哨兵时，给哨兵处的值放在j+1位置处即可 
				a[j+1]=a[j];
			}
			//给数据插进腾空的地方。 
			a[j+1]=a[0];
		}
	}
}

二、折半插入排序

2.1简介：

        折半插入是对直接插入的优化，减少了关键字对比的次数，但时间复杂度和空间复杂度和一直插入一样，移动次数没有改变，仅仅减少比较次数，比较次数取决于表中元素n。

        折半插入排序思想是，从第二个元素开始折半查找进行判断，找到该元素需要插入的位置，随后，进行折半查找，最后折半查找结束后low和high紧挨着互换左右位置，low处为需要插入的位置，随后进行移动，把low处及其后面的都往后移动，最后给a[low]=a[0]，赋值即可。

2.2代码：

void InsertHalfSort(int *a,int n)
{
	int i,j,low,high,mid;
	//对数组进行排序，先用折半法，查找位置 
	for(i=2;i<=n;i++)
	{
		a[0]=a[i];//从第二个数据开始判断比较 
		low=1;
		high=i-1;
		while(low<=high)//查找区间，最后查找完成后low和high左右挨着互换，high+1即low位置处为需要插入的地方 
		{
			mid=(low+high)/2;
			if(a[mid]<a[0])
				low=mid+1;
			else
				high=mid-1;
		}
		//折半后，此时low及其之后的数据都是比high处大的，而low位置处为需要插入的地方，因此需要给low机器后面的地方进行后移，给low处数据弄空 
		for(j=i-1;j>=low;--j)
		{
			a[j+1]=a[j];
		}
		a[low]=a[0];
	}
}

三、希尔排序

3.1简介：

        希尔不同于直接插入和折半，而是给表分割成无数子表，一趟一趟分割，合并，每一次分割的子表之间进行判断，以及排序移动，最后一趟趟汇总。每趟子表下标为i,i+d

空间复杂度仍未O(1)

时间复杂度为O(),坏的情况下是O()

稳定性：不稳定

适用性：仅适合于顺序存储。需要随机访问支持才行。

3.2.代码：

void ShellSort(int *a,int n)
{
	int i,j,d;
	//d为每次增量，随后d每次/2 
	for(d=n/2;d>=1;d=d/2) //d增量的趟次 
	{
		//开始比较， 从第一趟中，第一个比较队中来说，都是从比较队中第二个数据开始与前面的对比，前面的是i-d 
		for(i=d+1;i<=n;i++)//第一个比较队完成后，i++，进行第二个比较队 
		{
			if(a[i]<a[i-d])//按递增比较的话，如果后面的比前面的小，那么异常进行记录和交换 
			{
				a[0]=a[i];
				for(j=i-d; j>=0&&a[j]>a[0] ;j=j-d) //随后从队中第一个数据开始，往后移动，移动到它的下一位j+d处。判断条件为j大于0，且当前的值比移动的值大时，进行数据的后移 
				{
				a[j+d]=a[j];	
				}
				//移动完毕，进行赋值，此时两两交换完成 
				a[j+d]=a[0];
			}				
		}	
	}	
	
} 

四、总代码

#include <stdio.h>
//插入排序——直接插入排序
void InsertSort(int *a,int n)
{
	//传进数组和实际数据个数 
	int i,j;
	for(i=2;i<=n;++i)
	{
		//查找实际需要插入的位置i 
		if(a[i]<a[i-1])//因为按照递增顺序排，因此发现后面比前面小的情况就需要排序否则跳过，换下一个数据判断 
		{
			a[0]=a[i];//哨兵处放实际需要排的值，方便后面比较 
			
			for(j=i-1;a[j]>a[0];--j)//因为需要插入数据进行排序，因此需要从后往前后移，给插入的位置腾空移位置 
			{
				//给需要存放位置前的位置处，往后移动，腾空位置，当j所指的数据小于等于哨兵时，给哨兵处的值放在j+1位置处即可 
				a[j+1]=a[j];
			}
			//给数据插进腾空的地方。 
			a[j+1]=a[0];
		}
	}
}
//插入排序——折半插入
void InsertHalfSort(int *a,int n)
{
	int i,j,low,high,mid;
	//对数组进行排序，先用折半法，查找位置 
	for(i=2;i<=n;i++)
	{
		a[0]=a[i];//从第二个数据开始判断比较 
		low=1;
		high=i-1;
		while(low<=high)//查找区间，最后查找完成后low和high左右挨着互换，high+1即low位置处为需要插入的地方 
		{
			mid=(low+high)/2;
			if(a[mid]<a[0])
				low=mid+1;
			else
				high=mid-1;
		}
		//折半后，此时low及其之后的数据都是比high处大的，而low位置处为需要插入的地方，因此需要给low机器后面的地方进行后移，给low处数据弄空 
		for(j=i-1;j>=low;--j)
		{
			a[j+1]=a[j];
		}
		a[low]=a[0];
	}
}
//插入排序——希尔排序：
void ShellSort(int *a,int n)
{
	int i,j,d;
	//d为每次增量，随后d每次/2 
	for(d=n/2;d>=1;d=d/2) //d增量的趟次 
	{
		//开始比较， 从第一趟中，第一个比较队中来说，都是从比较队中第二个数据开始与前面的对比，前面的是i-d 
		for(i=d+1;i<=n;i++)//第一个比较队完成后，i++，进行第二个比较队 
		{
			if(a[i]<a[i-d])//按递增比较的话，如果后面的比前面的小，那么异常进行记录和交换 
			{
				a[0]=a[i];
				for(j=i-d; j>=0&&a[j]>a[0] ;j=j-d) //随后从队中第一个数据开始，往后移动，移动到它的下一位j+d处。判断条件为j大于0，且当前的值比移动的值大时，进行数据的后移 
				{
				a[j+d]=a[j];	
				}
				//移动完毕，进行赋值，此时两两交换完成 
				a[j+d]=a[0];
			}				
		}	
	}	
	
} 
 
//打印
void PrintSort(int *a,int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%d ",a[i]);	
	}	
	printf("\n"); 
} 
 
int main()
{
    int a[9]={0,49,38,65,97,76,13,27};
    int size=7;
    printf("开始值\n");
    PrintSort(a,size);
    //插入6进去
    int x;
	printf("请输入插入的值\n"); 
	scanf("%d",&x); 
	a[size+1]=x; 
	size++;
	printf("\插入后排序\n");
//	InsertSort(a,size);//直接插入排序 
//	InsertHalfSort(a,size);//折半插入排序 
	ShellSort(a,size);//希尔排序 
	PrintSort(a,size);
 }