十大经典排序算法——插入排序与希尔排序(超详解)

一、插入排序

1.基本思想

直接插入排序是一种简单的插入排序法，基本思想是：把待排序的记录按其数值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

2.直接插入排序

当插入第 end + 1 个元素时，前面的arr[0]，arr[1]，...  ，arr[end]已经排好序，此时用arr[end + 1]的值与arr[end]，arr[end - 1]，... 的值进行比较，找到插入位置将arr[end + 1]插入，原来位置上的元素顺序后移。

3.图示

3.时间复杂度：

时间复杂的一般是看最坏的情况

最坏的情况—逆序，时间复杂度：O(N2" role="presentation" style="position: relative;">N2$N^2$)

最好的情况—顺序，时间复杂度为：O(N" role="presentation" style="position: relative;">N$N$)

4.直接插入排序特性总结

(1)元素集合越接近有序，直接插入排序算法的时间效率越高

(2)时间复杂度：O(N2" role="presentation" style="position: relative;">N2$N^2$)

(3)空间复杂度：O(1)，是一种稳定的排序算法

(4)稳定性：稳定 

5.参考代码

//插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{//[0,end]是有序的，end + 1位置的值插入到[0,end],保持有序
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

二、希尔排序

1.基本思想

希尔排序又称缩小增量法， 希尔排序的基本思想是：现有选定一个整数gap，把待排序的文件中所有记录分成几个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。直到gap==1时，所有记录在同一组内排好序。

2.操作

(1)预排序（让数组接近有序）

(2)插入排序 

思想：根据给出的整数gap，将数组分组，再分别对这些组进行插入排序

gap > 1 是预排序，gap == 1 是插入排序 

gap越大，大的数可以越快跳到后面，小的数可以越快跳到前面，得到的数据也越不接近有序。

gap越小，跳的越慢，也越接近有序。当gap是1，相当于插入排序。

代码实现： 两种方式

int gap = 3;
//多组并着走
for (int i = 0; i < n - gap; ++i)
{
	int end = i;
	int tmp = arr[end + gap];
	while (end >= 0)
	{
		if (tmp < arr[end])
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;
}	

int gap = 3;
//一组一组走
for (int j = 0; j < gap; j++)
{
	for (int i = 0; i < n - gap; i += gap)
	{
		int end = i;
		int tmp = arr[end + gap];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		arr[end + gap] = tmp;
	}
}

3.如何选择希尔增量

希尔排序的分析是个复杂的问题，因为它的时间是所取“增量”序列的函数，者设计一些数学上尚未接轨的难题。因此，到目前为止尚未有人求得一种最好的增量序列，但大量的研究已经得出一些局部的结论。如有人指出，当增量序列为dlta[k]=" role="presentation" style="position: relative;">dlta[k]=$dlta[k]=$ 2t−k+1−1" role="presentation" style="position: relative;">2t−k+1−1$2^{t-k+1}-1$时，希尔排序的时间复杂度为O(N32)" role="presentation" style="position: relative;">O(N32)$O(N^{\frac{3}{2}})$，其中t为排序趟数，1⩽k⩽t⩽⌊log2(n+1)⌋" role="presentation" style="position: relative;">1⩽k⩽t⩽⌊log2(n+1)⌋$1⩽k⩽t⩽\lfloor {lo{g}_2}^{(n+1)}\rfloor$。还有人在大量的实验中推出：当n在某个特定范围内，希尔排序所需的比较和移动次数越为n1.3" role="presentation" style="position: relative;">n1.3$n^{1.3}$，当n→" role="presentation" style="position: relative;">n→$n\to$∞时，可减少到n(logn)2⌊2⌋" role="presentation" style="position: relative;">n(logn)2⌊2⌋$n({lo{g}_{}}^n{)}^{2^{\lfloor 2\rfloor }}$。增量序列可以有各种取法，但需要注意：应是增量序列中的值没有除以1以外的公因子，并且最后一个增量值必须等于1。

gap的取值有多种。最初Shell提出取gap=⌊n/2⌋" role="presentation" style="position: relative;">gap=⌊n/2⌋$gap=\lfloor n/2\rfloor$，gap=⌊gap/2⌋" role="presentation" style="position: relative;">gap=⌊gap/2⌋$gap=\lfloor gap/2\rfloor$，直到gap= 1，后来Knuth提出取gap=⌊gap/3⌋+1" role="presentation" style="position: relative;">gap=⌊gap/3⌋+1$gap=\lfloor gap/3\rfloor +1$。（+1是为了保证最后一个gap的值是1） 

在Knuth所著的《计算机程序设计技巧》中，利用大量的实验统计资料得出，当n很大时，关进码平均比较次数和对象平均移动次数大约在n1.25" role="presentation" style="position: relative;">n1.25$n^{1.25}$到1.6n1.25" role="presentation" style="position: relative;">1.6n1.25$1.6n^{1.25}$范围内，这是利用直接插入排序作为子序列排序方法的情况下得到的。

4.希尔排序完整图示： 

gap = gap / 3 + 1（+1是为了保证最后一个gap的值是1） 

5.希尔排序的特性总结 

(1)希尔排序是对直接插入排序的优化

(2)当gap > 1时都是预排序，目的是让数组更接近与有序。当gap == 1时，数组已经接近有序了，这样就会很快。对整体而言，可以达到优化的效果。

(3)希尔排序的时间复杂度不好计算，因为gap的取值方式有很多种，导致难以计算。    大约是在O(N1.3" role="presentation" style="position: relative;">N1.3$N^{1.3}$)左右。

理解一下过程：

(4)稳定性：不稳定

6.代码实现 

void SellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//多组并着走
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}	
	}
}

三、排序效率对比

将插入排序，希尔排序，堆排序的运行效率进行对比

http://t.csdnimg.cn/QtpwY堆排序详解在这篇文章！

void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
 
 
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
 
 
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	
	int begin2 = clock();
	SellSort(a2, N);
	int end2 = clock();
	
	int begin4 = clock();
	HPSort(a4, N);
	int end4 = clock();
 
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("HPSort:%d\n", end4 - begin4);
 
	free(a1);
	free(a2);
	free(a3);
}
 
 
int main()
{
	int arr[] = { 9,1,2,5,7,4,6,3,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	TestOP();
	return 0;
}

上图为代码运行结果，同样是十万个随机数，插入排序相较于希尔排序和堆排序就逊色一些。