排序算法--插入排序

 

       排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 我们这里的排序是内部排序。

        所谓排序，就是要整理表中的记录，使之按关键字递增(或递减)有序排列，当排序的关键字都不相同时，排序结果是唯一的。本篇博客介绍插入排序。 

        插入排序的基本思想是：每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。主要介绍直接插入排序，二分插入排序，希尔排序

 

1.直接插入排序

 

基本思路

 

      每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。假设待排序的记录存放在数组R[0..n]中。初始时，R[0]自成1个 有序区，无序区为R[1..n]。从i=1起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

 

实现代码

void InsertSort(int a[],int len)//递增排列
{
	int temp;
	for(int i=1;i<len;i++)//a[0]在有序区,需要依次把a[1...len-1]插入到有序区
	{
		temp=a[i];
		int j=i-1;//从有序区间最右边对比插入
		while(j>=0&&temp<a[j])
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;
	}

	//输出结果
	for(int i=0;i<len;i++)
		cout<<a[i]<<"  ";
}

 

效率分析

       直接插入排序所耗费的时间是有很大差异的。最好情况是表初态为正序，此时算法的时间复杂度为O(n),最坏情况是表的初态为反序，此时的时间复杂度为 O(n^2)。算法的平均时间复杂度也是O(n^2)。直接插入排序算法只使用了几个辅助变量，与问题n无关，即辅助空间复杂度为O(1)，也就是说它是 一个就地排序。

 

2.二分插入排序

 

基本思想

     是在上面直接插入排序的方法上在比较大小时用上前面说的二分查找。即在数据表中有一个元素序列v[0],v[1],v[2]......v[n].其中v[0],v[1],v[2]......v[i-1]是已经排好序的元素。在插入v[i]。利用折半搜索寻找v[i]的插入位置。

 

实现代码

//二分插入排序
void InsertSort1(int a[],int len)//递增排列
{
	int temp,low,high,mid;
	for(int i=1;i<len;i++)//a[0]在有序区,需要依次把a[1...len-1]插入到有序区
	{
		temp=a[i];
		low=0;high=i-1;
		while(low<=high)//在a[low....high]中二分查找有序插入的位置
		{
			mid=(low+high)/2;
			if(temp<a[mid])
				high=mid-1;
			else
				low=mid+1;
		}
		for(int j=i-1;j>=high+1;j--)
			a[j+1]=a[j];
		a[high+1]=temp;

	

	}
}

 

效率分析

     二分插入排序的空间复杂度为O(1)。二分插入排序只是减少了关键字的比较次数，而记录的移动次数不变。因此，时间复杂度仍为O(n^2)。

 

3.希尔排序

 

基本思想

         先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

 

具体步骤

        先取定一个小于n(数组的长度)的整数d1作为第一个增量，把表的全部记录分成d1个组，所有距离为d1

的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第二个增量d2(d2<d1)，重复上面步骤，直至所取的增量为d=1(di<di+i),，即所有记录放在同一组中进行直接插入排序。

 

例如：

 

实现代码

    我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数。

void ShellSort(int a[],int len)
{
	int gap,temp,j;
	gap=len/2;//增量初始值

	while(gap>0)
	{
                //---把gap当1，即相当直接排序代码
		for(int i=gap;i<len;i++)//对相隔增量gap位置的所有元素直接插入排序
		{
			temp=a[i];
			j=i-gap;
			while(j>=0&&temp<a[j])//对相隔gap的元素进行排序
			{
				a[j+gap]=a[j];
				j=j-gap;

			}
			a[j+gap]=temp;
			j=j-gap;
		}
		gap=gap/2;
	}

}

 

效率分析

    希尔排序的性能分析是一个复杂的问题，与增量有关，一般认为其平均时间复杂度为O(n^1.3)。希尔排序一般要比直接插入排序快。希尔排序算法也只是使用了几个辅助变量，与问题n无关，所以辅助空间复杂度为O(1)，也是就地排序。

     然而，希尔排序是一种不稳定的排序。因为两个元素相等时，希尔排序可能会改变它们两的位置，所以是不稳定排序
 

 

最后附上源码地址：https://github.com/longpo/algorithm/tree/master/InsertSort