第9章排序ppt课件.ppt

《第9章排序ppt课件.ppt》由会员分享，可在线阅读，更多相关《第9章排序ppt课件.ppt（57页珍藏版）》请在三一文库上搜索。

1、第9章 排序,9.1 基本概念,(1) 排序,2,对于有 n 个结点的线性表 (e0, e1, , en-1)，按照结点某些数据项的关键字按递增或者递减的次序，重新排列线性表结点的过程称为排序。,(2) 排序方法的稳定性 排序时参照的数据项称为排序码，通常选择结点的关键字作为排序码。如果线性表中排序码相等的结点经某种排序方法进行排序后，仍然能够保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。,3,(3) 内部排序和外部排序 排序可以分为内部排序和外部排序两类。,4,在排序过程中，如果线性表的全部结点都在内存，并且在内存中调整它们在线性表中的存储顺序，则称

2、这种排序方法为内部排序，简称内排序。,在排序过程中，如果线性表只有部分结点被调入内存，并且借助内存调整结点在外存中的存放顺序，则称这种排序方法为外部排序，简称外排序。,(4) 排序方法的性能 一般的内部排序方法分为：插入排序法、交换排序法、选择排序法、归并排序法和基数排序法。内部排序的方法很多，每种方法都有其各自的优点和缺点，适合于不同的环境，比如记录的初始状态，记录数量的多少等等。但是无论哪种排序方法，一般的性能评价标准主要有如下两条：,5, 执行排序算法所需要的时间；, 执行排序算法所需要的附加空间。,为了叙述方便，假定待排序的记录按递增顺序排序。另外，待排序的记录序列可以是顺序存储结构，

3、也可以是链表存储结构，若没有特别说明，假定待排序的记录均以顺序存储结构存放，且假定记录的关键字均为整数；待排序记录的数据类型定义如下：,6,#define MAXSIZE 100 / 顺序表最大长度 typedef int KeyType; / 定义关键字类型为整数类型,7,typedef struct / 记录定义 KeyType key; / 关键字项 InfoType otherinfo; / 其他数据项 RedType; / 记录类型,typedef struct / 顺序表定义 RedType rMAXSIZE+1; / r0 闲置或用作哨兵单元 int length; / 顺序表长

4、度 SqList; / 顺序表类型,9.2 插入排序法,插入排序法包括直接插入排序和希尔排序。直接插入排序 (straight insertion sort) 是一种最简单的排序方法。D.L.shell 在 1959 年提出了希尔排序 (shell sort)，又称缩小增量排序 (diminishing increment sort)，是对直接插入排序的一种改进。,1 直接插入排序,8,2 希尔排序,(1) 算法思想 直接插入排序的基本思想是：逐个处理待排序列中的记录，将其与前面已经排好序的子序中的记录进行比较，确定要插入的位置，并将记录插入到子序中。具体做法如下：,9,1. 直接插入排序,

5、把第 1 个记录看成是已经排好序的子序，这时子序中只有一个记录；,10, 从第 2 个记录起到最后一个记录，依次将记录和前面子序中的记录比较，确定记录插入的位置；, 将记录插入到子序中，子序记录个数加 1，直至子序长度和原来待排序列长度一致时结束。,(2) 算法编写,void InsertSort ( SqList / 插入到正确位置 / if / InsertSort,11,(3) 算法分析,12, 假定待排序列中的记录有 n 个，当待排序列中的记录按关键字非递减有序排序（简称正序）时，所需要进行的关键字之间比较的次数达最小值 n-1，记录不需要移动；反之，当待排序列中的记录按关键字非递增有

6、序排序（简称逆序）时，所需要进行的关键字之间比较的次数达最大值 (n-2)(n-1)/2，记录移动次数也达最大值 (n+4)(n-1)/2。,如果待排序记录是随机的，即待排序列中的记录可能出现的各种排列的概率相同，则可以取上述最小值和最大值的平均值，作为直接插入排序时所需要进行关键字之间的比较次数和移动记录的次数，约为 n2/4。由此，直接插入排序的时间复杂度为 O(n2)。,13, 直接插入排序是稳定的。直接插入排序适用于记录个数较少的场合。,(1) 算法思想 希尔排序的基本思想是：先将 n 个待排记录序列分割成若干个子序列，然后对各子序列分别进行排序，当整个序列中的记录 “基本有序” 时，

7、再对全体记录进行一次直接插入排序。具体做法如下：,14,2. 希尔排序, 取定一个正整数 d1 n，把全部记录按此间隔值从第 1 个记录起进行分组，所有距离为 d1k 倍数的记录放一组中，在各组内进行直接插入排序；,15, 取定一个正整数 d2 d1，重复上述分组和排序工作，直至取 di = 1 为止，即所有记录在一个组中进行直接插入排序。,一般地， di 取法为：d1 = n / 2，di+1 = di / 2。,(2) 算法描述,void ShellSort ( SqList / 一趟增量为 dk 的插入排序 / ShellSort,16,void Shellinsert ( SqList

8、 &L, int dk ) /*对顺序表 L 作一趟希尔插入排序。 此算法和一趟直接插入排序相比，作了以下修改： (1) 前后记录位置的增量是 dk，而不是 1； (2) r0 只是暂存单元，而不是哨兵。当 j = 0 时， 插入位置已经找到。*/ ,for ( i = dk+1; i 0 / 插入到正确位置 / if / ShellInsert,17,(3) 算法分析,18, 希尔排序的性能分析是一个复杂的问题，因为它的时间是所取 “增量” 序列的函数，到目前为止增量的选取无一定论。但是，无论增量序列如何取，最后一个增量值必须等于 1。希尔排序的速度一般要比直接插入排序快。按照希尔对 “增量

9、” 的取法，希尔排序的时间复杂度为 O(nlog2n)。 希尔排序是不稳定的。,9.3 交换排序法,交换排序法包括冒泡排序和快速排序。交换排序法的基本思想是：比较两个待排序记录的关键字，若为逆序则相互交换位置；反之，若为正序则保持原序。 冒泡排序 (bubble sort) 是一种简单交换排序。快速排序 (quick sort)，又称分区交换法，是对冒泡排序的一种改进，是目前内部排序中速度较快的一种方法。,冒泡排序,19,快速排序,(1) 算法思想,20,1. 冒泡排序, 将第 n 个记录的关键字和第 n-1 个记录的关键字进行比较，若为逆序则将两个记录进行交换，若为正序则保持原序；, 将第

10、n-1 个记录的关键字和第 n-2 个记录的关键字进行比较，重复上述排序过程；, 上述步骤 和 的排序过程称作第一趟冒泡排序，其结果使得关键字最小的记录被安置到第 1 个记录的位置上；, 进行第二趟冒泡排序，从第 n 个记录开始至第 2 个记录进行同样的操作，其结果是使得关键字次小的记录被安置到第 2 个记录的位置上；,21,依此类推，第 i 趟冒泡排序是从第 n 个记录到第 i 个记录之间依次进行比较和交换。整个排序过程需要进行 k (1kn) 趟冒泡排序，就像气泡一个个地往上冒一样，故称为冒泡排序。 显然，判别冒泡排序结束的一个条件应该是 “在一趟排序过程中没有进行过交换记录的操作”。,(

11、2) 算法描述,void BubbleSort ( SqList / for / BubbleSort,22,(3) 算法分析,23, 冒泡排序的效率与排序前记录的次序有关，如果排序前记录为正序，则冒泡排序只需要进行一趟排序，在排序过程中进行 n-1 次关键字比较，并且不移动记录；反之，如果排序前记录为逆序，则冒泡排序就需要进行 n-1 趟排序，在排序过程中需要进行 n(n-1)/2 次关键字比较，并且作等量级的记录移动。因此，冒泡排序总的时间复杂度为 O(n2)。 冒泡排序是稳定的。冒泡排序适用于记录基本有序的场合。,(1) 算法思想,24,2. 快速排序,快速排序的基本思想是：通过一趟排序

12、将待排序的 n 个记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后可以分别对这两部分记录继续进行排序，以达到整个序列有序。具体操作如下：, 设待排序的记录序列存于 L.rs, L.rs+1, , L.rt 中，首先选取一个记录（通常选取第 1 个记录 L.rs）作为 “枢轴 (pivot) ”；, 按以下原则重新排列其余记录：将所有关键字比 “枢轴” 记录小的记录都安置在其位置之前，将所有关键字比 “枢轴” 记录大的记录都安置在其位置之后。由此可将 “枢轴” 记录最后所在位置 i 作为分界线，将待排序记录 L.rs, L.rs+1, , L.rt 分割成两个子序列

13、 L.rs, L.rs+1, , L.ri-1 和 L.ri+1, L.rs+1, , L.rt 。这个过程称作一趟快速排序。,25, 对所分割的两部分别重复上述过程，直至每个部分内只剩下一个记录排序。快速排序完成。,一趟快速排序： 附设两个指针 low 和 high，初始时，它们分别是 s 和 t ，设 “枢轴” 记录的关键字为 pivotkey。先从 high 所指位置起向前搜索找到第一个关键字小于 pivotkey 的记录，并和 “枢轴” 记录互相交换；再从 low 所指位置起向后搜索，找到第一个关键字大于 pivotkey 的记录，并和 “枢轴” 记录互相交换。重复这两个步骤，直至 l

14、ow = high 时为止，,26,void QuickSort ( SqList / 对 L.r 1 . . L.length 作快速排序 / QuickSort,(2) 算法描述,27,void Qsort ( SqList / 对高子表递归排序 / if / QSort,28,int Partition ( SqList *L, int low, int high ) /* 交换顺序表 L 中子表 rlow . . high 的记录， 将 “枢轴” 记录到位，且返回其所在位置。 此时，在它之前（后） 的记录均不大（小）于它。*/ L.r0 = L.rlow; pivotkey = L.r

15、low.key; while ( low = pivotkey ) -high; L.rlow = L.rhigh; while ( low high / Partition,29,(3) 算法分析,30, 快速排序的平均实际复杂度为 O(nlog2n)。 但是，在待排序的记录已经有序的情况下，排序工作使用的时间反而最长。这时，第 1 趟排序经过 n-1 次比较后，将第 1 个记录仍然定位在它原来的位置上；第 2 趟排序经过 n-2 次比较后，将第 2 个记录仍然定位在它原来的位置上；依此类推，总的比较次数为 (n-1) + (n-2) + + 1 = n(n-1)/2，记为 O(n2)。因此

16、，在待排序记录基本有序的情况下，将蜕化为冒泡排序，时间复杂度为 O(n2)。, 快速排序递归算法需要堆栈来实现，栈中存放待排序记录序列的首尾位置，一般情况下需要栈空间 O(log2n)；在最坏的情况下，需要的栈空间为 O(n)。,31, 快速排序是不稳定的。快速排序不适用于记录基本有序的场合。,9.4 选择排序法,选择排序法的基本思想是：每一趟在 n-i+1 ( i = 1, 2, , n-1 ) 个记录中选取关键字最小的记录作为有序序列中的第 i 个记录。 选择排序法包括简单选择排序和堆排序。简单选择排序 (simple selection sort) 是一种最简单且最为广大读者熟悉的选择排

17、序法。堆排序 (heap sort) 是对树型选择排序方法的一种改进，避免了重复比较。,简单选择排序,32,堆排序,(1) 算法思想 简单选择排序的基本思想：将 n 个待排序记录存放在 L.r1 . .n 中，对 n 个待排序记录进行 n-1 趟扫描：,33,1. 简单选择排序, 第 1 趟扫描选出 n 个记录中关键字值最小的记录，并与 L.r1 记录交换位置；, 第 2 趟扫描选出余下的 n-1 个记录中关键字值次最小的记录，并与 L.r2 记录交换位置；,依此类推至第 n-1 趟扫描结束，所有记录有序。,void SelectSort ( SqList / for / SelectSort

18、,(2) 算法描述,34,(3) 算法分析,35, 初始文件有序时，移动记录为 0 次；, 初始文件逆序时，移动记录至多为 3(n-1) 次；, 初始文件随机时，外循环 i = 1 时，内循环要做 n-1 次比较；当外循环 i = 2 时，内循环要做 n-2 次比较；依此类推，当外循环 i = n-1 时，内循环要做 1 次比较。因此，总共比较次数为 n*(n-1)/2。简单选择排序时间复杂度为 O(n2)。, 简单选择排序是不稳定的。,使用简单选择排序法，从 n 个记录中选出关键字值最小的记录需要作 n-1 次比较，然后从其余 n-1 个记录中选出次最小的记录需要作 n-2 次比较，。显然，

19、相邻两趟中的某些比较是重复的。为了避免重复比较，可以采用树型选择排序方法。,36,2. 堆排序,(1) 树型选择排序的基本思想,37, 把 n 个记录的关键字两两比较，将其中关键字值较小的 n/2 个关键字取出，然后将这 n/2 个关键字进行两两比较，继续选择较小的关键字，直至选出一个最小关键字值；, 对余下的 n-1 个记录的关键字进行第 2 趟两两比较，再选出一个次小关键字；如此反复，直至结束。,这种两两比较的过程可以用一棵有 n 个叶子结点的树来描述。上面一层分支结点两两比较得到较小的关键字。依次类推，树根表示最后选出来的最小关键字，已经选出来的关键字的叶子结点用 表示。,(2) 堆排序

20、,38,树型选择排序算法克服了简单选择排序中比较次数过多的缺点，可把每趟比较的结果保存下来，比较的过程就是修改从树根到刚改为 的叶子结点这一路径上各结点的值的过程。每趟都经过 log2n 次比较就选择出一个最小关键字值，因此，总比较次数(nlog2n)。 但是这种方法的缺点是占用较多的存储空间来保存比较的结果。因此，1964 年威洛姆斯 (J.willioms) 提出对树型选择排序方法的改进方法堆排序。堆排序只需一个记录大小的辅助空间，与树型选择排序相比，在存储空间及比较次数方面作了一些改进。,(3) 堆的定义,如果用一维数组依次存放该序列，并且把这个一维数组看成是一棵完全二叉树的顺序存储表示

21、，则堆的含义可以这样认为：在这个二叉树中，所有的非叶子结点的关键字值 ki 均不大于（或不小于）其左右两个分支结点（即左右孩子结点）的关键字值 k2i 和 k2i+1。,39,一棵有 n 个记录的线性序列 R1, R2, , Rn ，其关键字序列 k1, k2, , kn 满足以下关系时，称之为堆。,kik2i,kik2i+1,kik2i,kik2i+1,( i = 1, 2, , n/2 ),或,(4) 堆排序,40,堆排序的关键问题有两个：,第一个问题是如何构造堆。,第二个问题是如何调整堆，即如何在输出堆的根结点后，调整剩余元素成为一个新的堆。, 调整堆,41,假设输出堆根结点之后，以堆的

22、最后一个元素替代之。此时根结点的左、右子树均为堆，则只需要自上至下进行调整即可。,第一步：将根结点与它的左、右孩子比较，如果根结点比它的两个孩子结点都小，则已是堆；否则，让根结点与其中较小的孩子结点交换，先让根结点满足堆的性质。,第二步：可能因为交换，使得以交换后的结点为根的子树不再满足堆的性质，则重复向下调整。,42, 当调整使新的更小子树依旧满足堆的性质时，重新建堆垒的过程结束；, 当交换使新的更小子树不再满足堆的性质时，继续按上述第一步方法调整被破坏的更小子树。,最坏的情况是直至调整到叶结点才结束。这种自上而下调整建堆的过程称为结点向下 “筛选”。, 构造堆,43,为了构造初始堆，可以在

23、已经是堆的两个子序列上面加上它们的根结点，并且作必要的调整使之成为更大的堆垒。 加上根结点后，可能不满足堆的定义，则可以用前述的 “筛选” 方法，使之成为堆。所以，从一个无序序列构造堆的过程就是反复 “筛选” 的过程。,如果将 n 个待排序记录的关键字序列组成一个完全二叉树，那么最后一个非叶子结点是第 n/2 个元素。做如下操作：,44,首先，将 n 个叶子结点组成 n 个堆；,然后，从第 n/2 个结点开始，依次将第 n/2 个结点，第 n/2-1 个结点，第 2 个结点，第 1 个结点按照堆的定义逐一加到它们的子结点上，直到建成一个完全的堆垒。,(4) 堆排序的算法,45, 算法思想,堆排

24、序算法由两个函数组成：, 筛选的函数 HeapAdjust ( )；, 实现堆排序的函数 HeapSort ( )。,void HeapSort ( SqList / 将 H.r1 . . i-1 重新调整为堆 / for / HeapSort,46, 算法描述,void HeapAdjust ( SqList ,47,for ( j = 2*s; j H.rj+1.key ) ) +j; if ( ! ( temp.key H.rj.key ) ) break; / temp 应插入在位置 s 上 H.rs = H.rj; s = j; / for H.rs = temp; / 插入 / H

25、eapAdjust, 算法分析,2 ( log2(n-1) + log2(n-2) + + log22 ) 2n ( log2n ),48,首先，堆排序算法的运行时间主要耗费在构造初始堆和调整新建堆时进行的反复 “筛选” 上。对深度为 k 的堆，在 HeapAdjust 算法中进行的关键字比较次数至多为 2(k-1) 次。n 个结点的完全二叉树深度为 log2n +1，则调整新建堆时调用 HeapAdjust 过程 n-1 次，总共进行的比较次数不超过下式之值：,由此，堆排序在最坏的情况下，其时间复杂度也为 O(nlog2n)，相对于快速排序，这是堆排序最大的优点。,49,其次，堆排序仅需要一

26、个记录大小的辅助存储空间，供交换元素使用。,最后，堆排序是不稳定的。堆排序不适用于记录较少的情况。,9.5 归并排序法,归并排序 (merging sort) 是又一类不同的排序方法。其基本思想是：将两个或两个以上的有序序列归并成一个有序序列。利用归并的思想容易实现排序。,两个有序序列的归并,50,归并排序,51,将两个有序的序列归并为一个新的有序序列，称为 2-路归并；将 3 个有序的序列归并为一个新的有序序列，称为 3-路归并；将多个有序的序列归并为一个新的有序序列，称为多路归并。以 2-路归并为例，其核心是将一维数组中前后相邻的两个有序序列合并为一个有序序列。,1. 两个有序序列的归并,

27、void Merge ( SqList SR, SqList *T, int i, int m, int n ) / 将有序的 SRi . . m 和 SRm+1 . . n 归并为有序的 TRi . . n for ( j = m+1, k = i; i = m / 将剩余的 SRj . . n 复制到 TR / Merge,52,(1) 算法思想,53,2. 归并排序, 将 n 个待排序的记录分成只含有 1 个记录的 n 个有序子序列；, 将这 n 个有序子序列依次两两归并，得到 n/2 个长度为 2 的有序子序列（当 n 为奇数时，有一个长度为 1 的子序列）；, 再对它们作两两合并，如

28、此重复，直到得到一个长度为 n 的有序表为止，归并排序完成。,(3) 算法分析,54, 对具有 n 个结点的序列进行归并排序需要进行 O(log2n)，每趟归并的执行时间为 O(n)，因此整个归并排序的时间复杂度为 O(nlog2n)。 在每趟归并排序的过程中，需要一个和 n 一样大小的附加空间，所以归并排序算法所需要的附加空间的空间复杂度为 O(n)， 归并排序与快速排序和堆垒排序相比，最大特点在于它是一种稳定的排序方法。,9.6 基数排序法,基数排序 (radix sorting) 和前面所述的各类排序方法完全不相同。前面几种排序方法主要是通过比较关键字和移动（交换）记录这两种操作来实现的

29、，而基数排序不需要进行关键字的比较和记录的移动（交换），是一种基于多关键字排序的思路而对单逻辑关键字进行排序的一种内部排序方法。,55,如下例子说明多关键字的排序思想。 假定扑克牌 52 张牌的次序为：2 3 A 2 3 A 2 3 A 2 3 A。每张牌有两个 “关键字”：花色 ( ) 和面值 ( 2 3 A )，而且花色优先于面值。其意思是在比较任意两张牌的大小时，先比较花色，花色相同时再比较面值。,56,多关键字排序,一般情况下：假设有 n 个记录的序列 R1, R2, , Rn 且每个记录 Ri 中含有 d 个关键字 (K0i , K1i , , Kd-1i )，则称上述序列对关键字 (K0i , K1i , , Kd-1i ) 有序是指：对于序列中任意两个记录 Ri 和 Rj (1ijn) 都满足下列有序关系： (K0i , K1i , , Kd-1i ) (K0j , K1j , , Kd-1j ) 其中 K0 称为最主关键字，Kd-1 称为最次关键字。,57,