数据结构——第3章排序.ppt

上堂课要点回顾 简单排序算法： u 插入排序 u 冒泡排序 u 选择排序 先进排序算法： u 快速排序 将无序子序列中的一 个或几个 记录“插入插入”到有 序序列中，从而增 加记录 的有序子序列的度。 时间效率： O(nO(n 2 2 ） 空间效率：OO（1 1） 算法的稳定性：稳定稳定 每趟将相邻记录两两比较，并按“前小 后大”（或“前大后小”）规则交换。 每趟结束时，不仅能挤出一个最大值， 若一趟中没有交换发生，还可以提前结 束排序。 时间效率： O(nO(n 2 2 ） 空间效率：O O（1 1） 算法的稳定性：稳定稳定 每一趟比较就找出一个最小（大）值 ，与待排序列最前面的位置互换即可 。 首先，在n个记录中选择最小者放 到r1位置；然后，从剩余的n-1个记 录中选择最小者放到r2位置；如此 进行下去，直到全部有序为止。 时间效率： O(nO(n 2 2 ） 空间效率：OO（1 1） 算法的稳定性：稳定稳定 从待排序列中任取一个元素 (例如取第 一个) 作为中心，所有比它小的元素一 律前放，所有比它大的元素一律后放， 形成左右两个子表；然后再对各子表重 新选择中心元素并依此规则调整，直到 每个子表的元素只剩一个。此时便为有 序序列了。 时间效率： O(nlogO(nlog 2 2 n n） 空间效率：OO（loglog 2 2 n n） 算法的稳定性：不稳定不稳定 1 low high 设 Rs=52 为枢轴。 例： 52 52 52 49 80 36 14 58 61 97 23 75 st high 23 low low 80 highhighhighhigh 14 low low 5252 2 【教学内容】 归并排序；堆排序；基数排序以及各种排序算法比较 【教学要求】 1.熟悉快速排序、归并排序、堆排序和基数排序的思想 排序过程及其依据的原则，对给定关键字的序列能够熟练 写出各种排序算法的排序过程。 2. 掌握各种排序方法的时间复杂度。了解各种排序算 法的平均情况和最坏情况的时间性能。 3. 掌握各种排序方法的优缺点比较及排序方法的选择。 【重点与难点】 快速排序、归并排序、堆排序和基数排序算法的排序 过程和算法；各种排序算法的平均情况和最坏情况的时间 性能及比较。 3 3.3.2 归并排序 归并排序的基本思想是：归并排序的基本思想是：将两个（或以上）的有序将两个（或以上）的有序 表组成新的有序表。表组成新的有序表。 更实际的意义：更实际的意义：可以把一个长度为可以把一个长度为n n 的无序序列看成是的无序序列看成是 n n 个个 长度为长度为 1 1 的有序子序列的有序子序列 ，首先做两两归并，得到，首先做两两归并，得到 n n / 2/ 2 个个 长度为长度为 2 2 的子序列的子序列 ；再做两两归并，；再做两两归并，如此重复，直到，如此重复，直到 最后得到一个长度为最后得到一个长度为 n n 的有序序列。的有序序列。 例：例：关键字序列T= （21，25，49，25*，93，62， 72，08，37，16，54），请给出归并排序的具体实 现过程。 4 2121252525*25* 93936262727208083737161654544949 2121 252525*25* 49496262 93930808 72721616 37375454 1616 3737 5454 2121 2525 25*25* 49490808 6262 7272 9393 0808 2121 2525 25*25* 4949 6262 7272 9393 0808 1616 2121 2525 25*25* 3737 4949 5454 6262 7272 9393 lenlen=1=1 lenlen=2=2 lenlen=4=4 lenlen=8=8 lenlen=16=16 1616 3737 5454 整个归并排序仅需整个归并排序仅需 loglog 2 2 n n 趟趟 5 void MSort (SR， / 当len=1时返回 else m=(s+t)/2; / 将SR st平分为SR sm和SR m+1t MSort (SR， / 将SR 一分为二, 2分为4 / 递归地将SR sm归并为有序的TR2sm MSort (SR， / 递归地将SR m+1t归并为有序的TR2m+1t MergeMerge(TR2， TR1， s, m, t ); / 将TR2 sm和TR2 m+1t归并到TR1 st / MSort 递归形式的两路归并排序算法递归形式的两路归并排序算法: : 参见教材参见教材P54P54 ( (一路无序变为有序一路无序变为有序) ) 简言之，先由“长”无序变成“短”有序， 再从“短”有序归并为“长”有序。 初次调用时为（L, L, 1, length） 6 一趟归并排序算法一趟归并排序算法: : ( (两路有序并为一路两路有序并为一路) ) 参见教材参见教材P53P53 void Merge Merge (SR， i0; - - i ) / / 把把r r 1length1length 建成大根堆建成大根堆 HeapAdjust(r, i, length ); / / 使使r r ilengthilength 成为大根堆成为大根堆 建堆算法建堆算法 ( (其实是堆排序算法中的第一步）其实是堆排序算法中的第一步） 这是针对结点 i 的堆调整函数，其含义是：从结点i开 始到堆尾为止，自上向下比较，如果子女的值大于双 亲结点的值，则互相交换，即把局部调整为大根堆。 14 针对结点 i 的堆调整函数HeapAdjust如下： HeapAdjust(r, i, m ) current=i; child=2*i; temp=ri; while(child=rchild.key)breack; else rcurrent=rchild; current= child; child=2* child; rcurrent=temp; / HeapAdjust /temp是根，child是其左孩子 /检查是否到达当前堆尾 /让child指向两子女中的大者 /根大则不必调整，结束整个函数 /否则子女中的大者上移 /并继续向下整理！并继续向下整理！ /直到自下而上都满足堆定义，再安置老根 从结点i开始到当前堆尾m为止，自上向下比较，如果子女的 值大于双亲结点的值，则互相交换，即把局部调整为大根堆。 /将根下降到子女位置 15 关键：关键：将堆的当前顶点输出后，如何将剩余序将堆的当前顶点输出后，如何将剩余序 列重新调整为堆？列重新调整为堆？ 方法：方法：将当前顶点将当前顶点与堆尾记录交换与堆尾记录交换，然后，然后仿仿建建 堆动作重新调整，如此反复直至排序结堆动作重新调整，如此反复直至排序结 束。束。 3. 3. 怎样进行堆排序？怎样进行堆排序？ 16 27 55 73 12 40 27 55 73 12 40 9898 交换交换 1 1号与号与 6 6 号记录号记录 9898 5555 1212 7373 40402727 1 2 3 456 98 55 73 12 40 2798 55 73 12 40 27 初建大顶堆初建大顶堆 5555 12124040 7373 1 3 654 2 2727 9898 例：例：对刚才建好的大顶堆进行排序：对刚才建好的大顶堆进行排序： 17 40 55 27 12 40 55 27 12 73 9873 98 交换交换 1 1号与号与 5 5 号记录号记录从从 1 1 号到号到 5 5 号号 重新重新 调整为大顶堆调整为大顶堆 4040 5555 12127373 2727 9898 1 3 654 2 73 55 27 12 40 73 55 27 12 40 9898 5555 12124040 7373 1 3 654 2 2727 9898 7373 2727 18 12 40 27 12 40 27 5555 73 9873 98 交换交换 1 1号与号与 4 4 号记录号记录从从 1 1 号到号到 4 4 号号 重新重新 调整为大顶堆调整为大顶堆 4040 5555 12127373 2727 9898 1 3 654 2 55 40 27 12 55 40 27 12 7373 9898 4040 5555 1212 4040 55557373 2727 9898 1 3 654 2 19 1212 4040 55557373 2727 9898 1 3 654 2 27 12 27 12 4040 5555 73 9873 98 交换交换 1 1号与号与 3 3 号记录号记录从从 1 1 号到号到 3 3 号号 重新重新 调整为大顶堆调整为大顶堆 40 12 27 40 12 27 5555 7373 9898 4040 1212 2727 1212 55557373 4040 9898 1 3 654 2 20 27 12 27 12 4040 5555 73 9873 98 交换交换 1 1号与号与 2 2 号记录号记录从从 1 1 号到号到 2 2 号号 重新重新 调整为大顶堆（调整为大顶堆（已已 经是，无需调整经是，无需调整） 2727 1212 55557373 4040 9898 1 3 654 2 12 12 27 27 4040 5555 73 9873 98 1212 2727 55557373 4040 9898 1 3 654 2 至此堆排序结束，至此堆排序结束， 1616为有序序列为有序序列 21 堆排序算法分析：堆排序算法分析： 时间效率：时间效率： O(O(n nloglog 2 2 n n) )。因为整个排序过程中需因为整个排序过程中需 要调用要调用n n-1-1次次HeapAdjust( )算法，而算法本身耗算法，而算法本身耗 时为时为loglog 2 2 n n； 空间效率：空间效率：O(1)O(1)。仅在第二个仅在第二个forfor循环中交换记循环中交换记 录时用到一个临时变量录时用到一个临时变量temptemp。 稳定性：稳定性： 不稳定。不稳定。 优点：优点：对小文件效果不明显，但对大文件有效。对小文件效果不明显，但对大文件有效。 22 3.4 基数排序 (Radix Sort)(Radix Sort) 要讨论的问题：要讨论的问题： 1. 1. 什么是什么是“ “多关键字多关键字” ”排序？实现方法？排序？实现方法？ 2. 2. 单逻辑关键字怎样单逻辑关键字怎样“ “按位值按位值” ”排序？排序？ 基数排序的基本思想是：基数排序的基本思想是： 借助多关键字排序的思想对单逻辑关键字进行排借助多关键字排序的思想对单逻辑关键字进行排 序。即：用关键字序。即：用关键字不同的位值不同的位值进行排序。进行排序。 23 1. 1. 什么是什么是“ “多关键字多关键字” ”排序？实现方法？排序？实现方法？ 例例1 1：对一副扑克牌该如何排序？：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为：若规定花色和面值的顺序关系为： 花色花色： 面值：面值：2 = 0; i- ) / 开始做 d 趟分配/收集, i是key的第i位 for ( int j = 0; j radix; j+ ) fj = 0; / 初态各队列清空 while ( p!= 0 ) / 开始将n个记录分配到radix个队列 int k = rp. keyi; / 取当前记录之key分量的第 i 位 if ( fk = 0) f k =p; / 若第k个队列空, 此记录成为队首； else rek.next=p; / 若队列不空,链入原队尾元素之后 ek =p; / 修改队尾指针，该记录成为新的队尾 p= rp.next; / 选下一关键字，直到本趟分配完 链表基数排序的算法：链表基数排序的算法： 36 j = 0; / 开始从0号队列（总共radix个队）开始收集 while ( f j = 0 ) j+; /若是空队列则跳过 r0.next=p = f j; /建立本趟收集链表的头指针 int last = ej; /建立本趟收集链表的尾指针 for ( k = j+1; k radix; k+) /逐个队列链接（收集） if ( f k ) /若队列非空 rlast.next=f k; last = ek; /队尾指针链接 rlast.next=0; /本趟收集链表之尾部应为0 / RadixSort 注：在此算法中，数组rn被反复使用，用来存放原始序 列和每趟收集的结果。记录从未移动，仅指针改变。 37 队列初始化队列初始化 p = 0?p = 0? j j=rp.keyi=rp.keyi f( f(j j) = 0?) = 0? f( f(j j) = p;) = p;rrej.next=p;.next=p; e(j) = p;e(j) = p; p =rp.next;p =rp.next; end;end; N N Y Y Y Y N N / /取第取第p p个关键字的第个关键字的第i i 位位 / /将将p p指向下一个关键字指向下一个关键字 队不空，则新元素应链 到原队尾元素之后 P是关键字序列r 的指针分量 队首为空吗？空则 f(j)新入队元素 队尾新入队 的元素地址 一趟一趟“ “分配分配” ”过程的算法流程过程的算法流程 38 假设有假设有n n 个记录个记录, , 每个记录的关键字有每个记录的关键字有d d 位，每个关键字的位，每个关键字的 取值有取值有radixradix个个, , 则需要则需要radixradix个队列个队列, , 进行进行d d 趟趟“ “分配分配” ”与与“ “收集收集 ” ”。分配（每趟）分配（每趟）：T(n)=O( n n )，收集（每趟）收集（每趟）：T(n)=O( radix radix )，因此因此时间复杂度时间复杂度：O ( O ( d d ( ( n n+ +radixradix ) ) ) )。 基数排序需要增加基数排序需要增加n n+2*+2*radixradix个附加链接指针，个附加链接指针，空间效率低空间效率低 空间复杂度空间复杂度：OO（ n n+2*+2*radixradix ）. . 稳定性：稳定性：稳定稳定。( (一直前后有序一直前后有序) )。 用途：用途：若基数若基数radixradix相同，对于记录个数较多而关键码位数较少相同，对于记录个数较多而关键码位数较少 的情况，使用链式基数排序较好。的情况，使用链式基数排序较好。 基数排序算法分析基数排序算法分析 特点：特点：不用比较和移动，改用分配和收集，时间效率高！不用比较和移动，改用分配和收集，时间效率高！ 39 一、时间性能 时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以 快速排序为最好。 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序， 其中以直接插入为最好，特别是对那些对关其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。键字基本有序的记录序列尤为如此。 时间复杂度为 O(n*d)：基数排序。 1. 按平均时间性能来分，有三类排序方法： 2. 当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中 关键字的分布而改变。 3.5 各种排序方法的综合比较 40 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、冒泡和简单选择) 和 堆排序的空间复杂度为 O(1)； 2. 快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助 空间； 3. 归并排序所需辅助空间最多，其空间复杂度为 O(n)； 4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(2*rd+n) 三、排序方法的稳定性能 1. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳 定的排序方法。 2. 对于不稳定的排序方法，只要能举出一个实例说明即可。 3. 快速排序、堆排序是不稳定的排序方法。 41 本章总结： 1)、插入排序 2)、交换排序：冒泡排序、快速排序 3)、选择排序：简单选择排序、堆排序 4)、