数据结构(8.2_1)——插入排序

插入排序

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

代码实现

#include <stdio.h>

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;//复制到插入位置
	}
}

代码实现 (带哨兵)

#include <stdio.h>

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];//复制到插入位置
	}
}

算法效率分析

空间复杂度：O(1)

时间复杂度:主要来自对比关键字，移动元素，若有n个元素，则需要n-1趟处理

最好情况：共n-1趟处理，每一趟只需要对比关键字1次，不用移动元素———O(n)

最坏情况：

第1趟：对比关键字2次，移动元素3次

第2趟：对比关键字3次，移动元素4次

...

第i趟：对比关键字i+1次，移动元素i+2次———O(n^2)

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

优化——折半插入排序

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

先将low指针和high指针相加除二得出mid指针

对比关键字key和数组[mid]哪个大

若数组[mid]>key，则low=mid+1；

若数组[mid]<key,则high=mid-1;

当high<low时，折半查找停止，将[low，i-1]内的元素全部右移，并将A[0]复制到low所指位置

注意：折半查找只能用于顺序列表

代码实现

	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])
					hith = mid - 1;//查找左半子表
				else
					low = mid - 1;//查找右半子表
		}
			for (j = i - 1; A[0] < A[j]; --j)//从后往前查找待插入位置
				A[j + 1] = A[j];//向后挪
			A[j + 1] = A[0];//复制到插入位置
			}
		}