【大学数据结构课件】排序1.pptVIP

内容提要 7.1 排序的基本概念 7.2 内部排序 内部排序的分类 插入排序 交换排序 选择排序 合并排序 计数排序 基数排序 内部排序方法比较 7.3 外部排序 7.1 排序的基本概念 1、排 序：按照结点中的某项值对集合中结点进行升序或降序的排列。 2、关 键 字：排序时参照的数据项，有主次之分 3、稳 定 性：如果排序操作使等值结点的相对位置(主要是指前后关系)保持不变，则排序是稳定的，否则是不稳定的。 4、内部排序：排序序列放在内存中 5、外部排序：需要对外存进行访问 7.1 内排序 1、内部排序的分类 I.按照时间复杂度来分(排序的结点数量为n) (1).简单的排序方法，O(n2) (2).先进的排序方法，O(nlog2n) (3).基数排序，O(dxn) II.按照排序过程中所依据的原则来分 (1).插入排序 (2).交换排序 (3).选择排序 (4).合并排序 III.按照是否改变结点的物理位置来分 (1).物理重排 (2).不改变结点位置的排序，包括：链地址法，利用辅助地址表排序，计数排序等 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 2、插入排序 内排序(cont’d) 3、交换排序 内排序(cont’d) 3、交换排序 内排序(cont’d) 3、交换排序 内排序(cont’d) 3、交换排序 内排序(cont’d) 3、交换排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 4、选择排序 内排序(cont’d) 5、合并排序（归并排序） 内排序(cont’d) 5、合并排序（归并排序） 内排序(cont’d) 5、合并排序（归并排序） 内排序(cont’d) 6、计数排序 内排序(cont’d) 6、计数排序 内排序(cont’d) (7)基数排序----多关键字排序 内排序(cont’d) 7、基数排序----多关键字排序 内排序(cont’d) 7、基数排序----多关键字排序 内排序(cont’d) 7、基数排序----多关键字排序 内排序(cont’d) 7、基数排序----多关键字排序 内排序(cont’d) 7、基数排序----多关键字排序 内排序(cont’d) 7、基数排序----多关键字排序 内排序(cont’d) 内排序(cont’d) 8、内部排序方法的比较 7.3 外排序 外部排序：指对大型文件的排序，由于文件中结点数据比较大，不可能将所有数据都放入内存。 外部排序的类型：归并排序，归并段放在文件中，归并结果放在另一文件中。 影响外部排序的因素：起始归并段的大小以及一次归并几段。 《数据结构》 第七章 排序 例、扑克牌排序，规则： ?2 ?3 ···?K?A ?2 ?3 ···?K?A ? 2?3 ···?K?A ? 2?3 ···?K?A ????法： 1、先排花色 2、先排面值 利用多关键码排序的思想处理单关键码的排序问题。 假定有一个n个对象序列{V0,V1,…Vn-1}，且每个对象Vi都含有d个关键码(Ki1,Ki2,…,Kid)。如果对于序列中任意两个对象Vi和Vj都满足： (Ki1,Ki2,…,Kid)=(Kj1,Kj2,…,Kjd)或 (Ki1,Ki2,…,Kid)=(Kj1,Kj2,…,Kjd) 则称序列对关键码(K1,K2,…,Kd)有序，其中， K1称为最高位关键码， Kd称为最低位关键码。 abac baab 实现多关键码排序有两种常用的方法，一种是最高位优先法(MSD,Most Significant Digit first)，一种是最低位优先法(LSD,Least Significant Digit first)。 MSD通常是一个递归过程：首先根据最高位关键码K1进行排序，得到若干个子序列，每个子序列中的对象都具有相同的关键码K1 。然后分别对每个子序列根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子序列，每个子序列中的对象具有相同的K1 、K2值。这样重复，直到对关键码Kd完成排序为止。 LSD做法是：首先根据最低关键码Kd对所有对象进行一趟排