数据结构与算法内排序_第1页
数据结构与算法内排序_第2页
数据结构与算法内排序_第3页
数据结构与算法内排序_第4页
数据结构与算法内排序_第5页
已阅读5页,还剩141页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

大纲8.1排序问题的基本概念8.2插入排序(Shell排序)8.3选择排序(堆排序)8.3交换排序8.4.1冒泡排序8.4.2快速排序8.5归并排序8.6分配排序和索引排序8.7排序算法的时间代价8.8内排序知识点总结数据结构与算法内排序全文共146页,当前为第1页。8.1基本概念记录(Record):结点,进行排序的基本单位关键码(Key):唯一确定记录的一个或多个域排序码(SortKey):作为排序运算依据的一个或多个域序列(Sequence):线性表由记录组成数据结构与算法内排序全文共146页,当前为第2页。什么是排序?排序将序列中的记录按照排序码顺序排列起来排序码域的值具有不减(或不增)的顺序内排序整个排序过程在内存中完成数据结构与算法内排序全文共146页,当前为第3页。排序问题给定一个序列R={r1,r2,…,rn}其排序码分别为k={k1,k2,…,kn}排序的目的:将记录按排序码重排形成新的有序序列R’={r’1,r’2,…,r’n}相应排序码为k’={k’1,k’2,…,k’n}排序码的顺序其中k’1≤k’2≤…≤k’n,称为不减序或k’1≥k’2≥…≥k’n

,称为不增序数据结构与算法内排序全文共146页,当前为第4页。正序vs.逆序“正序”序列:待排序序列正好符合排序要求“逆序”序列:把待排序序列逆转过来,正好符合排序要求例如,要求不升序列0812349696341208逆序!正序!数据结构与算法内排序全文共146页,当前为第5页。排序的稳定性稳定性存在多个具有相同排序码的记录排序后这些记录的相对次序保持不变例如,

341234’0896081234

34’96

稳定!数据结构与算法内排序全文共146页,当前为第6页。排序的稳定性稳定性存在多个具有相同排序码的记录排序后这些记录的相对次序保持不变例如,

341234’0896081234’

3496

不稳定!数据结构与算法内排序全文共146页,当前为第7页。稳定的形式化证明不稳定,反例说明

341234’0896081234’

3496数据结构与算法内排序全文共146页,当前为第8页。排序算法的衡量标准时间代价:记录的比较和移动次数空间代价算法本身的繁杂程度数据结构与算法内排序全文共146页,当前为第9页。8.2插入排序8.2.1直接插入排序8.2.2Shell排序数据结构与算法内排序全文共146页,当前为第10页。数据结构与算法内排序全文共146页,当前为第11页。插入排序动画1234’322964453478数据结构与算法内排序全文共146页,当前为第12页。插入排序算法template<classRecord>voidImprovedInsertSort(RecordArray[],intn){//Array[]为待排序数组,n为数组长度

RecordTempRecord; //临时变量

for(inti=1;i<n;i++){ //依次插入第i个记录

TempRecord=Array[i]; //从i开始往前寻找记录i的正确位置

intj=i-1;//将那些大于等于记录i的记录后移

while((j>=0)&& (Compare::lt(TempRecord,Array[j]))){ Array[j+1]=Array[j]; j=j-1; } //此时j后面就是记录i的正确位置,回填

Array[j+1]=TempRecord; }}next数据结构与算法内排序全文共146页,当前为第13页。算法分析稳定空间代价:Θ(1)时间代价:最佳情况:n-1次比较,2(n-1)次移动,Θ(n)最差情况:比较和交换次数为平均情况:Θ(n2)数据结构与算法内排序全文共146页,当前为第14页。8.2.2Shell排序直接插入排序的两个性质:在最好情况(序列本身已是有序的)下时间代价为Θ(n)对于短序列,直接插入排序比较有效Shell排序有效地利用了直接插入排序的这两个性质数据结构与算法内排序全文共146页,当前为第15页。Shell排序算法思想先将序列转化为若干小序列,在这些小序列内进行插入排序逐渐扩大小序列的规模,而减少小序列个数,使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序,从而完成排序数据结构与算法内排序全文共146页,当前为第16页。shell排序动画1234’322964453478next数据结构与算法内排序全文共146页,当前为第17页。“增量每次除以2递减”的Shell排序template<classRecord>voidShellSort(RecordArray[],intn){//Shell排序,Array[]为待排序数组,n为数组长度

inti,delta; for(delta=n/2;delta>0;delta/=2) //增量delta每次除以2递减

for(i=0;i<delta;i++) //分别对delta个子序列进行插入排序

ModInsSort(&Array[i],n-i,delta);//“&”传Array[i]的地址,待处理数组长度为n-i

//如果增量序列不能保证最后一个delta间距为1,可以安排下面这个扫尾性质的插入排序//ModInsSort(Array,n,1);}数据结构与算法内排序全文共146页,当前为第18页。针对增量而修改的插入排序算法template<classRecord>voidModInsSort(RecordArray[],intn,intdelta){ //修改的插入排序算法,参数delta表示当前的增量

inti,j; for(i=delta;i<n;i+=delta) //对子序列中第i个记录,寻找合适的插入位置

for(j=i;j>=delta;j-=delta){ //j以dealta为步长向前寻找逆置对进行调整

if(Array[j]<Array[j-delta]) //逆置对

swap(Array,j,j-delta); //交换Array[j]和Array[j-delta] elsebreak; }}数据结构与算法内排序全文共146页,当前为第19页。算法分析不稳定空间代价:Θ(1)增量每次除以2递减,时间代价:Θ(n2)选择适当的增量序列,可以使得时间代价接近Θ(n)数据结构与算法内排序全文共146页,当前为第20页。Shell排序选择增量序列增量每次除以2递减”时,效率仍然为Θ(n2)问题:选取的增量之间并不互质间距为2k-1的子序列都是由那些间距为2k的子序列组成的上一轮循环中这些子序列都已经排过序了,导致处理效率不高

数据结构与算法内排序全文共146页,当前为第21页。Hibbard增量序列{2k-1,2k-1-1,…,7,3,1},Shell(3)和Hibbard增量序列的Shell排序的效率可以达到Θ(n3/2)选取其他增量序列还可以更进一步减少时间代价数据结构与算法内排序全文共146页,当前为第22页。8.3选择排序8.3.1直接选择排序选出剩下的未排序记录中的最小记录,然后直接与数组中第i个记录交换,比冒泡排序减少了移动次数8.3.2堆排序堆排序:基于最大值堆来实现数据结构与算法内排序全文共146页,当前为第23页。直接选择排序动画1234’322964453478next数据结构与算法内排序全文共146页,当前为第24页。直接选择排序template<classRecord>voidSelectSort(RecordArray[],intn){

//依次选出第i小的记录,即剩余记录中最小的那个

for(inti=0;i<n-1;i++){ //首先假设记录i就是最小的

intSmallest=i; //开始向后扫描所有剩余记录

for(intj=i+1;j<n;j++) //如果发现更小的记录,记录它的位置

if(Compare::lt(Array[j],Array[Smallest])) Smallest=j; //将第i小的记录放在数组中第i个位置

swap(Array,i,Smallest); }}数据结构与算法内排序全文共146页,当前为第25页。直接选择排序性能分析不稳定空间代价:Θ(1)时间代价:比较次数:Θ(n2),与冒泡排序一样交换次数:n-1总时间代价:Θ(n2)数据结构与算法内排序全文共146页,当前为第26页。8.3.2堆排序选择类内排序直接选择排序:直接从剩余记录中线性查找最大记录堆排序:基于最大值堆来实现,效率更高选择类外排序置换选择排序赢者树、败方树数据结构与算法内排序全文共146页,当前为第27页。最大值堆排序过程示意图

78344534’122932数据结构与算法内排序全文共146页,当前为第28页。最大值堆排序过程示意图

32344534’122978数据结构与算法内排序全文共146页,当前为第29页。最大值堆排序过程示意图

453434’32122978数据结构与算法内排序全文共146页,当前为第30页。最大值堆排序过程示意图

343234’45122978数据结构与算法内排序全文共146页,当前为第31页。堆排序算法template<classRecord>voidsort(RecordArray[],intn){ inti; MaxHeap<Record>max_heap= MaxHeap<Record>(Array,n,n);//建堆

for(i=0;i<n-1;i++) //依次找出剩余记录中的最大记录,即堆顶

max_heap.RemoveMax(); //算法操作n-1次,最小元素不需要出堆}数据结构与算法内排序全文共146页,当前为第32页。算法分析建堆:Θ(n)删除堆顶:Θ(logi)一次建堆,n次删除堆顶总时间代价为Θ(nlogn)空间代价为Θ(1)数据结构与算法内排序全文共146页,当前为第33页。8.4交换排序8.4.1冒泡排序8.4.2快速排序数据结构与算法内排序全文共146页,当前为第34页。8.4.1冒泡排序算法思想不停地比较相邻的记录,如果不满足排序要求,就交换相邻记录,直到所有的记录都已经排好序检查每次冒泡过程中是否发生过交换,如果没有,则表明整个数组已经排好序了,排序结束避免不必要的比较数据结构与算法内排序全文共146页,当前为第35页。冒泡排序动画1234’322964783445next数据结构与算法内排序全文共146页,当前为第36页。冒泡排序算法template<classRecord>voidBubbleSort(RecordArray[],intn){ //优化的冒泡排序,Array[]为待排序数组,n为数组长度

boolNoSwap; //是否发生了交换的标志

inti,j; for(i=0;i<n-1;i++){ NoSwap=true; //标志初始为真

for(j=n-1;j>i;j--)

数据结构与算法内排序全文共146页,当前为第37页。冒泡排序算法for(j=n-1;j>i;j--) if(Array[j]<Array[j-1]){ //判断(Array[j-1],Array[j])是否逆置

swap(Array,j,j-1);//交换逆置对Array[j],Array[j-1] NoSwap=false; //发生了交换,标志变为假

}

if(NoSwap)//如果没发生过交换,表示已排好序,结束算法

return; }}数据结构与算法内排序全文共146页,当前为第38页。算法分析稳定空间代价:Θ(1)时间代价:比较次数:交换次数最多为Θ(n2),最少为0,平均为Θ(n2)。最大,平均时间代价均为Θ(n2)。最小时间代价为Θ(n):最佳情况下只运行第一轮循环数据结构与算法内排序全文共146页,当前为第39页。8.4.2快速排序算法思想:选择轴值(pivot)将序列划分为两个子序列L和R,使得L中所有记录都小于或等于轴值,R中记录都大于轴值对子序列L和R递归进行快速排序20世纪十大算法(Computingin7.1962London的ElliotBrothersLtd的TonyHoare提出的快速排序

基于分治法的排序:快速、归并数据结构与算法内排序全文共146页,当前为第40页。分治策略的基本思想分治策略的实例BST查找、插入、删除算法快速排序、归并排序二分检索主要思想划分求解子问题(子问题不重叠)综合解数据结构与算法内排序全文共146页,当前为第41页。快速排序分治思想2534453234’1229642529122934’34453264253412251234’64453464最终排序结果:1225293234’344564next45数据结构与算法内排序全文共146页,当前为第42页。轴值选择尽可能使L,R长度相等选择策略:选择最左边记录随机选择选择平均值数据结构与算法内排序全文共146页,当前为第43页。分割过程(Partition)整个快速排序的关键,轴值位于正确位置,分割后使得L中所有记录位于轴值左边R中记录位于轴值右边数据结构与算法内排序全文共146页,当前为第44页。一次分割过程1225322964453434’选择轴值并存储轴值最后一个元素放到轴值位置初始化下标i,j,分别指向头尾i递增直到遇到比轴值大的元素,将此元素覆盖到j的位置;j递减直到遇到比轴值小的元素,将此元素覆盖到i的位置重复上一步直到i==j,将轴值放到i的位置,完毕64ij3234294512next数据结构与算法内排序全文共146页,当前为第45页。快速排序算法template<classRecord>voidQuickSort(RecordArray[],intleft,intright){//Array[]为待排序数组,left,right分别为数组两端

if(right<=left) return; //如果子序列中只有0或1个记录,就不需排序

intpivot=SelectPivot(left,right); //选择轴值

swap(Array,pivot,right); //分割前先将轴值放到数组末端

pivot=Partition(Array,left,right);//分割后轴值已到达正确位置

//对左子序列进行递归快速排序QuickSort(Array,left,pivot-1);

//对右子序列进行递归快速排序QuickSort(Array,pivot+1,right); }数据结构与算法内排序全文共146页,当前为第46页。轴值选择函数intSelectPivot(intleft,intright){ //选择轴值,参数left,right分别表示序列的左右端下标

return(left+right)/2; //选择中间记录作为轴值}数据结构与算法内排序全文共146页,当前为第47页。分割函数template<classRecord>intPartition(RecordArray[],intleft,intright){//分割函数,分割后轴值已到达正确位置

intl=left;//l为左指针,r为右指针

intr=right; RecordTempRecord=Array[r]; //将轴值存放在临时变量中

数据结构与算法内排序全文共146页,当前为第48页。

while(l!=r){//开始分割,l,r不断向中间移动,直到相遇

//l指针向右移动,越过那些小于等于轴值的记录//直到找到一个大于轴值的记录

while(Array[l]<=TempRecord&&r>l) //“<=”也可以改写为“<”,但增加记录移动

l++; if(l<r){//若l,r尚未相遇,将逆置元素换到右边空位

Array[r]=Array[l]; r--; //r指针向左移动一步

}

数据结构与算法内排序全文共146页,当前为第49页。

//r指针向左移动,越过那些大于等于轴值的记录 //直到找到一个小于轴值的记录

while(Array[r]>=TempRecord&&r>l) //“>=”也可以改写为“>”,但增加记录移动

r--; if(l<r){//若l,r尚未相遇,将逆置元素换到左边空位

Array[l]=Array[r]; l++; //l指针向右移动一步

} } //endwhile Array[l]=TempRecord; //把轴值回填到分界位置l上

returnl; //返回分界位置l}数据结构与算法内排序全文共146页,当前为第50页。时间代价长度为n的序列,时间为T(n)T(0)=T(1)=1选择轴值时间为常数分割时间为cn分割后长度分别为

i和

n-i-1对子序列进行快速排序所需时间分别为T(i)和T(n-1-i)求解递推方程数据结构与算法内排序全文共146页,当前为第51页。最差情况总的时间代价为:数据结构与算法内排序全文共146页,当前为第52页。最佳情况数据结构与算法内排序全文共146页,当前为第53页。logn次分割

数据结构与算法内排序全文共146页,当前为第54页。假设在每次分割时,轴值处于最终排序好的数组中位置的概率是一样的也就是说,轴值将数组分成长度为0和n-1,1和n-2,…的子序列的概率是相等的,都为1/n数据结构与算法内排序全文共146页,当前为第55页。

T(i)和T(n-1-i)的平均值均为数据结构与算法内排序全文共146页,当前为第56页。数据结构与算法内排序全文共146页,当前为第57页。算法分析最差情况:时间代价:Θ(n2)空间代价:Θ(n)最佳情况:时间代价:Θ(nlogn)空间代价:Θ(logn)平均情况:时间代价:Θ(nlogn)空间代价:Θ(logn)

数据结构与算法内排序全文共146页,当前为第58页。算法分析(续)不稳定可能优化:轴值选择RQS小子串不递归消除递归数据结构与算法内排序全文共146页,当前为第59页。教材上的优化快速排序子数组小于某个长度(阈值n=28)时,不递归块与块之间有序最后对整个数组进行一次插入排序数据结构与算法内排序全文共146页,当前为第60页。8.5归并排序算法思想简单地将原始序列划分为两个子序列分别对每个子序列递归排序最后将排好序的子序列合并为一个有序序列,即归并过程数据结构与算法内排序全文共146页,当前为第61页。(25344532781234’64)(25344532)(781234’64)(2534)(4532)(7812)(34’64)(25)(34)(45)(32)(78)(12)(34’)(64)(2534)(3245)(1278)(34’

64)(25323445)(12

34’6478)(1225323434’456478)先划分再归并归并思想数据结构与算法内排序全文共146页,当前为第62页。两路归并排序template<classRecord>voidMergeSort(RecordArray[],RecordTempArray[],intleft,intright){ //Array为待排序数组,left,right两端

intmiddle; if(left<right){//序列中只有0或1个记录,不用排序

middle=(left+right)/2;//从中间划为两个子序列 //对左边一半进行递归 MergeSort(Array,TempArray,left,middle); //对右边一半进行递归

MergeSort(Array,TempArray,middle+1,right);

Merge(Array,TempArray,left,right,middle); //归并

}}数据结构与算法内排序全文共146页,当前为第63页。归并函数//两个有序子序列都从左向右扫描,归并到新数组template<classRecord>voidMerge(RecordArray[],RecordTempArray[],intleft,intright,intmiddle){ inti,j,index1,index2; for(j=left;j<=right;j++) //将数组暂存入临时数组

TempArray[j]=Array[j]; index1=left; //左边子序列的起始位置

index2=middle+1; //右边子序列的起始位置

i=left; //从左开始归并数据结构与算法内排序全文共146页,当前为第64页。while(index1<=middle&&index2<=right){ //取较小者插入合并数组中

if(TempArray[index1]<=TempArray[index2])//相等时左边优先

Array[i++]=TempArray[index1++]; elseArray[i++]=TempArray[index2++]; }

while(index1<=middle) //只剩左序列,可以直接复制 Array[i++]=TempArray[index1++]; while(index2<=right) //与上个循环互斥,直接复制剩余的右序列 Array[i++]=TempArray[index2++]; }数据结构与算法内排序全文共146页,当前为第65页。(25344532781234’64)(25344532)(781234’64)(2534)(4532)(7812)(34’64)(25)(34)(45)(32)(78)(12)(34’)(64)(2534)(4532)(1278)(6434’)(25323445)(786434’12)(1225323434’456478)先划分再归并R.Sedgewick优化归并思想数据结构与算法内排序全文共146页,当前为第66页。256478323434’4512R.Sedgewick优化归并i1i2k647834’12i1i2k数据结构与算法内排序全文共146页,当前为第67页。优化的归并排序#defineTHRESHOLD28template<classRecord>voidModMergeSort(RecordArray[],RecordTempArray[],intleft,intright){//Array为待排序数组,left,right两端

intmiddle; //如果序列长度大于阈值(28最佳),递归进行归并 if(right-left+1>THRESHOLD){

middle=(left+right)/2;//从中间划为两个子序列

//对左边一半进行递归 ModMergeSort(Array,TempArray,left,middle); 数据结构与算法内排序全文共146页,当前为第68页。优化的归并排序(cont.)

//对右边一半进行递归

ModMergeSort(Array,TempArray,middle+1,right);

//对相邻的有序序列进行归并

ModMerge(Array,TempArray,left,right,middle); }elseInsertSort(&Array[left],right-left+1);

//小长度子序列进行插入排序,“&”传Array[left]的地址}数据结构与算法内排序全文共146页,当前为第69页。优化的归并函数//优化的Sedgwick两个有序子序列归并,右子序列逆置了,都从两端向中间扫描,归并到新数组template<classRecord>voidModMerge(RecordArray[],RecordTempArray[],intleft,intright,intmiddle){ //归并过程

intindex1,index2;//两个子序列的起始位置

inti,j,k; for(i=left;i<=middle;i++) //复制左边的子序列

TempArray[i]=Array[i];数据结构与算法内排序全文共146页,当前为第70页。 //复制右边的子序列,但顺序颠倒过来 for(j=1;j<=right-middle;j++) TempArray[right-j+1]=Array[j+middle]; //开始归并,取较小者插入合并数组中

for(index1=left,index2=right,k=left;k<=right;k++) //为保证稳定性,相等时左边优先 if(TempArray[index1]<=TempArray[index2])

Array[k]=TempArray[index1++]; elseArray[k]=TempArray[index2--];}数据结构与算法内排序全文共146页,当前为第71页。时间代价划分时间两个子序列的排序时间归并时间,n数据结构与算法内排序全文共146页,当前为第72页。T(1)=1归并排序总时间代价也为Θ(nlogn)

数据结构与算法内排序全文共146页,当前为第73页。算法分析空间代价:Θ(n)总时间代价:Θ(nlogn)不依赖于原始数组的输入情况,最大、最小以及平均时间代价均为Θ(nlogn)。数据结构与算法内排序全文共146页,当前为第74页。算法分析(续)稳定优化:同优化的快速排序一样,对基本已排序序列直接插入排序R.Sedgewick优化:归并时从两端开始处理,向中间推进,简化了边界判断数据结构与算法内排序全文共146页,当前为第75页。8.6分配排序和基数排序不需要进行纪录之间两两比较需要事先知道记录序列的一些具体情况数据结构与算法内排序全文共146页,当前为第76页。8.6.1桶式排序事先知道序列中的记录都位于某个小区间段[0,m)内将具有相同值的记录都分配到同一个桶中,然后依次按照编号从桶中取出记录,组成一个有序序列数据结构与算法内排序全文共146页,当前为第77页。待排数组:

第一趟count:后继起始下标:count[i]=count[i-1]+count[i];021100121102344468957389618’1’20123456789++++0123456789数据结构与算法内排序全文共146页,当前为第78页。桶排序示意0211001211023444689511’23678’890123456782待排数组:

第一趟count后继起始下标:收集:7389618’1’20123456789170数据结构与算法内排序全文共146页,当前为第79页。桶式排序算法template<classRecord>voidBucketSort(RecordArray[],intn,intmax){ //Array数组长度为n,所有记录都位于区间[0,max)上

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

int*count=newint[max]; //桶容量计数器,count[i]存储了第i个桶中的记录数

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

TempArray[i]=Array[i];数据结构与算法内排序全文共146页,当前为第80页。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];

//count[i]记录了i+1的开始位置

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

//TempArray[i]放到Array[count[TempArray[i]-1]中}数据结构与算法内排序全文共146页,当前为第81页。算法分析数组长度为n,所有记录区间[0,m)上时间代价:统计计数时:Θ(n+m)输出有序序列时循环n次总的时间代价为Θ(m+n)适用于m相对于n很小的情况空间代价:m个计数器,长度为n的临时数组,Θ(m+n)稳定数据结构与算法内排序全文共146页,当前为第82页。8.6.2基数排序桶式排序只适合m很小的情况当m很大时,可以将一个记录的值即排序码拆分为多个部分来进行比较——基数排序数据结构与算法内排序全文共146页,当前为第83页。基数排序假设长度为n的序列

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

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

K=(kd-1,kd-2,…,k1,k0)数据结构与算法内排序全文共146页,当前为第84页。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称为最低排序码数据结构与算法内排序全文共146页,当前为第85页。例子例如:如果我们要对0到9999之间的整数进行排序将四位数看作是由四个排序码决定,即千、百、十、个位,其中千位为最高排序码,个位为最低排序码。基数r=10。可以按千、百、十、个位数字依次进行4次桶式排序4趟分配排序后,整个序列就排好序了数据结构与算法内排序全文共146页,当前为第86页。基数排序分为两类高位优先法(MSD,MostSignificantDigitfirst)低位优先法(LSD,LeastSignificantDigitfirst)数据结构与算法内排序全文共146页,当前为第87页。黑桃(S)>红心(H)>

方片(D)

>梅花(C)S3HJ

C8

H9S9D3

C1

D7数据结构与算法内排序全文共146页,当前为第88页。MSD方法(递归分治)先按花色:C8

C1

D3D7

HJ

H9S3S9再按面值:C1C8

D3D7

H9HJS3S9LSD方法先按面值:C1S3D3D’7

C’8H9S’9H’J再按花色:C1C’8

D3D’7

H9H’JS3S’9要求稳定排序!S3HJ

C8

H9S9D3

C1

D7数据结构与算法内排序全文共146页,当前为第89页。高位优先法(MSD,MostSignificantDigitfirst)先对高位kd-1进行桶式排序,将序列分成若干个桶中然后对每个桶再按次高位kd-2进行桶式排序,分成更小的桶依次重复,直到对k0排序后,分成最小的桶,每个桶内含有相同的排序码(kd-1,kd-2,…,k1,k0)最后将所有的桶依次连接在一起,成为一个有序序列这是一个分、分、…、分、收的过程数据结构与算法内排序全文共146页,当前为第90页。低位优先法(LSD,LeastSignificantDigitfirst)从最低位k0开始排序对于排好的序列再用次低位k1排序;依次重复,直至对最高位kd-1排好序后,整个序列成为有序的这是一个分、收;分、收;…;分、收的过程比较简单,计算机常用数据结构与算法内排序全文共146页,当前为第91页。基数排序的实现基于顺序存储基于链式存储数据结构与算法内排序全文共146页,当前为第92页。基于顺序存储的基数排序只讨论LSD原始输入数组R的长度为n基数为r排序码个数为d数据结构与算法内排序全文共146页,当前为第93页。数据结构与算法内排序全文共146页,当前为第94页。数据结构与算法内排序全文共146页,当前为第95页。基于数组的基数排序template<classRecord>voidRadixSort(RecordArray[],intn,intd,intr){//n为数组长度,d为排序码个数,r为基

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

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

inti,j,k; intRadix=1;//模进位,用于取Array[j]的第i位数据结构与算法内排序全文共146页,当前为第96页。//分别对第i个排序码进行分配for(i=1;i<=d;i++){

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

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

count[k]++; //相应计数器加1 } 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]个数据结构与算法内排序全文共146页,当前为第97页。 //从数组尾部,把记录收集到相应桶 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 }}数据结构与算法内排序全文共146页,当前为第98页。算法分析空间代价:临时数组,nr个计数器总空间代价Θ(n+r)数据结构与算法内排序全文共146页,当前为第99页。算法分析(续)时间代价桶式排序:Θ(n+r)d次桶式排序Θ(d·(n+r))数据结构与算法内排序全文共146页,当前为第100页。基于静态链的基数排序将分配出来的子序列存放在r个(静态链组织的)队列中链式存储避免了空间浪费情况数据结构与算法内排序全文共146页,当前为第101页。97538859264188’312241225326975988314131225326978888’5988’(c)第一趟收集(b)第一趟分配数据结构与算法内排序全文共146页,当前为第102页。2231419726882226314153598888’975388’594131225326978888’59(e)第二趟收集结果(最终结果)(d)第二趟分配数据结构与算法内排序全文共146页,当前为第103页。静态队列定义classNode{//结点类public: intkey; //结点的关键码值

intnext; //下一个结点在数组中的下标};classStaticQueue{//静态队列类public: inthead; inttail;};数据结构与算法内排序全文共146页,当前为第104页。基于静态链的基数排序//静态链实现的基数排序,n为数组长度,d为排序码个数,r为基数template<classRecord>voidRadixSort(Record*Array,intn,intd,intr){ inti,first=0; //first指向静态链中第一个记录

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

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

Array[i].next=i+1;//静态指针域设为下一个元素的下标

Array[n-1].next=-1;//链尾next为空数据结构与算法内排序全文共146页,当前为第105页。 //对第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); //线性时间整理静态链表,使得数组按下标有序}数据结构与算法内排序全文共146页,当前为第106页。//分配过程,A中存放待排序记录,first为静态链中的第一个记录//i为第i个排序码,r为基数template<classRecord>voidDistribute(Record*Array,intfirst,inti,intr,StaticQueue*queue){intj,k,a,curr=first; for(j=0;j<r;j++) //初始化r个队列

queue[j].head=-1; 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) //若桶空,Array[curr]就是第一个记录

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

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

curr=Array[curr].next;

}}数据结构与算法内排序全文共146页,当前为第107页。//收集过程,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; while(k<r-1){//继续收集下一个非空队列,若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; //收集完毕}数据结构与算法内排序全文共146页,当前为第108页。线性时间整理静态链表template<classRecord>voidAddrSort(Record*Array,intn,intfirst){inti,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;}}数据结构与算法内排序全文共146页,当前为第109页。算法分析空间代价n个记录空间r个子序列的头尾指针O(n+r)时间代价不需要移动记录本身,只需要修改记录的next指针O(d·(n+r))数据结构与算法内排序全文共146页,当前为第110页。空间vs时间速度比较快的排序算法O(nlogn)归并、分配、快速空间消耗都比较大堆空间消耗比较小对于大记录,采用地址排序数据结构与算法内排序全文共146页,当前为第111页。数组vs链表一般用数组静态链表数据结构与算法内排序全文共146页,当前为第112页。8.6.3索引地址排序动态链(new出来的指针)数组建立索引数组(通用)建立静态链表数据结构与算法内排序全文共146页,当前为第113页。索引数组

交换指针,减少交换记录的次数数据结构与算法内排序全文共146页,当前为第114页。索引方法1:结果下标IndexArray[i]存放的是Array[i]中数据应该待的位置。也就是说Array[IndexArray[i]]=Array[i]用另一个数组整理下标01234567排序码2925346434’123245结果2147503629256434’1232344501234567数据结构与算法内排序全文共146页,当前为第115页。索引方法2:结果下标IndexArray[i]存放的是Array[i]中应该摆放的数据位置。也就是说Array[i]=Array[IndexArray[i]]用另一个数组整理下标01234567排序码2925346434’123245结果5106247329256434’12开新数组323445数据结构与算法内排序全文共146页,当前为第116页。不开新数组只利用原Array和IndexArray可以用一个临时空间RecordTempRec;根据IndexArray内容,整理好原Array,使得Array数组按下标有序在O(n)的时间内完成数据结构与算法内排序全文共146页,当前为第117页。顺链整理下标01234567排序码2925346434’123245结果51062473整理2147503629256434’1232344501234567数据结构与算法内排序全文共146页,当前为第118页。得到索引2的方法?一般的排序方法都可以那些赋值(或交换)都换成对index数组的赋值(或交换)举例:插入排序数据结构与算法内排序全文共146页,当前为第119页。template<classRecord,classint_intCompare>voidAddrSort(RecordArray[],intn){ //Array[]为待排序数组,n为数组长度

int*IndexArray=newint[n],TempIndex; inti,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(Compare::lt(Array[IndexArray[j]], Array[IndexArray[j-1]]))

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

数据结构与算法内排序全文共146页,当前为第120页。//根据IndexArray整理Arrayfor(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; }}数据结构与算法内排序全文共146页,当前为第121页。得到索引2的方法?Rank排序静态链表的基数排序数据结构与算法内排序全文共146页,当前为第122页。Rank排序template<classRecord,classint_intCompare>voidRank(Record*array,intlistsize,Record*rank){ for(inti=0;i<listsize;i++) rank[i]=0; for(i=0;i<listsize;i++) for(intj=i+1;j<listsize;j++){ if(Compare::gt(Array[i],array[j]) rank[i]++; else rank[j]++; }}数据结构与算法内排序全文共146页,当前为第123页。8.7排序算法的时间代价8.7.1简单排序算法的时间代价8.7.2排序算法的理论和实验时间8.7.3排序问题的下限数据结构与算法内排序全文共146页,当前为第124页。8.7.1简单排序算法的时间代价比较次数直接插入排序改进的插入排序二分法插入排序冒泡排序改进的冒泡排序选择排序最佳情况Θ(n)Θ(n)Θ(nlogn)Θ(n2)Θ(n)Θ(n2)平均情况Θ(n2)Θ(n2)Θ(nlogn)Θ(n2)Θ(n2)Θ(n2)最差情况Θ(n2)Θ(n2)Θ(nlogn)Θ(n2)Θ(n2)Θ(n2)数据结构与算法内排序全文共146页,当前为第125页。移动次数直接插入排序改进的插入排序二分法插入排序冒泡排序改进的冒泡排序选择排序最佳情况0Θ(n)Θ(n)00Θ(n)平均情况Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n)最差情况Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n)数据结构与算法内排序全文共146页,当前为第126页。总代价直接插入排序改进的插入排序二分法插入排序冒泡排序改进的冒泡排序选择排序最佳情况Θ(n)Θ(n)Θ(nlogn)Θ(n2)Θ(n)Θ(n2)平均情况Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n2)最差情况Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n2)Θ(n2)数据结构与算法内排序全文共146页,当前为第127页。原因一个长度为n序列平均有

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

数据结构与算法内排序全文共146页,当前为第128页。8.7.2排序算法的理论和实验时间算法最大时间平均时间最小时间辅助空间代价稳定性直接插入排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定二分法插入排序Θ(n2)Θ(n2)Θ(nlogn)Θ(1)稳定冒泡排序Θ(n2)Θ(n2)Θ(n2)Θ(1)稳定改进的冒泡排序Θ(n2)Θ(n2)Θ(n)Θ(1)稳定选择排序Θ(n2)Θ(n2)Θ(n2)Θ(1)不稳定数据结构与算法内排序全文共146页,当前为第129页。算法最大时间平均时间最小时间辅助空间代价稳定性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)稳定数据结构与算法内排序全文共146页,当前为第130页。小结n很小或基本有序时插入排序比较有效Shell排序选择增量以3的倍数递减需要保证最后一趟增量为1综合性能快速排序最佳数据结构与算法内排序全文共146页,当前为第131页。测试环境硬件环境:CPU:IntelP43G内存:1G软件环境:windowsxpVisualC++6.0数据结构与算法内排序全文共146页,当前为第132页。随机生成待排序数组//设置随机种子inlinevoidRandomize(){srand(1);}//返回一个0到n之间的随机整数值inlineintRandom(intn){returnrand()%(n);}//产生随机数组ELEM*sortarray=newELEM[1000000];for(inti=0;i<1000000;i++)sortarray[i]=Random(32003);数据结构与算法内排序全文共146页,当前为第133页。时间测试#include<time.h>/*Clockticksmacro-ANSIversion*/#defineCLOCKS_PER_SEC1000clock_ttstart=0;//Timeatbeginning//InitializetheprogramtimervoidSettime(){tstart=clock();}//TheelapsedtimesincelastSettime()doubleGettime(){return(double)((double)clock()-(double)tstart)/(double)CLOCKS_PER_SEC;}数据结构与算法内排序全文共146页,当前为第134页。排序的时间测试Settime();

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

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

print(&array[i],listsize);

}

cout<<"Sortwithlistsize"<<listsize <<",arraysize"<<ARR

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论