基本思想

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入位置。

即边插入边排序，保证子序列中随时都是排好序的。

基本操作：有序插入

• 在有序序列中插入一个元素，保持序列有序，有序长度不断增加。
• 起初，a[0]是长度为1的子序列。然后，逐一将a[1]至a[n-1]插入到有序子序列中。

有序插入方法：
① 在插入a[i]前，数组a的前半段（a[0] - a[i-1]）是有序段，后半段（a[i] - a[n-1]）是停留于输入次序的“无序段”。
② 插入a[i]使a[0] - a[i-1] 有序，也就是要为a[i]找到有序位置j（0≤ j ≤ i），将a[i]插入在a[j]的位置上。

插入图示

如何找到插入位置 j 呢？

插入排序的种类

顺序法定位插入位置——直接插入排序
二分法定位插入位置——二分插入排序
缩小增量多遍插入排序——希尔排序

直接插入排序

直接插入排序——采用顺序查找法查找插入位置。

排序过程

1.复制插入元素

x = a[i];
1

2.记录后移，查找插入位置

for(j=i-1;j>=0&&x<a[j];j--)
	a[j+1]=a[j];
1
2

3.插入到正确位置

a[j-1]=x;
1

具体实现

void InsertSort(SqList &L) 
{	//对顺序表L做直接插入排序
	for(i=2;i<=L.length;++i) 
		if(L.r[i].key<L.r[i-1].key) 	// “<”，需将r[i]插入有序子表
		{
			L.r[O]=L.r[i]; 				// 将待插人的记录暂存到监视哨中
			L.r[i]=L.r[i-1]; 			// r[i-1]后移
			for(j=i-2; L.r[O].key<L.r[j].key; --j)	// 从后向前寻找插入位置
				L.r[j+1]=L.r[j];		// 记录逐个后移，直到找到插入位置
			L.r[j+1]=L.r[O];			// 将 r[O]即原r[i]，插人到正确位置
		}
}
//if
1
2
3
4
5
6
7
8
9
10
11
12
13

插入排序性能分析

实现排序的基本操作有两个：
（1）“比较”序列中两个关键字的大小；
（2）“移动”记录。

最好的情况（关键字在记录序列中顺序有序）：
11 25 32 47 56 70 81 85 92 96

最坏的情况（关键字在记录序列中逆序有序）：
81 85 92 96 70 56 47 32 25 11

平均情况：

时间复杂度结论

• 原始数据越接近有序，排序速度越快
• 最坏情况下（输入数据是逆有序的）Tw(n) = O(n²)
• 平均情况下，耗时差不多是最坏情况的一半 Te(n) = O(n²)
• 要提高查找速度，就要减少元素的比较次数、减少元素的移动次数

折半插入排序

查找插入位置时采用折半查找法。

具体实现

void BinsertSort(SqList &L) 
{	// 对顺序表L做折半插入排序
	for (i=2; i < =L.length; ++i) 
	{
		L.r[O]=L.r[i];			// 将待插人的记录暂存到监视哨中
		low=1;high=i-1; 		// 置查找区间初值
		while(low<=high)		// 在r[low .. high]中折半查找插入的位置
		{
			m=(low+high)/2; 	// 折半
			if(L.r[O].key<L.r[m].key) high=m-1; 		// 插入点在前一子表
			else low=m+1; 		// 插入点在后一子表
		}
		for (j=i-1;j>=high+1; --j) L.r[j+1]=L.r[j]; 	//记录后移
		L.r[high+1]=L.r[O]; 	// 将r[O]即原r[i], 插入到正确位置
	}							// for
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

折半插入排序算法分析

• 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快；
• 它所需要的关键码比较次数与待排序对象序列的初始排序无关，仅依赖于对象个数。在插入第i个对象时，需要经过log₂i +1次关键码比较，才能确定它应插入的位置；
  • 当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其好情况要差；
  • 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少；
• 折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列
  • 减少了比较次数，但没有减少移动次数
  • 平均性能优于直接插入排序

时间复杂度为O(n²)
空间复杂度为O(1)
是一种稳定的排序方法

希尔排序（Donald.L.Shell）

直接、折半插入排序的思考

可以在直接、折半插入排序时增大移动的步幅吗？
由原来的比较一次移动一步，变成比较一次移动一大步？

直接插入排序， 当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从 “减少记录个数” 和 “序列基本有序” 两个方面对直接插入排序进行了改进。

希尔排序基本思想

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

希尔排序算法特点

（1）缩小增量
（2）多遍插入排序

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

希尔排序过程

具体实现

void ShellInsert(SqList &L, int dk) 
{	// 对顺序表L做一趟增量是dk的希尔插入排序
	for(i=dk+1;i<=L.length;++i) 
		if(L.r[i].key<L.r[i-dk].key) 		// 需将L.r[i]插入有序增扯子表
		{
			L.r[O]=L.r[i];					// 暂存在L.r[O]
			for(j=i-dk; j >O&& L.r[O].key<L.r[j].key;j-=dk)
				L.r[j+dk]=L.r[j]; 			// 记录后移， 直到找到插入位置
			L.r[j+dk]=L.r[O]; 				// 将 r[O]即原r[i], 插入到正确位置
		}
}

void ShellSort(SqList &L,int dt[],int t) 
{	//按增批序列 dt[O .. t-1]对顺序表 L作t 趟希尔排序
	for (k=O;k<t;++k) 
		ShellInsert(L,dt[k]); 				// 一趟增址为 dt[t]的希尔插入排序
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

希尔排序算法分析

希尔排序算法效率与增量序列的取值有关

时间复杂度是n和d的函数：
O(n^1.25) - O(1.6n^1.25) ——经验公式

空间复杂度为O(1)

是一种不稳定的排序方法

如何选择最佳d序列，目前尚未解决；
最后一个增量值必须为1，无除了1之外的公因子；
不宜在链式存储结构上实现。

希尔排序算法特点

(1) 记录跳跃式地移动导致排序方法是不稳定的。
(2) 只能用于顺序结构，不能用于链式结构。
(3) 增量序列可以有各种取法，但应该使增量序列中的值没有除1 之外的公因子，并且最后一个增量值必须等于1。
(4) 记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合初始记录无序、n较大时的情况。