随笔,排序——插入排序

插入排序

基本思想

  • 每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。即边插入边排序,保证子序列中随时都是排好序的

基本步骤:

  1. 在R1..i-1中查找Ri的插入位置;
    R1..j.key <= Ri.key < Rj+1..i-1.keyundefined直接插入排序(基于顺序查找)排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。
  2. 将Rj+1..i-1中的所有记录均后移一个位置;
  3. 将Ri 插入(复制)到Rj+1的位置上。

在这里插入图片描述

算法描述

  • 从Ri-1向前进行顺序查找,监视哨设置在R0
  • 关键字大于Ri.key的记录向后移动
    if( L.ri.key<L.ri-1.key){
    R0 = Ri; // 设置“哨兵”
    Ri = Ri-1;
    for (j=i-2; R0.key<Rj.key; –j)undefined Rj+1 = Rj;
  • 循环结束表明Ri的插入位置为 j+1
    L.rj+1=L.r0; //插入到正确位置

算法实现

void InsertSort(SqList &L){
	int i, j;
	for(i = 2; i <= L.length; ++i){
		if(L.r[i].key < L.r[i - 1].key){
			// 将L.r[i]插入有序子表
			L.r[0] = L.r[i];  // 复制为哨兵
			L.r[i] = L.r[i - 1];
			for(j = i - 2; L.r[0].key < L.r[j].key; --j)
				L.r[j + 1] = L.r[j];  // 记录后移
			L.r[i + 1] = L.r[0];  // 插入到正确位置
		}
	}
}

算法分析

时间复杂度 —— O(n^2)

  • 最好的情况(关键字正序)
    – 比较次数:

    在这里插入图片描述

    – 移动次数:

    在这里插入图片描述
  • 最坏情况下(关键字逆序)
    – 第 i 趟比较i次,移动i+1次
    – 比较次数:

    在这里插入图片描述

    – 移动次数:

    在这里插入图片描述

平均时间复杂度:O(n^2)

空间复杂度 —— O(1)

  • 需要一个记录的辅助空间r(0)

稳定性

  • 稳定

特点:简单、容易实现,适用于待排序记录基本有序或待排序记录较小时


折半插入排序(基于折半查找)

基本思想:因为 R1..i-1 是一个按关键字有序的有序序列,则可以利用折半查找实现“在R1..i-1中查找Ri的插入位置”,如此实现的插入排序为折半插入排序。

算法实现

void BiInsertionSort(SqList &L){
	for(i = 2; i <= L.length; ++i){
		L.r[0] = L.r[i];  // 将L.r[i] 暂存到 r[0]
		// 在 L.r[1..i-1]中折半查找插入位置
		low = 1;
		high = i - 1;
		while(low <= high){
			m = (low + high) / 2;  // 折半
			if(L.r[0].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[0];
	}
}

算法分析

  • 时间复杂度为 O(n^2)
    最佳情况下总时间代价为O(nlog2n)
    最差和平均情况下仍为O(n^2)
  • 空间复杂度为 O(1)
  • 是一种稳定的排序方法
正文完