数据结构排序.ppt

堆排序算法思想建立最大堆循环执行以下步骤，直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆491625*252121160825*2549堆顶21与堆尾08交换虚线内调整为最大堆084925*2516082125*2549堆顶16与堆尾08交换虚线内调整为最大堆2108164925*2508162125*2549虚线内调整为最大堆211608第26页,共35页，星期六，2024年，5月堆排序堆排序算法分析建立最大堆设堆中有n个元素,对应完全二叉树有k层(2k-1≤n＜2k)第i层向下调整移动距离最大为(k-i),第i层节点数为2i-1总移动次数循环弹出堆顶元素执行n-1次向下调整，每次调整距离?log2(n+1)?总调整时间O(nlog2n)堆排序算法的计算时间复杂度为O(nlog2n)是不稳定排序第27页,共35页，星期六，2024年，5月归并排序算法思想将序列分成两个长度相等的子序列分别对两个子序列排序将排好序的两个子序列合并21254925*1608314121254925*1608314121254925*1608314121254925*1608314121254925*160831410816212525*314149212525*4908163141212525*4908163141第28页,共35页，星期六，2024年，5月归并排序算法分析计算时间包括对两个子序列分别排序时间归并的时间T(n)=cn+2T(n/2)=O(nlog2n)最好、最坏、平均时间复杂度均为O(nlog2n)是稳定排序第29页,共35页，星期六，2024年，5月桶式排序基本思想输入：在[0,1)区间内均匀分布的随机序列将区间[0,1)划分成一系列桶(等长子区间)，如[0,0.1),[0.1,0.2),…,[0.9,1)对属于桶内的序列分别排序，按桶的编号依次输出0123456789.72.78.12.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第30页,共35页，星期六，2024年，5月桶式排序算法分析整个桶排序时间复杂度为将元素分配到各个桶中的时间复杂度为O(n)假设每个桶中序列使用直接插入排序，时间复杂度为O(ni2)极限情况下，每个桶放一个元素，桶排序最好效率为O(n)第31页,共35页，星期六，2024年，5月基数排序多排序码排序花色：???????面值：2345678910JQKA排成以下序列就是多排序码排序?2,…,?A,?2,…,?A,?2,…,?A,?2,…,?A排序后的有序序列称为字典有序序列可先按花色排序，再按字母排序也可先按字母排序，再按花色排序第32页,共35页，星期六，2024年，5月基数排序多排序码排序最高位优先(MSD,MostSignificantDigitfirst)按第1排序码排序，会分成若干组递归对各组按第2,3,…,d排序码排序最后把所有子组元素依次连接起来形成有序序列最低位优先(LSD,LeastSignificantDigitfirst)按第d排序码(最低位)排序对上一排序结果按第d-1排序码(次低位)排序对上一排序结果按第d-2排序码排序，以此类推，直到按第1排序码完成排序，可得最终排序结果第33页,共35页，星期六，2024年，5月基数排序多排序码排序最高位优先(MSD,MostSignificantDigitfirst)按第1排序码排序，会分成若干组递归对各组按第2,3,…,d排序码排序最后把所有子组元素依次连接起来形成有序序列332633059589232664179457825714405361179232332,361457,405589633,664714825059123456789033236101243567894574051234657