数据结构与算法-分配排序和索引排序、排序算法的时间代价

8内排序(8.6-8.7)内排序(8.6-8.7)主要内容8.1排序问题的基本概念8.2插入排序（Shell排序）8.3选择排序（堆排序）8.4交换排序8.4.1冒泡排序8.4.2快速排序8.5归并排序8.6分配排序和索引排序8.7排序算法的时间代价2/798.6分配排序和索引排序不需要进行纪录之间两两比较需要事先知道记录序列的一些具体情况主要介绍两类分配排序算法：distributionsorting桶排基数排序介绍索引排序算法内排序(8.6-8.7)3/798.6.1桶式排序事先知道序列中的记录都位于某个小区间段[0，m)内将具有相同值的记录都分配到同一个桶中，然后依次按照编号从桶中取出记录，组成一个有序序列内排序(8.6-8.7)4/79待排数组：

第一趟count：后继起始下标：count[i]=count[i-1]+count[i];

021100121102344468957389618’1’2

0123456789＋＋＋＋

0123456789内排序(8.6-8.7)5/79桶排序示意0211001211023444689511’23678’890123456782待排数组：

第一趟count后继起始下标：收集：7389618’1’20123456789170内排序(8.6-8.7)6/79桶式排序算法template<classRecord>voidBucketSort(RecordArray[],intn,intmax){ //Array数组长度为n，所有记录都位于区间[0,max)上

Record*TempArray=newRecord[n];//临时数组

int*count=newint[max];//桶容量计数器

int

i;for(i=0;i<n;i++) //把序列复制到临时数组

TempArray[i]=Array[i];内排序(8.6-8.7)7/79

for(i=0;i<max;i++) //所有计数器初始都为0 count[i]=0;for(i=0;i<n;i++) //统计每个取值出现的次数 count[Array[i]]++;for(i=1;i<max;i++) //统计小于等于i的元素个数 count[i]=count[i-1]+count[i];

//c[i]记录i+1的起址

//从尾部开始按顺序输出，保证排序的稳定性for(i=n-1;i>=0;i--) Array[--count[TempArray[i]]]=TempArray[i];

//TempArray[i]放到Array[count[TempArray[i]-1]中}内排序(8.6-8.7)8/79算法分析数组长度为n,所有记录区间[0,m)上时间代价：统计计数时：Θ(n+m)输出有序序列时循环n次总的时间代价为Θ(m+n)适用于m相对于n很小的情况空间代价：m个计数器，长度为n的临时数组，Θ(m+n)稳定内排序(8.6-8.7)9/798.6.2基数排序桶式排序只适合m很小的情况当m很大时，可以将一个记录的值即排序码拆分为多个部分来进行比较——基数排序内排序(8.6-8.7)10/79基数排序假设长度为n的序列

R={r0，r1，…，rn-1}

记录的排序码K包含d个子排序码

K=(kd-1，kd-2，…，k1，k0)内排序(8.6-8.7)11/79R对排序码(kd-1，kd-2，…，k1，k0)有序对于任意两个记录Ri，Rj(0≤i<j≤n-1)，都满足

(ki,d-1，ki,d-2，…，ki,1，ki,0)≤(kj,d-1，kj,d-2，…，kj,1，kj,0)其中kd-1称为最高排序码k0称为最低排序码内排序(8.6-8.7)12/79例子

如果我们要对0到9999之间的整数进行排序将四位数看作是由四个排序码决定，即千、百、十、个位，其中千位为最高排序码，个位为最低排序码。基数r=10。可以按千、百、十、个位数字依次进行4次桶式排序4趟分配排序后，整个序列就排好序了内排序(8.6-8.7)13/79基数排序分为两类高位优先法MSD MostSignificantDigitfirst

低位优先法LSD LeastSignificantDigitfirst

内排序(8.6-8.7)14/79黑桃

(S)>红心

(H)

>

方片

(D)

>梅花

(C)

3

J

8

9

9

3

1

7内排序(8.6-8.7)15/79

3

J

8

9

9

3

1

7MSD方法（递归分治）先按花色：

8

1

3

7

J

9

3

9再按面值：

1

8

3

7

9

J

3

9LSD方法先按面值：

1

3

3

’7

8

9

’9

’J再按花色：

1

’8

3

’7

9

’J

3

’9要求稳定排序！内排序(8.6-8.7)16/79高位优先法MSD，MostSignificantDigitfirst先对高位kd-1进行桶式排序，将序列分成若干个桶中然后对每个桶再按次高位kd-2进行桶式排序，分成更小的桶依次重复，直到对k0排序后，分成最小的桶，每个桶内含有相同的排序码(kd-1，kd-2，…，k1，k0)最后将所有的桶依次连接在一起，成为一个有序序列这是一个分、分、…、分、收的过程内排序(8.6-8.7)17/79低位优先法LSD，LeastSignificantDigitfirst从最低位k0开始排序对于排好的序列再用次低位k1排序；依次重复，直至对最高位kd-1排好序后，整个序列成为有序的这是一个分、收；分、收；…；分、收的过程比较简单，计算机常用内排序(8.6-8.7)18/79基数排序的实现基于顺序存储基于链式存储内排序(8.6-8.7)19/79基于顺序存储的基数排序只讨论LSD原始输入数组R的长度为n基数为r排序码个数为d内排序(8.6-8.7)20/79内排序(8.6-8.7)21/79内排序(8.6-8.7)22/79基于数组的基数排序template<classRecord>voidRadixSort(RecordArray[],intn,intd,intr){//n为数组长度，d为排序码个数，r为基

//辅助排序的临时数组 Record*TempArray=newRecord[n];

int*count=newint[r];//存储第i个桶中的记录数

int

i,j,k;

intRadix=1;//模进位，用于取Array[j]的第i位内排序(8.6-8.7)23/79//分别对第i个排序码进行分配for(i=1;i<=d;i++){

for(j=0;j<r;j++) count[j]=0; //初始计数器 for(j=0;j<n;j++) { //统计每个桶

k=(Array[j]/Radix)%r;//取第i位

count[k]++; //计数器加1 }

内排序(8.6-8.7)24/79

for(j=1;j<r;j++) //将TempArray中的位置依次分配给r个桶

count[j]=count[j-1]+count[j]; //count[i]记录了i+1的开始位置

//元素i应该从Array[count[i]-1]往前追溯

//存放count[i]-count[i-1]个内排序(8.6-8.7)25/79

//从数组尾部，把记录收集到相应桶 for(j=n-1;j>=0;j--){

//取第i位排序码，Array[j]应该放到count[k]-1处 k=(Array[j]/Radix)%r; count[k]--; //桶剩余量的计数器减1 //Array[j]放到TempArray中，下标位置先前已被减1

TempArray[count[k]]=Array[j]; } for(j=0;j<n;j++) //将临时数组中的内容复制到Array中

Array[j]=TempArray[j]; Radix*=r;//往左进一位，修改模Radix}}内排序(8.6-8.7)26/79

//从数组尾部，把记录收集到相应桶 for(j=n-1;j>=0;j--){

//取第i位排序码，Array[j]应该放到count[k]-1处 k=(Array[j]/Radix)%r; count[k]--; //桶剩余量的计数器减1 //Array[j]放到TempArray中，下标位置先前已被减1

TempArray[count[k]]=Array[j]; } for(j=0;j<n;j++) //将临时数组中的内容复制到Array中

Array[j]=TempArray[j]; Radix*=r;//往左进一位，修改模Radix}}内排序(8.6-8.7)27/79算法分析空间代价：临时数组,nr个计数器总空间代价Θ(n+r)内排序(8.6-8.7)28/79算法分析（续）时间代价桶式排序：Θ(n+r)d次桶式排序Θ(d·(n+r))内排序(8.6-8.7)29/79基于静态链的基数排序将分配出来的子序列存放在r个(静态链组织的)队列中链式存储避免了空间浪费情况内排序(8.6-8.7)30/7997538859264188’312241225326975988314131225326978888’5988’(c)第一趟收集(b)第一趟分配内排序(8.6-8.7)31/792231419726882226314153598888’975388’594131225326978888’59(e)第二趟收集结果（最终结果）(d)第二趟分配内排序(8.6-8.7)32/79静态队列定义classNode{//结点类public:

intkey; //结点的关键码值

intnext; //下一个结点在数组中的下标};classStaticQueue{//静态队列类public:

inthead;

inttail;};内排序(8.6-8.7)33/79基于静态链的基数排序//静态链实现的基数排序//n为数组长度，d为排序码个数，r为基数template<classRecord>voidRadixSort(Record*Array,intn,intd,intr){

int

i,first=0; //first指向静态链中第一个记录

StaticQueue*queue=newStaticQueue[r];//静态队列 //初始化建链，相邻记录的静态指针链接为单链表

for(i=0;i<n-1;i++)

Array[i].next=i+1;

//指针指向下一个元素

Array[n-1].next=-1;

//链尾next为空内排序(8.6-8.7)34/79

//对第i个排序码进行分配和收集，一共d趟

for(i=0;i<d;i++){

Distribute(Array,first,i,r,queue); Collect(Array,first,r,queue); } delete[]queue;

AddrSort(Array,n,first); //线性时间整理静态链表，使得数组按下标有序}内排序(8.6-8.7)35/79//分配过程,A中存放待排序记录//first为静态链中的第一个记录//i为第i个排序码，r为基数template<classRecord>voidDistribute(Record*Array,intfirst,int

i,intr,StaticQueue*queue){

intj,k,a,curr=first; for(j=0;j<r;j++) //初始化r个队列

queue[j].head=-1;

内排序(8.6-8.7)36/79

while(curr!=-1){ //对整个静态链进行分配

k=Array[curr].key; //取第i位排序码数字k for(a=0;a<i;a++) k=k/r; k=k%r; //把Array[curr]分配到第k个桶中

if(queue[k].head==-1)//若桶空，就是第一个记录

queue[k].head=curr; elseArray[queue[k].tail].next=curr; //否则加到尾 //当前记录的下标curr被标记为该桶的尾部

queue[k].tail=curr; //静态指针curr移动一位，继续分配下一个记录

curr=Array[curr].next;

}}内排序(8.6-8.7)37/79//收集过程，Array中存放待排序记录，//first为静态链中的第一个记录//r为基数template<classRecord>voidCollect(Record*Array,int&first,intr,StaticQueue*queue){

intlast,k=0; //已收集到的最后一个记录

while(queue[k].head==-1)//找到第一个非空队列

k++; first=queue[k].head; last=queue[k].tail;

内排序(8.6-8.7)38/79

//继续收集下一个非空队列，若k==r-1则已是最后

while(k<r-1){

k++; //找下一个非空队列 //当前队列k为空，而且k还不是最后的队列r-1 while(k<r-1&&queue[k].head==-1) k++; //试探下一个队列 //将这个非空序列与上一个非空序列连接起来

if(queue[k].head!=-1){

Array[last].next=queue[k].head; last=queue[k].tail;//最后一个为尾部记录

} } Array[last].next=-1; //收集完毕}内排序(8.6-8.7)39/79线性时间整理静态链表template<classRecord>voidAddrSort(Record*Array,intn,intfirst){int

i,j;j=first; //j待处理数据下标，第一次为firstRecordTempRec;for(i=0;i<n-1;i++){//循环n-1次，每次处理第i大记录

TempRec=Array[j];//暂存第i大的记录Array[j]Array[j]=Array[i];//当前下标i的数据存放到j位置Array[i]=TempRec;//第i大记录入位Array[i].next=j;//第i大的记录的next链要保留调换轨迹jj=TempRec.next;//j移动到下一位while(j<=i)//j比i小，则是轨迹，顺链找到数据j=Array[j].next;}}内排序(8.6-8.7)40/79算法分析空间代价n个记录空间r个子序列的头尾指针Ｏ(n+r)时间代价不需要移动记录本身，只需要修改记录的next指针Ｏ(d·(n+r))内排序(8.6-8.7)41/79空间vs时间速度比较快的排序算法O(nlogn)归并、分配、快速空间消耗都比较大堆空间消耗比较小对于大记录，采用地址排序内排序(8.6-8.7)42/79数组vs链表一般用数组静态链表内排序(8.6-8.7)43/798.6.3索引排序动态链(new出来的指针)数组建立索引数组（通用）建立静态链表内排序(8.6-8.7)44/79索引数组交换指针，减少交换记录的次数用空间换取时间内排序(8.6-8.7)45/79索引方法1：结果下标IndexArray[i]存放的是Array[i]中数据应该待的位置。也就是说Array[IndexArray[i]]=Array[i]用另一个数组整理下标01234567排序码2925346434’123245结果2147503629256434’1232344501234567内排序(8.6-8.7)46/79索引方法2：结果下标IndexArray[i]存放的是Array[i]中应该摆放的数据位置。也就是说Array[i]=Array[IndexArray[i]]用另一个数组整理下标01234567排序码2925346434’123245结果5106247329256434’12开新数组32344501234567内排序(8.6-8.7)47/79不开新数组只利用原Array和IndexArray可以用一个临时空间RecordTempRec;根据IndexArray内容，整理好原Array，使得Array数组按下标有序在O(n)的时间内完成内排序(8.6-8.7)48/79顺链整理下标01234567排序码2925346434’123245结果51062473整理2147503629256434’1232344501234567内排序(8.6-8.7)49/79得到索引2的方法？一般的排序方法都可以那些赋值（或交换）都换成对index数组的赋值（或交换）举例：插入排序内排序(8.6-8.7)50/79template<classRecord>voidAddrSort(RecordArray[],intn){ //Array[]为待排序数组，n为数组长度

int*IndexArray=newint[n],TempIndex;

int

i,j,k;RecordTempRec;//只需一个临时空间

for(i=0;i<n;i++)IndexArray[i]=i; for(i=1;i<n;i++)//依次插入第i个记录

for(j=i;j>0;j--)//依次比较，发现逆置就交换

if(Array[IndexArray[j]]< Array[IndexArray[j-1]])) swap(IndexArray,j,j-1); elsebreak; //此时i前面记录已排序

内排序(8.6-8.7)51/79//根据IndexArray整理Array[算法8.15]for(i=0;i<n;i++){//调整的代价为O(n) j=i;

TempRec=Array[i]; while(IndexArray[j]!=i){ k=IndexArray[j]; Array[j]=Array[k];

IndexArray[j]=j;

j=k; } Array[j]=TempRec;

IndexArray[j]=j; }}内排序(8.6-8.7)52/79内排序(8.6-8.7)算法8.·5的代价时间代价Θ(n)

空间代价Θ(1)

53/79得到索引1的方法？*Rank排序静态链表的基数排序内排序(8.6-8.7)54/79Rank排序*template<classRecord>voidRank(Record*array,int

listsize,Record*rank){ for(int

i=0;i<listsize;i++) rank[i]=0; for(i=0;i<listsize;i++) for(intj=i+1;j<listsize;j++){ if(Array[i]>array[j]) rank[i]++; else rank[j]++; }}内排序(8.6-8.7)55/798.7排序算法的时间代价8.7.1简单排序算法的时间代价8.7.2排序算法的理论和实验时间8.7.3排序问题的下限内排序(8.6-8.7)56/79原因一个长度为n序列平均有

n(n-1)/4对逆置任何一种只对相邻记录进行比较的排序算法的平均时间代价都是Θ(n2)

内排序(8.6-8.7)57/798.7.2排序算法的理论和实验时间算法最大时间平均时间最小时间辅助空间代价稳定性直接插入排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定冒泡排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定选择排序Θ(n2)Θ(n2)Θ(n2)Θ(1)不稳定内排序(8.6-8.7)58/79算法最大时间平均时间最小时间辅助空间稳定性Shell排序(3)Θ(n3/2)Θ(n3/2)Θ(n3/2)Θ(1)不稳定快速排序Θ(n2)Θ(nlogn)Θ(nlogn)Θ(logn)不稳定归并排序Θ(nlogn)Θ(nlogn)Θ(nlogn)Θ(n)稳定堆排序Θ(nlogn)Θ(nlogn)Θ(nlogn)Θ(1)不稳定桶式排序Θ(n+m)Θ(n+m)Θ(n+m)Θ(n+m)稳定基数排序Θ(d·(n+r))Θ(d·(n+r))Θ(d·(n+r))Θ(n+r)稳定内排序(8.6-8.7)59/79小结n很小或基本有序时插入排序比较有效Shell排序选择增量以3的倍数递减需要保证最后一趟增量为1综合性能快速排序最佳内排序(8.6-8.7)60/79测试环境硬件环境：CPU：IntelT24001.83G内存：1G软件环境：windowsxpVisualC++6.0内排序(8.6-8.7)61/79随机生成待排序数组//设置随机种子inlinevoidRandomize(){srand(1);}//返回一个0到n之间的随机整数值inlineintRandom(intn){returnrand()%(n);}//产生随机数组ELEM*sortarray=newELEM[1000000];for(int

i=0;i<1000000;i++)

sortarray[i]=Random(32003);内排序(8.6-8.7)62/79时间测试#include<time.h>/*Clockticksmacro-ANSIversion*/#defineCLOCKS_PER_SEC1000clock_t

tstart=0;//Timeatbeginning//InitializetheprogramtimervoidSettime(){tstart=clock();}//TheelapsedtimesincelastSettime()doubleGettime(){return(double)((double)clock()-(double)tstart)/(double)CLOCKS_PER_SEC;}内排序(8.6-8.7)63/79排序的时间测试

Settime();

for(i=0;i<ARRAYSIZE;i+=listsize){

sort<int>(&array[i],listsize);

print(&array[i],listsize);

}

cout<<"Sortwithlistsize"<<listsize<<",arraysize"<<ARRAYSIZE<<",andthreshold"<<THRESHOLD<<":"<<Gettime()<<"seconds\n";内排序(8.6-8.7)64/79数组规模101001K10K100K1M10K正序10K逆序直接插入排序0.000000470.0000200.0017820.175217.917_____0.000110.35094选择排序0.000001100.0000410.0029220.277836.500_____0.277810.29109冒泡排序0.000001600.0001560.0156201.5617207.69_____0.000062.44840Shell排序(2)0.000001560.0000360.0006400.01090.19073.05790.001560.00312Shell排序(3)0.000000780.0000160.0002810.00380.05790.82040.001250.00687堆排序0.000002040.0000270.0003440.00420.05320.68910.004060.00375快速排序0.000001690.0000210.0002660.00300.03750.47820.001900.00199优化快排/160.000001720.0000200.0002650.00200.02350.36100.000820.00088优化快排/280.000000620.0000110.0001410.00180.02350.25940.000630.00063归并排序0.000002190.0000280.0003750.00450.05320.59690.003640.00360内排序(8.6-8.7)65/79数组规模101001K10K100K1M10K正序10K逆序优化归并/160.000000630.0000140.0001880.00300.03750.41570.002030.00265优化归并/280.000000620.0000130.0002040.00270.03600.41560.001720.00265顺序基数/80.000006100.0000490.0004690.00480.04810.48130.004840.00469顺序基数/160.000004850.0000340.0003290.00320.03240.32660.003280.00313链式基数/20.000025780.0002330.0022970.02340.24093.48440.022460.02281链式基数/40.000009220.0000750.0007190.00750.07731.37500.007190.00719链式基数/80.000007040.0000480.0004660.00490.05020.99530.004690.00469链式基数/160.000005160.0000300.0002660.00280.02950.65700.002810.00281链式基数/320.000005000.0000270.0002350.00280.02970.54060.002630.00266内排序(8.6-8.7)66/798.7.3排序问题的下限排序问题的时间代价在

(n)(起码I/O时间)到O(nlogn)(平均,最差情况)之间基于比较的排序算法的下限也为