堆排序最大化堆

概述

排序：内部排序：全部记录都可以同时调入内存进行的排序。 外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。

定义：设有记录序列：{R1、R2………..Rn}其相应的关键字序列为：

{K1、K2………..Kn};若存在一种确定的关系：Kx

<=Ky<=

…<=Kz

则将记录序列{R1、R2………..Rn}排成按该关键字有序的序列：

{Rx、Ry………..Rz}的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系或任意的关系。稳定与不稳定：若记录序列中的任意两个记录Rx、Ry的关键字Kx

=Ky；如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的。2合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk3合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk74合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk75合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk7136合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk7137合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk713498合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk713499合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk713496510合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk713496511合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk71349657612合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk71349657613合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk7134965768014合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk7134965768015合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。0123 44913659776780AB0123 4567Cijk713496576809716合并排序

Mergingsort:思想来源于合并两个已排序的顺序表。e.g:将下面两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。123 4549136597A76789 76780B3123 456789C491365977678037

实现很简单，A、B、C三表分别设置指针p、q、k初值为1,6,1，比较p、q指针指向

的结点，将小者放入C表,相应指针加1。如A、B表中一张表为空，则将另一张表的结点全部移入C表。比较次数和移动次数和两张表的结点总数成正比。17合并排序

合并二张有序表：template<classEType>voidMerge(ETypea[],ETypeaa[],intn,intlow,intup,int

m){intp=low,q=low+m,r;//合并a[low]至a[low+m-1]和a[low+m]至a[up]。

for(r=1;r<=n;r++)aa[r]=a[r];r=low;//数组

a的初始指针。while(p<low+m&&q<up+1){ while(p<low+m&&aa[p]<=aa[q])a[r++]=aa[p++]; if(p<low+m)while(q<up+1&&aa[q]<aa[p])a[r++]=aa[q++];}if(p==low+m) for(;q<=up;q++)a[r++]=aa[q];if(q==up+1) for(;p<=low+m-1;p++)a[r++]=aa[p];}18合并排序

合并排序的基本思想：

1234567978352416793845216378941652347891652子表长m：1子表长m：2子表长m：4子表长m：8分析：1、被合并的二张表中第一张表的起始地址设为low,那么第二张表的起始地址应为low+m,而终止地址通常为up=low+2m-1。如果up>n(表长)，那么up=n；即取二者小者作第二张表的终止地址。

2、当up+m>=n时，意味着下一次被合并的两张表中的第一张表的末地址大于等于最大下标n，这说明被合并的第二张表不存在，意味着本趟结束。要过渡到下一趟合并；m应增大一倍。

3、当子表长m>=n时，合并排序结束。ij19合并排序

合并排序法：template<classEType>voidMergeSort(ETypea[],intn){//待排序的表为数组a,a[0]不用，待排序的数组元素为

a[1],a[2],……,a[n]。

int

low=1;//被合并的二个表中的第一个表的首地址。

intup; //被合并的二个表中的第二个表的末地址。

intm=1;//被合并的二个表中的第一个表的表长。初始时为1。

EType*aa;aa=newEType[n+1];//用于合并的辅助数组，aa[0]仍然不用。

while(m<n){

up=min(low+2*m–1,n); Merge(a,aa,n,low,up,m);//将a[low]至

a[low+m-1]和a[low+m]至a[up]进行合并。

if(

up+m<n)

low=up+1;//up+m≥n意味着被合并的另一张表不存在。

else{m*=2;

low=1;

}//过渡到下一次合并，子表长度增大一倍。

}delete[]aa;}

20合并排序·时间复杂性分析：

合并的过渡趟数：logn

每趟进行时，调用merge过程n/(2*len)次，每次比较和数据移动都是(2*len)

次，因此每趟代价为O(n)。总的代价为T(n)=O(nlogn)

在递归的情况下：可通过下式求出时间复杂性的级别。

2forn=2 T(n)= T(n/2)+T(n/2)+nelse解上述的递归式，可知时间复杂性为T(n)=O(nlogn)。当n是2的整数幂时简化为T(n)=O(nlogn)21用比较法进行排序的时间下界

判定树模型：如下图所示，说明对a,b,c进行分类的一颗判定树。当判断条件成立时， 转向左，否则转向右。

比较法分类的下界：Ω(nlogn)a<ba<b<ca<cb<ca<cb<ca<c<bc<a<bc<b<ab<a<cb<c<anoyesyesyesyesyesnononono

注意：树高代表比较的代价。因此只要知道了树高和结点数n的关系，就可以求出 用比较法进行排序时的时间代价。另外，n个结点的分类序列，其叶子结点 共有n!片。22用比较法进行排序的时间下界

定理：高为H的二叉树，最多具有2(H-1)片叶子。

证明：H＝1时，最多1片叶子，定理成立。

H＝2时，最多2片叶子，定理成立。 设H＝n-1时公式成立。则当H＝n时，根结点有具有叶子结点最多的高为n-1的左 右子树；叶子结点总数为：

2(n-2)×2

＝2(n-1)

公式成立。推论：具有N片叶子的二叉树，高最少为logN+1。或比较次数最少为logN

。

比较法分类的下界：Ω(nlogn)高为n-1具有2(n-2)片叶子高为n-1具有2(n-2)片叶子H=1H=2H=n

定理：把n个不同的结点进行分类的任一判定树的高 度至少为log(n!)+1。

证明：n个元素的排序序列的总数共有n!种，因此在 相应的判定树上至少有n!片叶子。根据上述定 理，可证。推论：用比较的方法对n个元素的进行分类。在最坏 情况下至少需要cnlogn

次比较，或 Ω(nlogn)23用比较法进行排序的时间下界

比较法分类的下界：Ω(nlogn)X轴Y轴求y=logx

的积分的示意图211234y=logn11n-1nj=1nn1

logn!=Σlogj≥logxdx

不难求出上述积分的值为：nlogn-nloge+loge≥nlogn-nloge。注意到：loge=1.44。

24简单选择排序

执行过程：1225492516834521254925168212549258162125492516218rprp1649252521816492525218rp1621252549816212525498rp1621252549816212525498rp16212525498625template<classEType>voidSelectSort(ETypea[],intn){intp,q;//p、q为数组a的指针。a[1],a[2],…,a[n]为待排序序列。a[0]不用。

intr;//暂时保存具有最小键值的结点地址。

for(p=1;p<n;p++){ r=p; for(q=p+1;q<=n;q++)if(a[q]<a[r])r=q;//记住本趟挑选的最小结点的地址。

if(r!=p){a[0]=a[p];a[p]=a[r];a[r]=a[0];}//若最小结点不是a[p],则交换。

}}简单选择排序26有n个元素的数组的比较次数

(n-1)+(n-2)+...+2+1=O(n2)交换次数

3(n-1)因循环执行(n-1)次，最坏情况下每次都交换。

总的时间复杂性代价为：O(n2)简单选择排序树型选择排序

改进：简单选择排序没有利用上次选择的结果，是造成速度慢的主要原因。如果能够 加以改进，将会提高排序的速度。381376276549974938651327133813选出最小者13树型选择排序

改进：简单选择排序没有利用上次选择的结果，是造成速度慢的重要原因。如果，能 够加以改进，将会提高排序的速度。由于有更好的排序方法，所以本方法用的 很少。381376276549974938651327133813选出次最小者，应利用上次比较的结果。从被13打败的结点27、76、38中加以确定。堆排序

堆的定义：n个元素的序列{k1，k2

，……，kn

}，当且仅当满足以下关系时，称 之为堆：

ki<=

k2i ki>=

k2i ki<=

k2i+1 ki>=

k2i+1

(i=1,2,……,n/2)

且分别称之为最小化堆和最大化堆。

e.g:序列{96,83,27,11,9} 最大化堆

{12，36，24，85，47，30，53，91}最小化堆

或9691183272314512478591362453306273184530

70604030128最大堆的最大元素

1031

[1][2][3][4][5][6][7]706012403081070160240

4

30

512

386root10

7数组表示的堆

32建堆30160240

4

70

58

312610

7root[1][2][3][4][5][6][7]3060840701210叶子结点，符合堆的的定义。不合堆的定义，需调整。即建立小堆。建立的第一个小堆的堆顶的下标为n/2数组h33建堆30160240

4

70

58

312610

7root[1][2][3][4][5][6][7]3060124070810叶子结点，符合堆的的定义。不合堆的定义，需调整。即建立大堆。建立的第一个小堆的堆顶的下标为n/2数组h34建堆30160240

4

70

512

38610

7root[1][2][3][4][5][6][7]3060124070810不合堆的定义，需调整。建立以h[2]为堆顶的正确的最大化小堆。数组h35建堆30170240

4

60

512

38610

7root[1][2][3][4][5][6][7]3070124060810不合堆的定义，需调整。建立以h[2]为堆顶的正确的最大化小堆。数组h36建堆30170240

4

60

512

38610

7root[1][2][3][4][5][6][7]3070124060810不合堆的定义，需调整。建立以h[1]为堆顶的正确的最大化堆。数组h37建堆70130240

4

60

512

38610

7root[1][2][3][4][5][6][7]7030124060810不合堆的定义，需调整。建立以h[1]为堆顶的正确的最大化堆。数组h38建堆70160240

4

30

512

38610

7root[1][2][3][4][5][6][7]7060124030810不合堆的定义，需调整。建立以h[1]为堆顶的正确的最大化堆。数组h39建堆时间复杂性的分析：

时间耗费的代价：建堆的时间耗费＋排序的时间耗费建堆的时间耗费：设树根处于第

1层，该堆共有h层。建堆从第h-1层开始进行。只 要知道了每一层的结点数（建的小堆的个数），和每建一个小堆所 需的比较次数，就可以求得建堆的时间耗费。建的小堆的性质：第i层上小堆的个数＝第i层上结点的个数＝最多

2i-1

第i层上小堆的高度＝h-i+1

建第i层上每个小堆最多所需的比较次数＝2×（h-i）次建堆的时间耗费：

T(n)<=∑2i-1×(h-i)×2=∑2i×(h-i)=∑2h-j×j =2h∑j/2j注意：即使是高度为h的完全的二叉树，满足以下式子：

2h－1<=n<=2h-1故：2h<=2n

又：∑j/2j<2

所以：建堆的时间复杂性为4n=O(n)级i=h-1i=h-1j=1h-111j=1h-1j=1∞10304060127086231745123=h40建堆

建立最大化堆template<classEType>voidMaxHeap<EType>::SiftDown(intj){//heap[1],…,heap[n]为存储堆的数组。heap[0]不用。

intMaxSon;//用于记录大儿子的下标地址。

heap[0]=heap[j];for(;j*2<=CurrentSize;j=MaxSon){MaxSon=2*j;if(MaxSon!=CurrentSize&&heap[MaxSon+1]>heap[MaxSon])MaxSon++;if(heap[MaxSon]>heap[0])heap[j]=heap[MaxSon];elsebreak;}heap[j]=heap[0]; }

template<classEType>voidMaxHeap<EType>::BuildHeap(){for(intj=CurrentSize/2;j>0;j--)SiftDown(j);}30170240

4

6051238610

7j41

堆排序7060124030810values70160240

4

30

512

3

86root10

7[1][2][3][4][5][6][7]42

堆排序values1060124030870不需再考虑！[1][2][3][4][5][6][7]10160240

4

30

512

386root70

743

堆排序values6040121030870[1][2][3][4][5][6][7]60140210

4

30

512

386root70

744

堆排序6040121030870[1][2][3][4][5][6][7]60140210

4

30

512

386root70

745

堆排序values8401210306070不需再考虑！[1][2][3][4][5][6][7]8140210

4

30

512

3606root70

746

values4030121086070堆排序[1][2][3][4][5][6][7]40130210

4

8

512

3606root70

747

values4030121086070堆排序[1][2][3][4][5][6][7]40130210

4

8

512

3606root70

748

values堆排序8301210406070不需再考虑！[1][2][3][4][5][6][7]8130210

4

40

512

3606root70

749

values3010128406070堆排序[1][2][3][4][5][6][7]3011028

4

40

512

3606root70

750

values3010128406070堆排序[1][2][3][4][5][6][7]3011028

4

40

512

3606root70

751

values堆排序8101230406070不需再考虑！[1][2][3][4][5][6][7]8110230

4

40

512

3606root70

752

values1210830406070堆排序[1][2][3][4][5][6][7]12110230

4

40

58

3606root70

753

values1210830406070堆排序[1][2][3][4][5][6][7]12110230

4

40

58

3606root70

754

values堆排序不需再考虑！8101230406070[1][2][3][4][5][6][7]8110230

4

40

512

3606root70

755

values1081230406070堆排序[1][2][3][4][5][6][7]1018230

4

40

512

3606root70

756

values1081230406070堆排序[1][2][3][4][5][6][7]30

510

71018230

4

40

512

3606root70

757

数组h堆排序8101230406070不需再考虑！[1][2][3][4][5][6][7]10230

4

40

512

3606root70

78

158

堆排序template<classEType>voidSiftDown(ETypea[],intj,intSize){//a[1],…,a[Size]为存储堆的数组。a[0]不用。注意：本函数用于排序。Size为堆的最

//大下标，j为当前要建立的最大化堆的堆顶结点的地址。

intMaxSon;//用于记录大儿子的下标地址。

a[0]=a[j];for(;j*2<=Size;j=MaxSon){ MaxSon=2*j; if(MaxSon!=Size&&a[MaxSon+1]>a[MaxSon])MaxSon++; if(a[MaxSon]>a[0])a[j]=a[MaxSon]; elsebreak;}a[j]=a[0]; }template<classEType>voidMaxHeapSort(ETypea[],intSize){for(intj=Size/2;j>0;j--)//a[1],a[2],…,a[Size]为待排序的数组。a[0]不用。

SiftDown(a,j,Size);//将

a[1],a[2],…,a[Size]建成最大化堆。

for(intk=Size;k>1;k--){ Swap(a[1],a[k]);//交换

a[1]和

a[k],最大元素放在

a[k]。

SiftDown(a,1,k-1);//将

a[1],a[2],…,a[k-1]调整为最大化堆。

}}59堆排序

时间复杂性的分析：建堆的时间耗费＋排序的时间耗费排序的时间耗费： 结点个数 高度 比较次数最多

j=2 log2+1 <=2×log2 j=3 log3+1 <=2×log3 j=4 log4+1 <=2×log4 j=n-1 log(n-1)+1 <=2×log(n-1)所以：T(n)<=2(log2+log3+……..+log(n-1))=2log(n-1)!T(n)=O(nlogn)时间复杂性的分析：10304060127086231745123=h60堆排序

堆排序的时间代价分析推导：O(nlogn)X轴Y轴求y=logx的积分的示意图21234y=logx11n-1nj=2n-1n1

log(n-1)!=Σlogj≤logxdx

不难求出上述积分的值为：nlogn-nloge+loge≥nlogn-nloge。注意到：loge=1.44。

61堆排序

最大化堆（最小化堆亦可）用以表示优先队列常用的基本操作：

1、Inset：将具有给定优先数的新结点插入优先队列，代价O(logn)

若分二步：1、先找出新结点的插入位置，代价为O(logn)2、通过移动，将新结点插入，代价O(logn)

总代价仍未改进，仍是O(logn)2、DeleteMax：删除具有最大优先数的结点，代价O(logn)3、Delete：删除任一结点，代价O(logn)4、IncreasePriority(DecreasePriority):

增大（或减少）结点的优先数代价O(logn)5、Merge：合并二个优先队列为一个无法在O(logn)内做到改进：使用最左树9659518377231453931484767899111415494110112921121379316171层2层3层4层5层62最左树最左树：是一棵二叉树。结点的s值。设二叉树的外部结点(空的儿子结点)的

s值为0，其他每个结点的

s值为左、右儿子结点的s值的小者加

1。如果每个结点的左儿子的s

值不小于右儿子的s值，而且父结点之值大于等于(或小于等于)儿子结点(如果存在的

话)之值的话，那末这棵二叉树被称之为最左树。

3111112211329015322010751211013182311112256816122463最左树

定理：设x是最左树的内部结点，那么1.

以

x为根的子树的结点的数目至少为

2S(x)–1。2.

如果子树

x有m个结点，S(x)至多为

log2(m+1)。3.

通过最右路径，从

x到达外部结点的路径长度为

S(x)。证明：1.设x所在结点的层次为

0，儿子结点的层次为1，以下依次加1，……。则根据定义，x的后代中，如果

s值为1，则该后代的儿子中必有一个为空。换句话说，由

x到达最“近”的且s值为1的后代之前，x及其后代的儿子数2都为两个。因此，直至第

S(x)－

1层没有外部结点，第

S(x)层才有外部结点。所以，结点总数至少为：1+2+……+2S(x)-1=2S(x)-1个结点。注意，从第S(x)层起，开始出现外部结点，同时还可能有内部结点。

2．由

1.可知，结点数至少为2s(x)-1=m时，x的s值为S(x)。S(x)的值至多

为log(m+1)。

3.根据定义，每个内部结点的右儿子的

s值小于等于左儿子的

s值，故通过最右路径，从x到达外部结点的路径长度为S(x)。很明显，任意结点的s值为本结点到它的度为0或1的子孙结点的最短路径长度加1。

2311112256816122431111122113290153220107512110131864最左树23111122568161224311111221132901532201075121101318

合并最左树示例1121075112122472

合并中涉及到的最左树65最左树

合并过程

1172117212105a、b、1172c、1212412105117212124121051172232225681612124121051172d、f、e、

66最左树

最后得到的最左树

14111112239015322012110830231125681612124111051172g、

67a[0]用作哨兵。共执行5遍操作。每遍操作：先将元素复制内容放入a[0]，再将本元素同已排序的序列，从尾开始进行比较。在已排序的序列中寻找自己的位置，进行插入。或者寻找不到，则一直进行到哨兵为止。意味着本元素最小，应该放在a[1]。每一遍，排序的序列将增加一个元素。如果序列中有n个元素，那么最多进行n遍即可。直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。01236241061234568直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453624j69直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453624j70直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453624j2471直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453610j2472直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453610j2473直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453610j2474直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106123453610j241075直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。01236241061234536246j1076直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。01236241061234536246j1077直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。01236241061234536246j1078直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。01236241061234536246j10679直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106345362412j1061280直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106345362412j1061281直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106345362412j1061282直接插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。0123624106345362412j106121283直接插入排序01210203040345102040505030分析:移动、比较次数可作为衡量时间复杂性的标准正序时：比较次数∑1=n-1 i=2

移动次数2（n-1）

n

逆序时：比较次数∑i=(n+2)(n-1)/2 i=2

移动次数∑(i+1)=(n+4)(n-1)/2

i=2nn84直接插入排序01236241063453624121061212template<classEType>voidSimpleInsertSort(ETypea[],intSize){

int

j,q;//a[1],a[2],…,a[Size]为待排序的数组。a[0]为哨兵单元。

ETypetemp=a[0];for(j=2;j<=Size;j++){a[0]=a[j];for(q=j;a[0]<a[q-1];q--) a[q]=a[q-1];a[q]=a[0];}a[0]=temp; //恢复a[0]原来的值，用于快速排序法中。}程序实现:362410612j85折半插入排序template<classEType>voidBinaryInsertSort(ETypea[],int

Size) {

int

low,high;//a[1],a[2],…,a[Size]为待排序的数组。a[0]用哨兵单元。

intj,k,mid;

for(j=2;j<=Size;j++){a[0]=a[j];low=1;high=j-1;//在

a[1],…,a[j-1]范围内寻找a[j]的插入位置。

while(low<=high){ mid=(low+high)/2;//中点下标。

if(a[0]<a[mid])high=mid–1;//小于中点，查找左段。

elselow=mid+1;//大于等于中点，查找右段。

}for(k=j-1;k>=low;--k)a[k+1]=a[k];a[low]=a[0];} }程序实现:362410612362412high1061212方法：在已排序的序列中查找下一元素的插入位置，将该元素插入进去，形成更长的排序序列。如：12的插入位置为下标3。减少了比较次数，未降低时间复杂性。jlow86折半插入排序362410612362412high1061212方法：在已排序的序列中查找下一元素的插入位置，将该元素插入进去，形成更长的排序序列。如：12的插入位置为下标3。减少了比较次数，未降低时间复杂性。jlow12362412high10612jlow12362412high10612jlow

m

m注意:low指针总是指向新关键字的下标地址，如：12的插入位置为3。87

希尔(shell)排序e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序

1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。步长8：49、38、65、97、76、13、27、49、55、4步长8：49、38、65、97、76、13、27、49、55、488希尔排序e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序

1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。步长8：49、38、65、97、76、13、27、49、55、4步长8：49、4、65、97、76、13、27、49、55、38步长为8的序列的排序结束。89希尔排序e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序

1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。步长4：49、4、65、97、76、13、27、49、55、38步长4：49、4、65、97、76、13、27、49、55、3890希尔排序e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序

1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。步长4：49、4、27、49、55、13、65、97、76、38步长4：49、4、65、97、76、13、27、49、55、3891希尔排序e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序

1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。步长2：49、4、27、49、55、13、65、97、76、38步长2：49、4、27、49、55、13、65、97、76、3892希尔排序e.g:将序列49、38、65、97、76、13、27