数据结构(Java)-第9章排序讲述.ppt

13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 输出：13 27 49 38 97 65 76 50 13 输出：13 97 49 38 27 65 76 50 13 输出：13 27 38 49 50 27 65 76 97 13 输出：13 27 65 49 50 27 38 76 97 13 输出：13 27 38 49 65 50 27 38 76 97 13 输出：13 27 38 76 65 50 27 38 49 97 13 输出：13 27 38 49 50 65 76 27 38 49 97 13 输出：13 27 38 49 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 97 76 27 38 49 50 13 输出：13 27 38 49 50 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 65 97 27 38 49 50 13 输出：13 27 38 49 50 65 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 五、归并排序 2－路归并排序 基本思想：假设初始序列有n个记录，首先把n个记录看成n个长度为1的有序序列，进行两两归并，得到 个长度为2的关键字有序序列，再两两归并直到所有记录归并成一个长度为n的有序序列为止。 【例9.8】有一组记录，它们的关键字分别为：（51，60，38，17，59，22，20，85），用2-路归并法进行排序（关键字递增有序）。 五、归并排序 排序过程： 数组下标： 0 1 2 3 4 5 6 7 关键字序列： 51 60 38 17 59 22 20 85 第三趟排序后： [17 20 22 38 51 59 60 85] 第一趟排序后： [51 60] [17 38] [22 59] [20 85] 第二趟排序后： [17 38 51 60] [20 22 59 85] 六、基数排序 9.6.1 多关键字排序 多关键字的定义 例 对52张扑克牌按以下次序排序： ?2?3……?A?2?3……?A ?2?3……?A?2?3……?A 两个关键字：花色（ ???? ） 面值（23……A） 并且“花色”地位高于“面值” 六、基数排序 多关键字排序 最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。 最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。 六、基数排序 9.6.2 基数排序 基本思想：先根据多个关键字分别排序，再将其合并到一起；多关键字排序按照从最主要关键字到最次要关键字或者从最次要关键字到最主要关键字的顺序逐次排序。 【例9.9】有一组记录，它们的关键字分别为：（973, 622, 593, 743, 155, 214, 448, 765, 239, 381），用基数排序法进行排序（关键字递增有序） 六、基数排序 步骤一：对关键字按个位进行递增排序 个位数字 0 1 2 3 4 5 6 7 8 9 关键字 381 622 973 214 155 448 239 593 765 743 六、基数排序 步骤二：对关键字按十位进行递增排序 个位数字 0 1 2 3 4 5 6 7 8 9 关键字 214 622 239 743 155 765 973 381 593 448 步骤三：对关键字按百位进行递增排序 个位数字 0 1 2 3 4 5 6 7 8 9 关键字 155 214 381 448 593 622 743 973 239 765 排序结果：155，214，239，381，448，593，622，743，765，973。 七、各种排序算法的比较 排序方法 平均时间 最坏时间 辅助空间 稳定性 直接插入排序 稳定 冒泡排序