2.插入排序

插入排序

---

00:02

基本思想是每次将一个待排序的记录按其关键字大小插入前面己排好序的子序列,直到全部记录插入完成

直接插入排序

假定初始序列为 $49,38,65,97,76,13,27, \overline{49}$, 初始时 49 可以视为一个已排好序的子序列, 按照上述算法进行直接插入排序的过程如图 8.1 所示, 括号内是已排好序的子序列。

image.png

• 空间复杂度$O(1)$
• 时间复杂度:最好为$O(n)$,最坏为$O(n^2)$
• 是稳定排序
• 适用于顺序存储和链式存储的线性表。

提示

在最好情况下,表中元素己经有序,此时每插入一个元素,都只需比较一次而不用移动元素

void InsertSort(ElemType A[],int n){
	int i, j;
	for(i=2; i < n; i++){
		A[0] = A[i];
		if(A[i] < A[i-1]){
			for(j = i-1; A[0] < A[j]; --j){
				A[j+1] = A[j];
			}
			A[j+1] = A[0];
		}
	}
}

折半插入排序

当排序表为顺序表时, 可以对直接插入排序算法做如下改进:由于是顺序存储的线性表,所以查找有序子表时可以用折半查找来实现。确定待插入位置后,就可统一地向后移动元素。

折半插入排序仅减少了比较元素的次数, 约为 $O\left(n \log _{2} n\right)$, 该比较次 数与待排序表的初始状态无关, 仅取决于表中的元素个数 $n$; 而元素的移动次数并未改变, 它依赖于待排序表的初始状态。因此, 折半插入排序的时间复杂度仍为 $O\left(n^{2}\right)$, 但对于数据量不很大 的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

当 low>high 时折半查找停止，应将 [low,i-1]内的元素全部右移，并将 A[O] 复制到 low 所指位置
当 A[mid]==A[0]时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插入位置(应继续令low=mid+1)，最终应将当前元素插入到low所指位置（即high+1）

void InsertSort(ElemType A[],int n){
	int i,j,low,high,mid;
	for(i = 2;i <= n; i++){ //依次将A[2]~A[n]插入前面的已排序序列
		A[0] = A[1];
		low = 1;
		high = i-1;
		while(low <= high)
	}
}

希尔排序

8.2.3希尔排序

---

00:00

希尔排序的基本思想是：先将待排序表分割成若干形如 $L[i, i+d, i+2 d, \cdots, i+k d]$ 的 “特殊” 子表, 即把相隔某个 “增量” 的记录组成一个子表, 对各个子表分别进行直接插入排序, 当整个 表中的元素已呈 “基本有序” 时, 再对全体记录进行一次直接插入排序。

实例

取$d_1=5,d_2=3$,则:

image.png

• 若待排序列为 “正序”时, 其时间效率可提高至$O(n)$，更适用于基本有序的排序表和数据量不大的排序表
• 空间复杂度$O(1)$
• 时间效率：当n在某个特定范围时,希尔排序的时间复杂度约为 $O(n^{1.3})$,在最坏情况下希尔排序的时间复杂度为$O(n^2)$^[1]
• 是一种不稳定的排序方法
• 仅适用于线性表为顺序存储的情況

---

1. 希尔排序的时间复杂度依赖于增量序列的函数,这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难 ↩︎