直接插入排序

Posted on | Post modified: | In
Words count in article: 612 | Reading time ≈ 2

-直接插入排序算法简介
-直接插入排序算法分析

插入排序

插入排序是一种简单直观的排序方法，其基本思想在于每次将一个待排序的记录，按其关键字大小插入到前面已经排序的子序列中，知道全部记录插入完成。

直接插入排序
为了实现将元素L(i)插入到已有序的子序列L[1…i-1]，需要执行以下操作：
1.查找出L(i)在L[1…i-1]中的插入位置k
2.将L[k…i-1]中所有元素全部后移一个位置
3.将L[i]复制到L[k]

为了实现排序，将L(2)~L(n)依次插入到前面已排好序的子序列中，初始假定L[1]是一个已排好序的子序列。

1
2
3
4
5
6
7
8
9
10
void InsertSort(ElemType A[],int n){
//直接插入排序算法
	int i,j;
	for(i=2;i<=n;i++)             //依次将A[2]~A[n]插入到前面已排序序列
		if(A[i].key<A[i-1].key){  //若A[i]的关键码小于其前驱，需将A[i]插入到有序表
			A[0]=A[i];            //复制为哨兵
			for(j=i-1;A[0].key<A[j].key;--j)  //从后往前查找待插入位置
				A[j+1]=A[j];      //复制到插入位置
	}
}

性能分析
空间效率：使用了常数个辅助单元，空间复杂度为O（1）
时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
在最好的情况下，表中元素已经有序，每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O（n）
在最坏的情况下，表中顺序刚好与排序结果中元素顺序相反时，总的比较次数达到最大，为2+3+…+n，总的移动次数也达到最大，3+4+…+n+1.
平均情况下，考虑待排序表中的元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与移动次数约为n2/4.

由此，直接插入排序算法的时间复杂度为O（n2）

Thanks for your reward！