第9章 排序解析.ppt

本章目录 9.1 基本概念 排序的分类 按照参加排序的数据元素（记录）是否全部放置在内存中可把排序分为内排序和外排序。 内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。 排序的分类 按照排序所依据的关键码的个数可以把排序分为单键排序和多键排序。 单键排序：根据一个关键码进行的排序。 多键排序：根据多个关键码进行的排序。 排序的分类 按照排序的方法是否建立在关键码比较的基础上可以把排序分为： 基于比较：主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。 不基于比较：根据待排序数据的特点所采取的其它方法，通常是没有大量的关键码之间的比较和记录的移动操作的排序。 内排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 内排序的主要方法 内排序的主要方法 内排序的主要方法 内排序的主要方法 9.2 插入排序 直接插入排序 操作步骤： Step1:选取L.key[1] 作为初始的有序序列,i=2; Step2:将L.key[i]插入到前面的有序序列中，使 其有序序列长度增加1； Step3:i=i+1，若i的值小于表长，则重复Step2， 否则排序结束。 直接插入排序 算法分析： 空间效率：仅用了一个辅助单元，O(1)。 时间效率： 最好情况下：初始序列是顺序的 最坏情况下：初始序列是逆序的 平均情况下：初始序列是无序的 稳定性：是一种稳定的排序方法。 直接插入排序 折半插入排序 折半插入排序 操作步骤： Step1: 顺序表中前j-1个记录有序，将第j个记录插入。 令low=1；high=j-1；r[0]=r[j]； Step2: 若low>high，得到插入位置，转Step5; Step3: 若low≤high，则取有序子表的中点 m=(low+high)/2； Step4: 若r[0].key<r[m].key，则插入位置在低半区， 令high=m-1；否则插入位置在高半区， 令low=m+1；转Step2; Step5: high+1即为待插入位置，从j-1到high+1的记录， 逐个后移，r[high+1]=r[0]；放置待插入记录。 折半插入排序 算法分析： 时间复杂度：O(n2)。 空间复杂度：O(1)。 稳定性：是一种稳定的排序方法。 表插入排序 算法思想： 为了减少在排序过程中进行的 “移动”记录的操作，必须改变排序过程中采用的存储结构。 利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。 表插入排序 静态链表说明: #define SIZE 200 typedef struct{ ElemType elem； /*元素类型*/ int next； /*指针项*/ }NodeType； /*表结点类型*/ typedef struct{ NodeType r[SIZE]； /*静态链表*/ int length； /*表长度*/ }L_TBL； /*静态链表类型*/ 表插入排序操作步骤 Step1: 从第一个记录开始调整，令j=l->r[0].next；将i指向第一个记录位置； Step2: 若i=l->length时，调整结束；否则: 表插入排序 举例说明 希尔排序 希尔排序 操作步骤： Step1: 选择一个步长序列t1，t2，…，tk，其中 ti>tj， tk=1； Step2: 按步长序列个数k，对序列进行k趟排序； Step3: 每趟排序，根据对应的步长ti，将待排序列分割 成若干长度为m的子序列，分别对各子表进行直 接插入排序。仅步长因子为1时，整个序列作为 一个表来处理，表长度即为整个序列的长度。 希尔排序 举例说明： 希尔排序 算法分析： 时间复杂度：由于希尔排序是依赖于增量的选取，它的时间复杂度是在O(nlog2n)~O(n2)之间。 空间复杂度：在希尔排序的过程中只需要一个辅助空间用于暂存当前待插入的记录，因此，希尔排序的空间复杂度为O(1)。 稳