本文共 597 字，大约阅读时间需要 1 分钟。

insertsort

算法思想：将待排序的记录按大小插入已经排序好的子序列中

算法分析： 时间复杂度O（n^2） 空间复杂度O（1） 稳定的算法 适用于顺序存储和链式存储的线性表 特点：可以提前终止循环，在数据基本有序时效率很高 应用：在复杂排序中作为一个子过程 来优化

void InsertSort(elemtype *a,int n){//逆序	for(int i=1;i
   
    0&&a[j]>a[j-1];j--){//简洁写法 		int temp = a[j-1];			a[j-1] = a[j];			a[j] = temp;	}}
   

部分过程图示

5>2交换位置，j从开始递减直到1

12>2，交换位置，j– 12>5,交换位置 改进插入算法 添加哨兵，每次比较不交换位置，而是向后赋值，将哨兵保存的元素插入合适的位置 主要改进点：赋值次数减少了，（因为交换需要赋值三次）

void BetterInsertSort(elemtype *a,int n){	for(int i=1;i
   
    0&&a[j-1]
   

还是以这个为例

第一步不动 5比2大，因为逆序，所以5不在正确的位置上，把2赋给第2个元素 5比第1个元素大，将guard保存的元素赋给第一个元素 12>5>2，所以5，2，12都不在正确的位置上 12比第一个元素还大 12>7>5>2

转载地址：http://lrqen.baihongyu.com/