数据结构第9章-排序

清华大学 殷人昆 C++数据结构 书稿 课件,学习数据结构的最好复习资料,也可以作为考研的参考资料,非常有用

第9章 排序

一、复习要点

排序是使用最频繁的一类算法。排序分内排序与外排序。内排序算法主要分5大类，有12个算法。在插入排序类中讨论了直接插入排序、二分法插入排序、表插入排序和shell排序算法；在交换排序类中讨论了起泡排序和快速排序算法；在选择排序类中讨论了简单选择排序、锦标赛排序和堆排序算法；在归并排序类中讨论了迭代的两路归并排序和递归的表归并排序算法；在多排序码排序类中讨论了最低位优先的链表基数排序算法。其中，不稳定的排序方法有shell排序、简单选择排序、快速排序和堆排序；适合于待排序对象数目n比较大的排序方法有快速排序、堆排序、归并排序和基数排序；排序码比较次数不受对象排序码初始排列影响的排序方法有折半插入排序、简单选择排序、锦标赛排序、两路归并排序和基数排序，其中，当排序码的初始排列接近有序时，直接插入排序和起泡排序等增长很快，而快速排序则变成慢速排序。

外排序是基于外存的排序方法。由于外存以顺序存取的效率最高，以归并排序最为适合。因此，外排序以k路平衡归并为主。在k个对象排序码中选取最小排序码，采用了败者树。这是一种高效的选择算法。此外，还讨论了初始归并段生成的方法，最佳归并树等问题。

本章复习的要点是： 1、基本知识点

要求理解排序的基本概念，包括什么是排序，排序的稳定性，排序的性能分析，如时间代价（对象排序码的比较次数和对象的移动次数）和空间代价（附加对象个数）。掌握插入排序（直接插入排序；折半插入排序；链表插入排序）、交换排序（起泡排序；快速排序）、选择排序（直接选择排序；链表选择排序；锦标赛排序；堆排序）、迭代的归并排序等内排序的方法及其性能分析方法。理解基数排序方法及其性能分析方法。理解多路平衡归并等外排序方法及败者树构造方法。理解生成初始归并段及败者树构造方法。理解最佳归并树的建立方法。

2、算法设计

插入排序：直接插入排序算法、折半插入排序算法、链表插入排序算法 交换排序：起泡排序算法，快速排序的递归算法和用栈实现的非递归算法 选择排序：直接选择排序算法，链表选择排序算法，堆排序算法

归并排序：两路归并算法，迭代的归并排序算法；递归的链表归并排序算法和用队列实现的非递归链表归并排序算法

其它排序算法：计数排序算法，奇偶排序算法

二、难点和重点

1、基本概念：排序码、初始排序码排列、排序码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序

2、插入排序

当待排序的排序码序列已经基本有序时，用直接插入排序最快 3、选择排序

用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，而不是顺次后移。这导致方法不稳定。

当在n个数据(n很大)中选出最小的5 8个数据时，锦标赛排序最快

清华大学 殷人昆 C++数据结构 书稿 课件,学习数据结构的最好复习资料,也可以作为考研的参考资料,非常有用

锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂2k-1 < n 2k 在堆排序中将待排序的数据组织成完全二叉树的顺序存储。 4、交换排序

快速排序是一个递归的排序方法

当待排序排序码序列已经基本有序时，快速排序显著变慢。 5、二路归并排序

归并排序可以递归执行

归并排序需要较多的附加存储。可以采用一种“推拉法”实现归并排序，算法的时

间复杂度为O (n)、空间复杂度为O(1)

归并排序对待排序排序码的初始排列不敏感，排序速度较稳定 6、外排序

多路平衡归并排序的过程、I/O缓冲区个数的配置 外排序的时间分析、利用败者树进行多路平衡归并 利用置换选择方法生成不等长的初始归并段 最佳归并树的构造及WPL的计算

三、教材中习题的解析

9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】

内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。 不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“>(或<)”改写成“≥(或≤)”，也可能造成不稳定。

9-2 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。 (1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】

(1) 直接插入排序

清华大学 殷人昆 C++数据结构 书稿 课件,学习数据结构的最好复习资料,也可以作为考研的参考资料,非常有用

初始排列 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9

[ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2

1 2 12 ] 12 12 12 10 10 10 6 6

2 16 16 16 ] 16 16 12 12 10 10

3 30 30 30 30 ] 28 16 16 16 12 12

4 28 28 28 28 28 16* 16* 16 16

5 10 10 10 10 10 30 ] 28 20 16* 16*

6 16* 16* 16* 16* 16* 16* 28 20 18

7 20 20 20 20 20 20 20 30 ] 28 20

8 6 6 6 6 6 6 6 6 28

9 18 18 18 18 18 18 18 18 18 排序码比较次数 1 1 1 2 5 3 3 3 8

(2) 希尔排序(增量为5,2,1)

初始排列 0 d = 5 d = 2 d = 1

12 10 10 2

1 2 2 2 6

2 16 16 16 10

3 30 6 6 12

4 28 18 16* 16

5 10 12 12 16*

6 16* 16* 18 18

7 20 20 20 20

8 6 30 30 28

9 18 28 28 30

排序码比较次数 1+1+1+1+1 = 5

(1+1+2+1) + (1+1 +1+1) = 9

1+1+3+1+3+1+1 +1+2 = 14

希尔(shell)本人采取的增量序列为 n/2 , n/2 /2 , n/2 /2 /2 , ,1。一般地，增量序列可采用 nα , nα α , nα α α , , 1。大量实验表明，取α=0.45454的增量序列比取其他的增量序列的优越性更显著。计算 0.45454n 的一个简单方法是用整数算术计算(5*n-1)/11。需要注意，当 < 1/2时，增量序列可能不以1结束，需要加以判断和调整。

(3) …… 此处隐藏：16249字，全部文档内容请下载后查看。喜欢就下载吧 ……