编程入门教程第十章 排序 - 图文

10.3.3堆排序小顶堆:ri

?时间复杂度O(nLogn)?

大顶堆:ri>r2i,ri>r2i+1空间复杂度O(1)

349839816581737339814765564756122098349820ypb@ustc.edu.cn21中国科学技术大学voidHeapAdjust(HeapType&H,ints,intm){//算法10.10

//已知H.r[s..m]中记录的关键字除H.r[s]之外均满足堆的定义，rc=H.r[s];

for(j=2*s;j<=m;j*=2){//沿key较大的孩子结点向下筛选

if(j=H.r[j].key)break;//rc应插入在位置s上H.r[s]=H.r[j];s=j;}//for

H.r[s]=rc;//插入}//HeapAdjust

voidHeapSort(HeapType&H){

for(i=H.length/2;i>0;--i)HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){H.r[i]?H.r[1]HeapAdjust(H,1,i-1);}

}//HeapSortypb@ustc.edu.cn22中国科学技术大学10.3.4希尔排序?又称“缩小增量排序”

初始：

4938659776132749554913└────────┘

3827└───────┘

6549└───────┘9755└───────┘

76

└───────┘

一趟排序:132749550449386597

└────┴────┴────┘

270465└────┴────┘

494997└────┴────┘

5538

└────┴────┘

二趟排序：130449382749556597三趟排序：041327384949556576

04

0476

767697

ypb@ustc.edu.cn23中国科学技术大学希尔排序voidShellInsert(SqList&L,intdk){for(i=dk+1;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-dk].key)){L.r[0]=L.r[i];//暂存在L.r[0]

for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];//插入}

}//ShellInsert

voidShellSort(SqList&L,intdlta[],intt){for(intk=0;k

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

ypb@ustc.edu.cn24中国科学技术大学