插入排序超详解释，一看就懂

void InsertSort(SqList &L){

int i, j;

for (i=2; i<=L.length; ++i) {

if (L.r[i].key < L.r[i-1].key){                 //若"<"需将L.r[i]插入有序子表
L.r[0]=L.r[i];                                 //复制为哨兵

for (j=i-1;L.r[O].key<L.r[j].key; --j){

L.r[j+1]=L.r[j];                            //记录后移

}

L.r[j+1]=L.r[O];                          //插入到正确位置
     }

}

五、折半插入排序

1、查找插入位置时采用折半查找法，如下图所示：

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[O].key < L.r[mid].key )      high = mid -1;
else low=mid+1;

}                        //循环结束，high+1则为插入位置

for (j=i-1;j>=high+1;--j) 
L.r[j+1]= L.r[j;                  //移动元素
L.r[high+1] = L.r[0];            //插入到正确位置
       }

}        //BInsertSort

3、折半插入排序——算法分析

（1）折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快;

（2）它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。

（3）当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差;

（4）在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少;

（5）折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列

减少了比较次数，但没有减少移动次数

六、希尔排序

1、基本思想:

先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

2、希尔排序算法的特点:

（1）缩小增量

（2）多遍插入排序

3、希尔排序的典例

4、由上图可知，希尔排序的思路

①定义增量序列 $D_{k}$ ： $D_{M}$ > $D_{M-1}$ >...> $D_{1}$ =1;

上图的典例就是：D3=5;D2=3;D1=1;

②对每一个 $D_{k}$ 进行“ $D_{k}$ -间隔”插入排序（k=M,M-1,...1)

5、希尔排序的特点

一次移动，移动位置较大，跳跃式地接近排序后的最终位置，最后一次只需要少量移动。

6、希尔排序的算法描述

void ShellSort (Sqlist &L int dlta[], int t){  //按增量序列dlta[0...t- 1]对顺序表L作希尔排序。

for(k=O; k<t; ++k)

Shellinsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序

}//ShellSort


void ShellInsert(SqList &L，int dk)

//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
for(i=dk+1; i<=L.length; ++i)

if(r[i].key < r[i-dk].key) {

r[0]=r[i];

for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk)

r[j+dk]=r[j];

r[j+dk]=r[0];
}

    }

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

排序

数据结构与算法

笔记

排序算法

算法