数据结构_09_排序

1、东南大学计算机学院东南大学计算机学院 方效林方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第第九九章章 排序排序本章主要内容本章主要内容n排序的概念排序的概念n插入排序插入排序r顺序插入排序顺序插入排序r折半插入排序折半插入排序r希尔排序希尔排序n快速排序快速排序n选择排序选择排序n归并排序归并排序n分配排序分配排序n内部排序算法分析内部排序算法分析2排序的概念排序的概念n定义定义r将一组杂乱无章的数据按一定规律顺次排列将一组杂乱无章的数据按一定规律顺次排列n数据表数据表(dataList)r待排序数据元素的有限集合待排序数据元素的有限集合n排序码排序码(key)r通常数据

2、元素有多个属性，作为排序依据的属性通常数据元素有多个属性，作为排序依据的属性称为排序码称为排序码学生成绩表，按学号小到大排序，按成绩高到低排序学生成绩表，按学号小到大排序，按成绩高到低排序3排序的概念排序的概念n排序的稳定性排序的稳定性r两数据元素排序码相同，排序前后两元素先后顺两数据元素排序码相同，排序前后两元素先后顺序序若相同，则是稳定的若相同，则是稳定的若不同，则不稳定若不同，则不稳定n内排序和外排序内排序和外排序r内排序内排序所有元素都在存在内存的排序所有元素都在存在内存的排序r外排序外排序数据太多，内存放不下，而存放在外部存储器，排序数据太多，内存放不下，而存放在外部存储器，排序时需

3、要经常在内、外存之间读写数据时需要经常在内、外存之间读写数据41(a)2(b)2(c)3(d)1(a)2(c)2(b) 3(d)2(c)1(a)3(d) 2(b)初始初始排序排序1排序排序2稳定的稳定的不稳定不稳定排序的概念排序的概念n排序的时间开销排序的时间开销r内排序一般用数据比较次数和数据移动次数衡量内排序一般用数据比较次数和数据移动次数衡量r外排序一般用外存的读写次数衡量外排序一般用外存的读写次数衡量(外存慢外存慢)n排序的空间开销排序的空间开销r执行排序算法需要的存储空间执行排序算法需要的存储空间5顺序插入排序顺序插入排序n顺序插入排序算法顺序插入排序算法r将待排序元素，从后向前寻找

4、适当的插入位置，将待排序元素，从后向前寻找适当的插入位置，直到所有元素都插入为止直到所有元素都插入为止6212549 25* 1608初始初始212549 25* 1608第第1步步212549 25* 1608第第2步步212549 25* 1608第第3步步2125 25* 491608第第4步步162125 25* 4908第第5步步插入插入25，25 21，无需移动，无需移动插入插入49，49 25，无需移动，无需移动插入插入25*，25* 49，2125 25* 491608插入插入16，16 49,25*,25,21，162125 25* 490808162125 25* 49插入

5、插入08，08 high，49,25*,25后移，后移，23填入填入162125 25* 4923012345lowmidhigh162125 25* 4923012345low mid high162125 25* 4923012345low mid highmid23,high=mid-1,mid=(low+high)/2mid23,low=mid+1,mid=(low+high)/2162125 25* 4923012345lowmid highmid23,low=mid+1,mid=(low+high)/2折半插入排序折半插入排序n算法分析算法分析r平均情况下，折半搜索比顺序搜索快平均

6、情况下，折半搜索比顺序搜索快r搜索元素搜索元素i需比较需比较 log2i +1次次r总比较次数总比较次数r移动的时间复杂度移动的时间复杂度O(n2)r是稳定的排序算法，需额外一个存储空间是稳定的排序算法，需额外一个存储空间10 1k21021n1i2222kkk332211)ilog(1nnlog*n11)n(log*n12*1)(k2*k2*32*22*122k1k210-比较的时间复杂度比较的时间复杂度O(n*log2n)希尔排序希尔排序n基本思想基本思想r设定不同设定不同gap值，距离值，距离gap的元素放一起插入排序的元素放一起插入排序11212549 25* 1608初始初始2125

7、49 25* 1608第第1步步212549 25* 1608212549 25* 1608gap= n/3 +1 = 3 211608 25* 2549结果结果211608 25* 2549gap= gap/3 +1 = 2 211608 25* 2549081621 25* 2549结果结果081621 25* 2549081621 25* 2549gap= gap/3 +1 = 1 结果结果第第2步步第第3步步最后最后1步是步是n个元素进行插入排序个元素进行插入排序是不是很慢？是不是很慢？希尔排序希尔排序n算法分析算法分析r设定不同设定不同gap值，距离值，距离gap的元素放一起插入排序

8、的元素放一起插入排序gap值越来越小，由于前面的排序过程，使得大多数值越来越小，由于前面的排序过程，使得大多数数据已经基本有序，因此希尔排序速度仍然很快数据已经基本有序，因此希尔排序速度仍然很快gap的取值方法有很多种的取值方法有很多种gap= gap/3 +1gap= gap/2 希尔排序复杂度分析很困难，还没有完整的数学分析希尔排序复杂度分析很困难，还没有完整的数学分析统计得出，平均比较和移动次数在统计得出，平均比较和移动次数在n1.25,1.6n1.25内内是是不稳定不稳定的排序算法的排序算法12快速排序快速排序n基本思想基本思想rPartition：任取一元素：任取一元素x为基准为基准

9、(如选第如选第1个个)，小于，小于x的元素放在的元素放在x左边，大于等于左边，大于等于x的元素放在的元素放在x右边右边r对左、右部分递归执行上一步骤直至只有一个元对左、右部分递归执行上一步骤直至只有一个元素素13212549 25* 1608初始初始第第1层层第第2层层第第3层层选选21为基准为基准左部选左部选08，右部选，右部选25*为基准为基准左部选左部选16，右部选，右部选25为基准为基准081621254925*081621 25* 2549081621 25* 2549第第4层层右部选右部选49为基准为基准081621 25* 2549快速排序快速排序nPartition(low,h

10、igh)r初始时基准坐标初始时基准坐标p = low, x=alow=21r从从i=low+1位置开始判断，比位置开始判断，比x小的元素与小的元素与p下一个下一个位置交换，位置交换，p自加自加1r循环直至循环直至i high，最后，最后alow与与ap交换交换14pppipihigh,停止停止ialow与与ap交换交换ai与与ap+1交换交换, p+ai与与ap+1交换交换, p+212549 25* 1608211649 25* 2508211608 25* 2549081621 25* 254915作业：作业：对数据对数据aN进行快速排序的程序进行快速排序的程序qsort(a , 0, n

11、-1)快速排序快速排序n性能分析性能分析r快速排序是一个递归算法快速排序是一个递归算法1621081625*2549081621 25* 2549递归树递归树快速排序快速排序n性能分析性能分析r快速排序的趟数取决于递归树的深度快速排序的趟数取决于递归树的深度r若每次选取的基准可将序列划分成长度相近的左若每次选取的基准可将序列划分成长度相近的左、右两部分，则下一层将对两个长度减半的序列、右两部分，则下一层将对两个长度减半的序列排序排序设原序列有设原序列有n个元素，选基准和划分所需时间为个元素，选基准和划分所需时间为O(n)设整个快速排序所需时间为设整个快速排序所需时间为T(n)，则有：，则有：T

12、(n) cn + 2T(n/2) / c 是一个常数是一个常数 cn + 2(cn/2 + 2T(n/4) = 2cn + 4T(n/4) 2cn + 4(cn/4 +2T(n/8) = 3cn + 8T(n/8) cn log2n + nT(1) = O(nlog2n )1721081625*2549快速排序快速排序n性能分析性能分析r快速排序平均计算时间为快速排序平均计算时间为O(nlog2n)r平均计算时间是所有内部排序方法中最好的平均计算时间是所有内部排序方法中最好的r递归算法每层需保存递归调用的指针和参数递归算法每层需保存递归调用的指针和参数r平均情况下平均情况下最大递归层数为最大递

13、归层数为 log2(n+1) 存储开销为存储开销为O(log2n)18快速排序快速排序n性能分析性能分析r最坏情况最坏情况单枝树，每次划分只得到比上一次少一个元素的序列单枝树，每次划分只得到比上一次少一个元素的序列比较次数比较次数递归树有递归树有n层，存储开销为层，存储开销为O(n)快速排序是不稳定的算法快速排序是不稳定的算法1921081625*25492n1)n(n21i)(n21n1i快速排序快速排序n改进算法改进算法r快速排序对快速排序对长度很小的序列长度很小的序列排序并不比直接插入排序并不比直接插入快快r长度取长度取525时，直接插入法比快速排序法快时，直接插入法比快速排序法快10%

14、r改进方法改进方法1：在快速排序递归过程中，当序列长度小于一定值时，在快速排序递归过程中，当序列长度小于一定值时，使用直接插入排序法使用直接插入排序法r改进方法改进方法2：在快速排序递归过程中，当序列长度小于一定值时，在快速排序递归过程中，当序列长度小于一定值时，退出排序退出排序得到一个整体上几乎已经排好序的序列得到一个整体上几乎已经排好序的序列对这个几乎已经排好序的序列使用直接插入排序法对这个几乎已经排好序的序列使用直接插入排序法20快速排序快速排序n改进算法改进算法r基准元素的选取对算法性能有很大影响基准元素的选取对算法性能有很大影响r改进方法改进方法1：可随机选择一个元素作为基准，避免最

15、坏情况发生可随机选择一个元素作为基准，避免最坏情况发生r改进方法改进方法2：取左端点、右端点、中点取左端点、右端点、中点(mid= (left+right)/2 )这三这三个元素中的中间值作为基准个元素中的中间值作为基准21212549 25* 163508左端点左端点右端点右端点中点中点取取21，25*，08三个元素中的三个元素中的21为基准为基准选择排序选择排序n直接选择排序直接选择排序r在待排序序列中选择最小的元素在待排序序列中选择最小的元素xrx与第一个元素对换与第一个元素对换r剔除剔除x，对剩下元素执行以上步骤，对剩下元素执行以上步骤22212549 25* 1608初始初始0825

16、49 25* 1621第第1步步081649 25* 2521第第2步步081621 25* 2549第第3步步081621 25* 2549第第4步步081621 25* 2549第第5步步选择排序选择排序n直接选择排序直接选择排序r算法分析算法分析设有设有n个元素，第个元素，第i趟比较次数为趟比较次数为n-i-1次次总比较次数为总比较次数为移动次数移动次数最好情况为最好情况为0最坏情况为最坏情况为3(n-1)直接选择排序是不稳定算法直接选择排序是不稳定算法232n0i21)n(n1)i(nKCN堆排序堆排序n算法思想算法思想r建立最大堆建立最大堆r循环执行以下步骤，直至所有元素出堆循环执行

17、以下步骤，直至所有元素出堆每次堆顶元素每次堆顶元素(即最大元素即最大元素)与堆中最后一个元素交换与堆中最后一个元素交换剔除最大元素后调整为最大堆剔除最大元素后调整为最大堆49082525* 1621i=221 25 4925*16 08最后一元素的父节点最后一元素的父节点i=2开始调整开始调整i=121 25 4925*16 08调整调整i=1i=0调整调整i=021 25 4925*16 0849082525* 162149082525* 1621形成最大堆形成最大堆49 25 2125*16 0821082525* 1649堆排序堆排序n算法思想算法思想r建立最大堆建立最大堆r循环执行以下

18、步骤，直至所有元素出堆循环执行以下步骤，直至所有元素出堆每次堆顶元素每次堆顶元素(即最大元素即最大元素)与堆中最后一个元素交换与堆中最后一个元素交换剔除最大元素后调整为最大堆剔除最大元素后调整为最大堆堆顶堆顶49与堆尾与堆尾08交换交换49 25 2125*16 08212525* 164908214925*0816252525*21 08 16 49虚线内调整为最大堆虚线内调整为最大堆堆顶堆顶25与堆尾与堆尾16交换交换虚线内调整为最大堆虚线内调整为最大堆214916082525*25*16 21 08 25 49堆顶堆顶25*与堆尾与堆尾08交换交换虚线内调整为最大堆虚线内调整为最大堆堆排

19、序堆排序n算法思想算法思想r建立最大堆建立最大堆r循环执行以下步骤，直至所有元素出堆循环执行以下步骤，直至所有元素出堆每次堆顶元素每次堆顶元素(即最大元素即最大元素)与堆中最后一个元素交换与堆中最后一个元素交换剔除最大元素后调整为最大堆剔除最大元素后调整为最大堆491625* 252121 16 0825*25 49堆顶堆顶21与堆尾与堆尾08交换交换虚线内调整为最大堆虚线内调整为最大堆084925* 2516 08 2125*25 49堆顶堆顶16与堆尾与堆尾08交换交换虚线内调整为最大堆虚线内调整为最大堆2108164925* 2508 16 2125*25 49虚线内调整为最大堆虚线内调

20、整为最大堆211608堆排序堆排序n堆排序算法分析堆排序算法分析r建立最大堆建立最大堆设堆中有设堆中有n个元素个元素, 对应完全二叉树有对应完全二叉树有k层层(2k-1n2k)第第i层向下调整移动距离最大为层向下调整移动距离最大为(k-i), 第第i层节点数为层节点数为2i-1总移动次数总移动次数r循环弹出堆顶元素循环弹出堆顶元素执行执行n-1次向下调整，每次调整距离次向下调整，每次调整距离 log2(n+1) 总调整时间总调整时间O(nlog2n) ) )( (k kn nO O 1k1i1- ii22堆排序算法的计算时间复杂度为堆排序算法的计算时间复杂度为O(nlog2n)是不稳定排序是不

21、稳定排序归并排序归并排序n算法思想算法思想r将序列分成两个长度相等的子序列将序列分成两个长度相等的子序列r分别对两个子序列排序分别对两个子序列排序r将排好序的两个子序列合并将排好序的两个子序列合并28212549 25*1608314121 25 4925*16 08 31 4121 25 4925*16 08 31 4121 254925*16 0831 41212549 25*1608314108 16 21 2525*31 41 4921 2525*4908 16 31 4121 2525*4908 1631 41归并排序归并排序n算法分析算法分析r计算时间包括计算时间包括对两个子序列分

22、别排序时间对两个子序列分别排序时间归并的时间归并的时间rT(n) = cn+2T(n/2) = O(nlog2n)r最好、最坏、平均时间复杂度均为最好、最坏、平均时间复杂度均为O(nlog2n)r是稳定排序是稳定排序29桶式排序桶式排序n基本思想基本思想r输入：在输入：在0,1)区间内均匀分布的随机序列区间内均匀分布的随机序列将区间将区间0,1)划分成一系列桶划分成一系列桶(等长子区间等长子区间)，如，如0, 0.1), 0.1, 0.2), , 0.9, 1)对属于桶内的序列分别排序，按桶的编号依次输出对属于桶内的序列分别排序，按桶的编号依次输出300123456789.72 .78.12

23、.17.21 .23 .26.39.68.94.78.17.39.26.72.94.21.12.23.680123456789.78 .72.17 .12.26 .21 .23.39.68.94桶式排序桶式排序n算法分析算法分析r整个桶排序时间复杂度为整个桶排序时间复杂度为将元素分配到各个桶中的时间复杂度为将元素分配到各个桶中的时间复杂度为O(n)假设每个桶中序列使用直接插入排序，时间复杂度为假设每个桶中序列使用直接插入排序，时间复杂度为O(ni2)r极限情况下，每个桶放一个元素，桶排序最好效极限情况下，每个桶放一个元素，桶排序最好效率为率为O(n)31)O(n)O(nO(n)2n1i2i 基

24、数排序基数排序n多排序码排序多排序码排序r花色：花色： r面值：面值：2345678910JQKAr排成以下序列就是多排序码排序排成以下序列就是多排序码排序 2, , A, 2, , A, 2, , A, 2, , Ar排序后的有序序列称为字典有序序列排序后的有序序列称为字典有序序列可先按花色排序，再按字母排序可先按花色排序，再按字母排序也可先按字母排序，再按花色排序也可先按字母排序，再按花色排序32基数排序基数排序n多排序码排序多排序码排序r最高位优先最高位优先(MSD, Most Significant Digit first)按第按第1排序码排序，会分成若干组排序码排序，会分成若干组递归

25、递归对各组按第对各组按第2,3,d排序码排序排序码排序最后把所有子组元素依次连接起来形成有序序列最后把所有子组元素依次连接起来形成有序序列r最低位优先最低位优先(LSD, Least Significant Digit first)按第按第d排序码排序码(最低位最低位)排序排序对上一排序结果按第对上一排序结果按第d-1排序码排序码(次低位次低位)排序排序对上一排序结果按第对上一排序结果按第d-2排序码排序，以此类推，直到排序码排序，以此类推，直到按第按第1排序码完成排序，可得最终排序结果排序码完成排序，可得最终排序结果33基数排序基数排序n多排序码排序多排序码排序r最高位优先最高位优先(MSD

26、, Most Significant Digit first)按第按第1排序码排序，会分成若干组排序码排序，会分成若干组递归递归对各组按第对各组按第2,3,d排序码排序排序码排序最后把所有子组元素依次连接起来形成有序序列最后把所有子组元素依次连接起来形成有序序列34332 633 059 589 232 664 179 457 825 714 405 361179 232 332, 361 457, 405 589633,664714 82505912345678903323610 1 243567 8 94574051 2 3 465708 96336640 1 243567 8 9基数排序基数排序n最低位优先最低位优先(LSD)r按第按第d排序码排序码(最低位最低位)排序排序r对上一排序结果按第对上一排序结果按第d-1排序码排序码(次低位次低位)排序排序r对上一排序结果按第对上一排序结果按第d-2排序码排序，以此类推，直到按排序码排序，以此类推，直到按第第1排序码完成排序，可得最终排序结果排序码完成排序，可得最终排序结果33263358923266417945782540536101234567893613326335898251796644052324573613322326336648254054575891790123456789361332 232 63