第八章-内排序【】2优秀文档

第八章内排序宋国杰北京大学信息科学技术学院28.6分配排序和基数排序特征：不需要进行排序比较，而是通过“分配”和“收集”过程来实现排序。前提：需事先知道记录序列的一些具体情况如所有记录值都固定的某个区间，如记录都位于某个小区间段[0，m)内31、桶式排序Bucketsorting，最简单的分配排序基本思想事先知道序列中记录都位于某个小区间[0，m)内将具有相同值的记录都分配到同一桶中，然后依次按照编号从桶中取出记录，组成一个有序序列桶的个数取决于关键字的取值范围(m)for(intj=0;j<r;j++) //初始化r个队列count[Array[i]]++;inti,j,k;::Distribute(Record*Array,intfirst,inti,intr,StaticQueue*queue){Array[last].next=first;0123456789先对高位kd-1进行桶式排序，将序列分成若干个桶中for(i=0;i<n;i++) //统计每个取值出现的次数inti,j,k;count[j]=count[j-1]+count[j];电话：62754785第二趟收集（让队尾指针t[i]链接到下一非空队首指针h[i+1]）待排数组：

第一趟count：后继起始下标：count[i]=count[i-1]+count[i];021100121102344468957389618’1’20123456789＋＋＋＋0123456789桶排序示意0211001211023444689511’23678’890123456782待排数组：

第一趟count后继起始下标：收集：7389618’1’20123456789170template<classRecord>voidBucketSort(RecordArray[],intn,intm){

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

int*count=newint[m]; //小于或等于i的元素个数

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

TempArray[i]=Array[i];for(i=0;i<max;i++) //所有计数器初始都为0 count[i]=0;6桶式排序算法for(i=0;i<n;i++) //统计每个取值出现的次数

count[Array[i]]++;for(i=1;i<max;i++) //统计小于等于i的元素个数

count[i]=count[i-1]+count[i];

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

Array[--count[TempArray[i]]]=TempArray[i];}8算法分析时间代价统计计数时：Θ(m+n)总的时间代价：Θ(m+n)

空间代价需要m个计数器，n个临时空间总的空间代价：Θ(m+n)适用于m相对于n很小的情况稳定算法对m的讨论当m为Θ(n)数量级时，时间代价为Θ(Θ(n)+n)，还是Θ(n)。这时桶式排序的效率相对于前面那些排序算法是一个飞跃但当m为更高数量级，例如Θ(nlogn)或Θ(n^2)时，时间代价就由m来决定，也变成Θ(nlogn)或Θ(n^2)。这时桶式排序相比于前面那些排序就没有什么优势了，不仅如此，桶式排序还需要额外的Θ(m+n)的空间代价。因此，桶式排序只对于m较小时才具有实际意义102、基数排序桶式排序只适合m很小的情况当m很大时，可以将一个记录的值即排序码拆分为多个部分来进行比较，即基数排序（RadixSort）设长度为n的序列R={r0,r1,…,rn-1}，记录的排序码K包含d个子排序码K=(kd-1,kd-2,…,k1,k0)，则称R对排序码(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称为最低排序码。Ki的取值范围称为基数，记做r11举例0到9999之间整数排序将4位数看作是由4个排序码决定，即千、百、十、个位，其中千位为最高排序码，个位为最低排序码。基数r=10可以按千、百、十、个位数字依次进行4次桶式排序4趟分配排序后，整个序列就排好序扑克牌若规定花色和面值的顺序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A则可以先按花色排序，花色相同者再按面值排序；也可以先按面值排序，面值相同者再按花色排序。12基数排序分为两类高位优先法（MSD，MostSignificantDigitfirst）低位优先法（LSD，LeastSignificantDigitfirst）扑克牌排序MSD方法思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。LSD方法思路：先按面值分成13堆（每堆4张牌），然后对每堆牌按花色进行排序（用插入排序等稳定的算法）13高位优先法先对高位kd-1进行桶式排序，将序列分成若干个桶中然后对每个桶再按次高位kd-2进行桶式排序，分成更小的桶依次重复，直到对k0排序后，分成最小的桶，每个桶内含有相同的排序码(kd-1，kd-2，…，k1，k0)；最后将所有的桶依次连接在一起，成为一个有序序列这是一个分、分、…、分、收的过程是一个递归分治问题

14低位优先法从最低位k0开始排序对于排好的序列再用次低位k1排序依次重复，直至对最高位kd-1排好序后，整个序列成为有序的这是一个分、收；分、收；…；分、收的过程。比较简单，计算机常用151617基数排序的实现基于顺序存储基于静态链式存储下面基于LSD方法进行讨论18基于顺序存储的基数排序原始输入数组R的长度为n基数为r排序码个数为d192021基于数组的基数排序算法template<classRecord>voidRadixSorter<Record>::Sort(RecordArray[],intn,intd,intr){ //n为数组长度，d为排序码数，r为基数

Record*TempArray=newRecord[n]; //临时数组 int*count=newint[r]; //计数器

inti,j,k; intRadix=1;

for(i=1;i<=d;i++){ //取Array[j]的第i位排序码

for(j=0;j<r;j++) //分别对第i个排序码分配 count[j]=0; //初始计数器均为0 for(j=0;j<n;j++){ //统计每个桶中的记录数

//取Array[j]的第i位排序码 k=(Array[j]/Radix)%r; count[k]++; //相应计数器加1 } //将TempArray中的位置依次分配给r个桶 for(j=1;j<r;j++) count[j]=count[j-1]+count[j];23 //将所有桶中的记录依次收集到TempArray中

for(j=n-1;j>=0;j--){

k=(Array[j]/Radix)%r;//取Array[j]的第i位排序码 count[k]--;//从第k个桶取出一个记录，计数器减1 TempArray[count[k]]=Array[j]; }

for(j=0;j<n;j++)//将临时数组中的内容复制到Array中 Array[j]=TempArray[j]; Radix*=r; }}24算法分析空间代价：临时数组,nr个计数器Θ(n+r)时间代价桶式排序：Θ(n+r)d次桶式排序Θ(d*(n+r))25基于静态链的基数排序将分配出来的子序列存在r个(静态链组织的)队列中链式存储避免了在分配和收集时都需要移动所有记录，导致时间代价增高26静态队列定义classNode{//结点类public: intkey; //结点的关键码值

intnext; //下一个结点在数组中的下标};classStaticQueue{//静态队列类public: inthead;//头指针 inttail;//尾指针};27614921485637738101215530790306第一趟分配t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]614738921485637101215530790306h[0]h[1]h[2]h[3]h[4]h[5]h[6]h[7]h[8]h[9]原始序列静态链表：r[0]→（从最低位i=3开始排序，h[]

是队首指针，t[]为队尾指针）第一趟收集（让队尾指针t[i]链接到下一非空队首指针h[i+1]

即可）530790921101614485215306637738r[0]→举例0123456789tail=first; //first为子序列的尾部叶结点的最小深度就是最佳情况下的最小比较次数//first为静态链中的第一个记录,i为第i个排序码，r为基数TempArray[count[k]]=Array[j];for(i=0;i<max;i++) //所有计数器初始都为0count[i]=0;Bucketsorting，最简单的分配排序高位优先法（MSD，MostSignificantDigitfirst）::Distribute(Record*Array,intfirst,inti,intr,StaticQueue*queue){MSD方法思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；count[j]=count[j-1]+count[j];template<classRecord>for(inta=0;a<i;a++)先对高位kd-1进行桶式排序，将序列分成若干个桶中可以按千、百、十、个位数字依次进行4次桶式排序01234567828第一趟收集的结果：t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]614738921485637101215530790306h[0]h[1]h[2]h[3]h[4]h[5]h[6]h[7]h[8]h[9]第二趟分配（按次低位i=2）530790921101614485215306637738第二趟收集（让队尾指针t[i]

链接到下一非空队首指针h[i+1]

）530790921101614485215306637738r[0]→r[0]→29第二趟收集的结果：530790921101614485215306637738t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]614738921485637101215530790306h[0]h[1]h[2]h[3]h[4]h[5]h[6]h[7]h[8]h[9]第三趟分配（按最高位i=1）第三趟收集（让队尾指针t[i]链接到下一非空队首指针h[i+1]

）530790921101614485215306637738r[0]→r[0]→排序结束！30基数排序算法template<classRecord>voidRadixSort(Record*Array,intn,intd,intr){ inti,first=0; //first指向静态链中第一个记录 //存放r个桶的静态队列 StaticQueue*queue=newStaticQueue[r]; //建链，初始为next域指向下一个记录 for(i=0;i<n-1;i++) Array[i].next=i+1; Array[n-1].next=-1; //链尾next为空 //对第i个排序码进行分配和收集，一共d趟for(i=0;i<d;i++){ Distribute(Array,first,i,r,queue); Collect(Array,first,r,queue);} delete[]queue;}32分配过程template<classRecord>voidLinkRadixSorter<Record>::Distribute(Record*Array,intfirst,inti,intr,StaticQueue*queue){ //first为静态链中的第一个记录,i为第i个排序码，r为基数

for(intj=0;j<r;j++) //初始化r个队列 queue[j].head=-1;

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

intk=Array[first].key; //取第i位排序码数字 for(inta=0;a<i;a++) k=k/r; k=k%r;

if(queue[k].head==-1) queue[k].head=first; else //否则加到子序列的尾部 Array[queue[k].tail].next=first;

queue[k].tail=first; //first为子序列的尾部

first=Array[first].next; //继续分配下一个记录 }}34收集过程template<classRecord>voidLinkRadixSorter<Record>::Collect(Record*Array,int&first,inti,intr,StaticQueue*queue){ //first为静态链中的第一个记录，i为第i个排序码，r为基数

intlast,k=0; //已收集到的最后一个记录 //找到第一个非空队列

while(queue[k].head==-1)k++;

first=queue[k].head; last=queue[k].tail; while(k<r-1) {//继续收集下一个非空队列

k++;

//找到下一个非空队列 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; //收集完毕}36算法分析空间代价n个记录空间r个子序列的头尾指针Ｏ(n+r)时间代价不需要移动记录本身，只需要修改记录的next指针Ｏ(d·(n+r))时间代价是O(d*n)，但是实际上还是O(nlogn)没有重复编码的情况，需要n个不同的编码来处理他们也就是说，即O(nlogn)378.7各种排序算法的理论和实验时间代价算法最大时间平均时间最小时间辅助空间代价稳定性直接插入排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定二分法插入排序Θ(n2)Θ(n2)Θ(nlogn)Θ(1)稳定冒泡排序Θ(n2)Θ(n2)Θ(n2)Θ(1)稳定改进的冒泡排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定选择排序Θ(n2)Θ(n2)Θ(n2)Θ(1)不稳定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)稳定38测试环境硬件环境：CPU：IntelP42.4G内存：512MDDR软件环境：windowsxp39随机生成待排序数组//设置随机种子inlinevoidRandomize(){srand(1);}//返回一个0到n之间的随机整数值inlineintRandom(intn){returnrand()%(n);}//产生随机数组ELEM*sortarray=newELEM[1000000];for(inti=0;i<1000000;i++) sortarray[i]=Random(32003);t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]7各种排序算法的理论和实验时间代价int*TempArray=newRecord[n]; //临时数组电话：62754785//n为数组长度，d为排序码数，r为基数面值：2<3<4<5<6<7<8<9<10<J<Q<K<A判定树的深度为log(n!)是指已知的最快算法所达到的最佳渐进效率{returnrand()%(n);}先对高位kd-1进行桶式排序，将序列分成若干个桶中面值：2<3<4<5<6<7<8<9<10<J<Q<K<A原始输入数组R的长度为ncount[j]=count[j-1]+count[j];//返回一个0到n之间的随机整数值//存放r个桶的静态队列while(k<r-1&&queue[k].40数组规模10010K1M10K正序10K逆序直接插入排序0.0001751.7266_____0.000313.44187优化插入排序0.0000920.8847_____0.000311.76157二分插入排序0.0000360.