08-8.2.1 插入排序

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

思想

每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成

算法实现

void InsertSort(int A[], int n){
	int i, j, temp;
	for(i = 1; i < n; i ++){  // 将各元素插入已排好序的序列中
		if(A[i] < A[i-1]){  // 若A[i]关键字小于前驱
			temp = A[i];  // 用temp暂存A[i]
			for(j = i - 1; j >= 0 && A[j] > temp; -- j){  // 检查所有前面已经排好序的元素
				A[j+1] = A[j];  // 所有大于temp的元素都向后挪位
			}
			A[j+1] = temp;  // 复制到插入位置
		}
	}
}

带哨兵

void InsertSort(int A[], int n){
	int i, j;
	for(i = 2; i < n; i ++){  // 依次将A[2]~A[n]插入到前面已经排序的序列
		if(A[i] < A[i-1]){  // 若A[i]关键字小于前驱，将A[i]插入有序表
			A[0] = A[i];  // 复制为哨兵，A[0]不存放元素
			for(j = i - 1; A[0] < A[j]; -- j){  // 从后往前查找待插入位置
				A[j+1] = A[j];  // 向后挪位
			}
			A[j+1] = A[0];  // 复制到插入位置
		}
	}
}

优点：不用每轮循环都判断j >= 0
空间复杂度：$O(1)$
时间复杂度：主要来自对比关键字、移动元素，若有n各元素，则需要n-1次处理
最好时间复杂度（全部有序）：$O(n)$
最坏时间复杂度（全部逆序）：$O(n^2)$
平均时间复杂度：$O(n^2)$
算法稳定性：稳定

优化-折半插入排序

思路

先用折半查找找到应该插入的位置，再移动元素

void InsertSort(int A[], int n){
	int i, j, low, high, mid;
	for(i = 2; i <= n; i ++){  // 依次将A[2]~A[n]插入前面的已排序序列
		A[0] = A[i];  // 将A[i]暂存到A[0]
		low = 1; high = i - 1;  // 设置折半查找的范围
		while(low <= high){  // 折半查找（默认递增有序）
			mid = (low + high)/2;  // 取中间点
			if(A[mid] > A[0])
				high = mid - 1;  // 查找左半子表
			else
				low = mid + 1;  // 查找右半子表
		}
		for(j = i - 1; j >= high + 1; -- j){
			A[j+1] = A[j];  // 统一后移元素，空出插入位置
		}
		A[high+1] = A[0];  // 插入操作
	}
}