内部排序培训课件.ppt

第10章 内部排序 10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论 整个快速排序过程: [初始关键字] 49 38 65 97 76 13 27 49` 第一趟快速排序： {27 38 13 } 49 {76 97 65 49`} 第二趟快速排序： {13 } 27 {38} {49` 65} 76 {97} 结束 结束 第三趟快速排序： 49` {65} 结束 结束 有序序列： 13 27 38 49 49` 65 76 97 第四趟快速排序： 快速排序算法的性能分析： （1）空间：需一个栈空间来实现递归。 （3）时间：基本运算：比较关键字和移动记录操作 平均时间复杂度：Tavg(n)= 快速排序算法的改进：三者取中法 若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，时间复杂度为O（n*n)。 用“三者取中”的法则来选取枢轴，即比较L.r[s].key、L.r[t].key和L.r[(s+t)/2].key，取三者中其关键字为中间值的记录为枢轴。 10.4选择排序 选择排序的基本思想:每一趟在n-i+1(i=1,2,...n-1)个记录中 选取关键字最小的记录作为有序序 列中第i个记录。 选择排序 简单选择排序 树形选择排序 堆排序 10.4.1简单选择排序 简单选择排序的算法设计: (1)需进行n-1趟选择操作; (2)第i趟选择操作为:通过n-i次关键字间比较,从n-i+1个记录中选出关 键字最小的记录,并和第i个记录交换; 简单选择排序的算法实现: Void selectsort (sqlist L) { for (i=1;iL.length; ++i ) { j=selectminkey(L,i); if (i!=j) L.r[i]??L.r[j]; } } 算法性能分析: (1)空间:一个辅助空间; (2)时间:基本操作:关键字的比较和记录的移动; 关键字的比较次数:(n-1)+(n-2)+…+1=n(n-1)/2 记录的移动次数:[0+3(n-1)]/2=3(n-1)/2 10.4.2 树形选择排序 在简单选择排序中,在n个关键字中进行n-1次比较选出最小值,然后继续在剩余的n-1个关键字中进行n-2次比较选出次小值,…… 在8个数中选出前3个数 需进行7+6+5=18次比较 改进 在n个关键字中进行n-1次比较选出最小值之后,利用本次比较的信息,在剩余的n-1个关键字中并非一定要进行n-2次比较就可选出次小值,…… 在8个数中选出前3个数 只需进行11次比较 例:有8个运动员参加体育锦标比赛,要决出前3名,比赛规则 依据:若甲胜乙,乙胜丙,则甲胜丙的原则;则此8名运动员 需进行11场比赛,而不是18场. 选拔冠军的比赛程序: BAO HE LI LIU BAO LI LIN BAO HU WU XEI LIN LIN HU BAO 需进行7场比赛 选拔亚军的比赛程序: LI HE LI LIU LIU LI LIN * HU WU XEI LIN LIN HU LIN 需进行2场比赛 选拔季军的比赛程序: LI HE LI LIU LIU LI * * HU WU XEI WU HU HU HU 需进行2场比赛 又称锦标赛排序，首先对n个记录的关键字进行两两比较，然后在其中一半较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。 树形选择排序的基本思想: 树形选择排序算法的执行步骤: 用一棵有n个叶子结点的完全二叉树表示排序过程: (1)n个叶子结点依次存放排序之前的n个关键字; (2)构造非叶子结点:每个非叶子结点的值为其左、右孩子结点中的 较小值，则根结点是所有叶子中的最小关键字，输出根结点的值； (3)修改非结点的关键字：把据有根结点值的叶子结点的值改为“最 大值”，然后从叶子开始，和其左（或右）兄弟的值进行比较， 修改从叶子结点到根的路径上各结点的值，输出根