数据结构之树和图算法.ppt

第9章 排序 设 n 个记录的序列为 R1 , R2 , R3 , . . . , Rn 其相应的关键字序列为 K1 , K2 , K3 , . . . , Kn 若规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn ， 使得相应的关键字满足如下非递减关系: Kp Kp Kp . . . Kp 123 n 则原序列变为一个按关键字有序的序列: Rp , Rp , Rp , . . . , Rp 123 n 此操作过程称为排序。 排序排序 第9章 排序 假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ； 若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是 稳定的。 若在排序后的序列中 Rj 仍领先于 Ri ，则称排序方法是 不稳定的。 例，序列 3 15 8 8 6 9 若排序后得 3 6 8 8 9 15稳定的 若排序后得 3 6 8 8 9 15不稳定的 稳定排序与不稳定排序稳定排序与不稳定排序 第9章 排序 内部排序: 指的是待排序记录存放在计算机随机存储器 中进行的排序过程。 外部排序: 指的是待排序记录的数量很大，以致内存一 次不能容纳全部记录，在排序过程中尚需对外存进行 访问的排序过程。 内部排序与外部排序内部排序与外部排序 第9章 排序 排序的时间复杂性排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过 程。因此排序的时间复杂性可以算法执行中的数据比较次 数及数据移动次数来衡量。当一种排序方法使排序过程在 最坏或平均情况下所进行的比较和移动次数越少，则认为 该方法的时间复杂性就越好，分析一种排序方法，不仅要 分析它的时间复杂性，而且要分析它的空间复杂性、稳定 性和简单性等。 第9章 排序 按照排序过程中所依据的原则的不同可以分类为: 插入排序 交换排序(快速排序) 选择排序 归并排序 基数排序 二叉排序树排序 内部排序内部排序 第9章 排序 思想: 利用有序表的插入操作进行排序 有序表的插入: 将一个记录插入到已排好序的有序表中 ，从而得到一个新的有序表。 例，序列 13 27 38 65 76 97 插入 49 13 27 38 49 65 76 97 插入排序插入排序直接插入排序直接插入排序 第9章 排序 例，序列 49 38 65 97 76 13 27 初始，S = 49 ； 38 49 初始，令第 1 个元素作为初始有序表； 依次插入第 2 , 3 , , k 个元素构造新的有序表； 直至最后一个元素； 38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用比较和移动两种操作。 直接插入排序算法描述直接插入排序算法描述 第9章 排序 void insertsort(ElemType R,int n) /待排序元素用一个数组R表示，数组有n个元素 for ( int i=1; i=0)j-) Rj+1=Rj; /元素后移空出插入位 Rleft=temp; 第9章 排序 折半插入效率分析折半插入效率分析 二分插入算法与直接插入算法相比， 需要辅助空间与直接插入排序基本一致； 时间上，前者的比较次数比直接插入查找的最坏情况 好，最好的情况坏， 两种方法的元素的移动次数相同， 因此二分插入排序的时间复杂度仍为O(n2)。 二分插入算法与直接插入算法的元素移动一样是顺序 的，因此该方法也是稳定的。 第9章 排序 分析直接插入排序 1. 若待排序记录序列按关键字基本有序，则排序效 率可大大提高； 2. 待排序记录总数越少，排序效率越高； 希尔希尔(shell)(shell)排序排序 第9章 排序 思想: 先将待排序记录序列分割成为若干子序列分别进行直接插入排序 ； 待整个序列中的记录基本有序后，再全体进行一次直接插入排序 。 例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序49 13 19 38 27 65 48 97 55 76 4 13 19 4927 3848 6555 974 76 第9章 排序 第二趟排序 13 19 4927 3848 6555 974 76 13 55 38 76 27 4 65 49 48 19 97 13 38 55 764 27 49 6519 48 97 第三趟排序 4 13 19 27 38 48 49 55 65 76 97 第9章 排序 希尔排序的算法希尔排序的算法 template void ShellSort (T Vector, int arrSize ) T temp; int gap = arrSize / 2; /gap是子序列间隔 while ( gap != 0 ) /循环,直到gap为零 for ( int i = gap; i = gap; j -= gap ) if ( temp =i; j-) if (Rj= pivot) high -; Arraylow = Arrayhigh; while(low void SelectSort ( T Vector, int CurrentSize) for ( int i = 0; i b和ab), z如果以每次比较作为节点，则每个以比较为基础的排 序算法都可以用一个二叉树来表示，其中一个中间节 点表示一次比较，叶子节点表示排序的一种结果，这 样的二叉树称为判定树或决策树 z举例：比如有一个序列a, b, c(a,b,c互不相等） ，下列 算法： 先比较a和b, 再比较a和c，最后比较b和c 可以用下面的判定树表示 第9章 排序 归并排序（归并排序（Merge Sort)Merge Sort) |以比较为基础的排序算法的下界 ab?ab? yesyes ac?ac? yesyes bc?bc? yesyes abcabc acbacb nono nono nono cabcab ac?ac? yesyes bacbac nono bc?bc? yesyes bcabca cbacba nono 第9章 排序 归并排序（归并排序（Merge Sort)Merge Sort) |以比较为基础的排序算法的下界 z假设输入为a,b,c, acb, 则算法执行经过的路线为(ab) (ac)(bc)，需要3次比较 z假设输入为a,b,c, bac, 则算法执行经过的路线为(ab) (ac) 需要2次比较 z任何以比较为基础的排序算法都可以表示为一棵决策 树 树的形状和大小表示的是排序算法的功能和需要排序的元素个 数 树的高度表示了算法的运行时间 任何排序决策树都有n!个叶子 第9章 排序 归并排序（归并排序（Merge Sort)Merge Sort) |以比较为基础的排序算法的下界 z根据数据结构中关于二叉树的性质，有： z最坏情况：任何排序算法至少要做 次比较 z平均情况：任何排序算法的平均比较次数的下界是 z结论：具有O(nlgn)复杂度的比较排序算法在渐进意义 下是最优的算法 第9章 排序 是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。 1. 多关键字排序 扑克牌问题 : 已知扑克牌中52张牌面的次序关系定义为: 花色: 面值: 2 3 A . . . 例， 8 3 花色优先级更高 ，为主关键字， 面值为次关键字 基数排序基数排序 第9章 排序 2. 52张牌排序方法 : 最高位优先法(MSDF) : 先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色； 然后分别对每一堆按“面值”大小整理有序。 最低位优先法(LSDF) : 先按不同“面值”分成 13 堆 ； 然后将这 13 堆牌自小至大叠在一起( 2 , 3 , . . . , A ) ； 然后将这付牌整个颠倒过来再重新按不同的“花色”分成 4 堆 ； 最后将这 4 堆牌按自小至大的次序合在一起 。 收集 分配 第9章 排序 3. 基数排序 基数排序就是借助于“分配”和“收集”两种操作实现对单逻辑关键字 的排序。 首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。 其次，利用 LSDF 法实现对若干关键字的排序。 例，若关键字是数值，且值域为 0K999 ， 故可以将 K 看作是由 3 个关键字 K0 K1 K2 组成 ， 例，603是由 6 0 3 组成。 第9章 排序 例，序列 278 109 063 930 589 184 505 269 008 083 第一趟分配0 1 2 3 4 5 6 7 8 9 278 109063930 589 184505 269 008083 第一趟收集930063 083184505278 008109 589 269 第二趟分配0 1 2 3 4 5 6 7 8 9 930063083 184 505278 008 109589 269 第二趟收集505 008 109930063 269278083 184 589 第9章 排序 第二趟收集505 008 109930063 269278083 184 589 第三趟分配0 1 2 3 4 5 6 7 8 9 505008 109930 063 269 278 083 184589 第三趟收集008 063 083109 184269 278505 589930 第9章 排序 中序遍历可实现二叉搜索树结点的有序化 13 8 5 23 18 37 9 5 8 9 13 18 23 37 ? 如何实现 自大到小排 列 二叉树排序二叉树排序 第9章 排序 各种内排序方法的选择 1从时间复杂度选择 对元素个数较多的排序，可以选快速排序、堆排序、归 并排序，元素个数较少时，可以选简单的排序方法。 2从空间复杂度选择 尽量选空间复杂度为O（1）的排序方法，其次选空间复 杂度为O(log2n)的快速排序方法，最后才选空间复杂度为 O（n）二路归并排序的排序方法。 3一般选择规则 （1） 当待排序元素的个数n较大，排序码分布是随机， 而对稳定性不做要求时，则采用快速排序为宜。 第9章 排序 （2)当待排序元素的个数n大，内存空间允许，且要求 排序稳定时，则采用二路归并排序为宜。 （3）当待排序元素的个数n大，排序码分布可能会出 现正序或逆序的情形，且对稳定性不做要求时，则采 用堆排序或二路归并排序为宜。 （4)当待排序元素的个数n小，元素基本有序或分布较 随机，且要求稳定时，则采用直接插入排序为宜。 (5)当待排序元素的个数n小，对稳定性不做要求时， 则采用直接选择排序为宜，若排序码不接近逆序，也 可以采用直接插入排序。冒泡排序一般很少采用。 第9章 排序 各种排序方法的比较各种排序方法的比较 第9章 排序 案例分析：多项式相加案例分析：多项式相加 |C+中如何表示多项式 z链表 |对两个多项式中的每个数据项的变量进行 排序 |执行加法运算 第9章 排序 课堂练习课堂练习 |对于一组记录的排序码为(465，792，562 ，383，401，845，502，423)，写出基数 排序（低位优先）进