插入类排序法

直接插入排序

算法思想

将第i个记录插入到前面i-1个已排好的记录子集中。
具体：将第1个记录看做已排好的有序单元素子集，i从2到n循环进行直接插入。
直接插入排序是最简单、最基本的插入排序法。

算法描述

void InsSort(RecordType r[],int length) {
    
	int i,j;
	for(i=2; i<=length; i++) {
    
		r[0]=r[i];  j=i-1;
		while(r[0].key<r[j].key) {
    
			r[j+1]=r[j]; j=j-1; }
		r[j+1]=r[0];
	}
} /* InstSort */

算法分析

最好情况：有序
比较次数：n-1，移动次数：

希尔排序(缩小增量排序法)

算法思想

先指定一个增量，将待排序记录序列分割成若干“较稀疏”的子序列，对各子序列分别进行直接插入排序。
逐步缩小增量并继续对形成的新子序列进行直接插入排序。
最后一轮，取增量为1，即对全部记录进行一次直接插入排序。
各子序列进行直接插入排序

具体实现

一般并不是先对一个子序列进行插入排序，再对另一个子序列进行插入排序。
从第一个子序列的第二个记录开始，顺序扫描整个待排序记录序列，各子序列的记录会轮流出现，当前记录将会在属于的子序列中轮流进行插入。