基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一个对象的适当位置上，知道对象全部插入为止
基本操作：有序插入
①在有序序列中插入一个元素，保持序列有序，有序长度不断增加
②起初，a[0]是长度为1的子序列，然后，逐一将a[1]至a[n-1]插入到有序子序列中
③在插入a[i]前，数组a的前半段（a[0]~a[i-1]）是有序段，后半段（a[i]~a[n-1]）是停留于输入次序的“无序段”
④插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j（0≤j≤i），将a[i]插入在a[j]的位置上
插入排序的种类：
（1）顺序法定位插入位置——直接插入排序
①复制插入元素（x=a[i]）
②记录后移，查找插入位置 （for(j=i-1;j>=0&&x
直接插入排序算法：
void InsertSort(SqList &L){
int i,j;
for(i=2;i<=L.length;++i){
if(L.r[i].key
for(j=i-1;L.r[0].key
}
L.r[j+1]=L.r[0]; //插入到正确位置
}
}
}
实现排序的基本操作有两个：
①“比较”序列中两个关键字的大小
②“移动”记录
最好的情况（关键字在记录序列中顺序有序）：
“比较”的次数：n-1
“移动”的次数：0
最坏的情况（关键字在记录序列中逆序有序）：
“比较”的次数：(n+2)(n-1)/2
“移动”的次数：(n+4)(n-1)/2
时间复杂度结论：
①原始数据越接近有序，排序速度最快
②最坏情况下（输入数据是有逆有序）Tw(n)=O(n2)
③平均情况下，耗时差不多是最坏的一半 Te(n)=O(n2)
④要提高查找速度，减少元素的比较次数，减少元素的移动次数
（2）二分法定位插入位置——二分插入排序
算法描述：
void BInsertSort(SqList &L){
for(i=2;i<=L.length;++i){ //依次插入第2-第n个元素
L.r[0]=L.r[i]; //当前插入元素存到“哨兵”位置
low=1; high=i-1; //采用二分查找法查找插入位置
while(low<=high){
mid=(low+high)/2;
if(L.r[0].key
} //循环结束，high+1则为插入位置
for(j=i-1;j>=high+1;—j) L.r[j+1]=L.r[j]; //移动元素
L.r[high+1]=L.r[0]; 、、插入到正确位置
}
}
算法分析：
①折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快
②它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第i个对象时，需要经过[log2i]+1次关键码比较，才能确定它应插入的位置（当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差；在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少）
③折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列
（3）缩小增量多遍插入排序——希尔排序
基本思想：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
特点：
①一次移动，移动位置较大，跳跃式地接近排序后的最终位置
②最后一次只需少量移动
③增量序列必须是递减的，最后一个必须是1
④增量序列应该是互质的
算法分析：
①希尔排序算法效率与增量排序的取值有关
②希尔排序算法是一种不稳定的排序算法
若有收获，就点个赞吧
0 人点赞
