9 内部排序

第9章内部排序一、问答题1. 什么是内部排序？什么是排序方法的稳定性？2. 对于本章介绍的内部排序方法，哪几种是稳定的？哪几种是不稳定的？对不稳定的排序方法试举例说明。

3. 对于给定的一组记录的关键字：23，13，17，21，30，60，58，28，30，90。

试分别写出用下列排序方法对其进行排序时，每一趟排序后的结果：(1)直接插入排序；(2)希尔排序；(3)冒泡排序；(4)直接选择排序；(5)快速排序(6)堆排序(7)归并排序。

4. 对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这n个元素的初始序列。

(1)n = 8时，在最好的情况下需要进行多少次比较？试说明理由。

(2)给出n = 8时的一个最好情况的初始排列实例。

5 试为下列各种情况选择合适的排序方法：(1)n = 30，要求在最坏的情况下，排序速度最快；(2)n = 30，要求排序速度既要快，又要排序稳定。

6. 判别以下序列是否为堆（所有的非叶子结点的关键字值k i均不大于其左右两个分支结点的关键字值k2和k2i+1。

），如果不是，则把它调整为堆。

(1)( 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 )；(2)( 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 )；(3)( 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 )；(4) ( 05, 56, 20, 03, 23, 40, 38, 29, 61, 05, 76, 28, 100 )。

7. 一组待排序记录的关键字是：986，321，123，432，500，654，018，765，987，210。

按照LSD方法写出基数排序的过程和结果。

8. 试证明：如果对于一个长度为n的任意文件进行排序，则至少需进行nlog2n次比较。

9. 试构造对5个整数元素进行排序，最多只用7次比较的算法思想。

R[3] 10
R[4] 60
R[5] 25
R[6] 30
R[7] 18 18 18 18
18 36 20

10 10 36
60 60 60
25 25 25
30 30 30
【算法】直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*对排序表R[1]..R[n]进行直接插入排序，n是记录的 个数*/ for(i=2; i<=n; i++) if (R[i].key<R[i-1].key) {R[0]=R[i]; /*将R[i]插入R[1].. R[i-1]中， R[0]为监测哨*/ for(j=i-1; R[0].key<R[j].key; j--) R[j+1]=R[j]; /*后移记录*/ R[j+1]=R[0]; /*插入到合适位置*/ } }
空间性能：除排序表以外的内存占用情况。 时间性能：比较关键码的次数，数据移动的次数。 它们往往是排序表规模（n）的函数
6. 记录和排序表的数据结构
一般采用顺序结构存储排序表。 记录和排序表的类型定义如下： #define MAXNUM … /* MAXNUM 为足够大的数 typedef struct { keytype key; …… } datatype; datatype R[MAXNUM]; /*关键码字段*/ /*其它信息*/ /*记录类型*/ /*定义排序表的存储
第一趟排序结果，使得间隔为5的字表有序： P=3
29 7 41 30 11 39 50 76 41 13 10 0 80 78 86
子序列分别为:{29,30,50,13,78}，{7,11,76,100,86}， {41,39,41,80}。第二趟排序结果： P=1

第九章排序一、填空题（1）排序是将一组任意排列的数据元素按________________的值从小到大或从大到小重新排列成有序的序列。

（2）在排序前，关键字值相等的不同记录间的前后相对位置保持____________的排序方法称为稳定的排序方法。

（3）在排序前，关键字值相等的不同记录间的前后相对位置_______________的排序方法称为不稳定的排序方法。

（4）外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中。

（5）当数据已经有序时，不再进行排序的方法是_________________排序方法。

（6）在堆排序中，首先要使数据成堆，在堆中所有的____________都不比其孩子结点小（或大）。

（7）在直接插入排序的方法中，当需要将第i个数据插入时，此时前i-1个数据是___________的。

（8）对一个基本有序的数据进行排序___________________排序方法运算次数最少。

二、选择题（1）排序是根据__________的大小重新安排各元素的顺序。

A. 数组B. 关键字C. 元素D. 结点（2）稳定的排序方法是指在排序中，关键字相等的不同记录间的前后相对位置_______。

A. 保持不变B. 保持相反C. 不定D. 无关（3）不稳定的排序方法是指在排序中，关键字相等的不同记录间的前后相对位置______。

A. 保持不变B. 保持相反C. 不定D. 无关（4）内部排序是指在排序的整个过程中，全部数据都在计算机的________________。

A. 内存储器B. 外存储器C. 内存储器和外存储器D. 寄存器（5）外部排序是指在排序的整个过程中，全部数据在计算机的__________中完成的排序。

A. 内存储器B. 外存储器C. 内存储器和外存储器D. 寄存器（6）直接插入排序的方法是_____________的排序方法。

A. 稳定B. 不稳定C. 外部D. 选择（7）直接插入排序的方法是从第__________个元素开始，插入前边适当位置的排序方法。

数据结构第9章排序数据结构第9章排序第9章排名本章主要内容：1、插入类排序算法2、交换类排序算法3、选择类排序算法4、归并类排序算法5、基数类排序算法本章重点难点1、希尔排序2、快速排序3、堆排序4.合并排序9.1基本概念1.关键字可以标识数据元素的数据项。

如果一个数据项可以唯一地标识一个数据元素，那么它被称为主关键字；否则，它被称为次要关键字。

2．排序是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。

如果排序依据的是主关键字，排序的结果将是唯一的。

3.排序算法的稳定性如果要排序的记录序列中多个数据元素的关键字值相同，且排序后这些数据元素的相对顺序保持不变，则称排序算法稳定，否则称为不稳定。

4.内部排序与外部排序根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。

内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放在内存中，另一部分放在外围设备上。

整个排序过程需要在内存和外存之间进行多次数据交换才能得到排序结果。

本章仅讨论常用的内部排序方法。

5.排序的基本方法内部排序主要有5种方法：插入、交换、选择、归并和基数。

6.排序算法的效率评估排序算法的效率主要有两点：第一，在一定数据量的情况下，算法执行所消耗的平均时间。

对于排序操作，时间主要用于关键字之间的比较和数据元素的移动。

因此，我们可以认为一个有效的排序算法应该是尽可能少的比较和数据元素移动；第二个是执行算法所需的辅助存储空间。

辅助存储空间是指在一定数据量的情况下，除了要排序的数据元素所占用的存储空间外，执行算法所需的存储空间。

理想的空间效率是，算法执行期间所需的辅助空间与要排序的数据量无关。

7.待排序记录序列的存储结构待排序记录序列可以用顺序存储结构和和链式存储结构表示。

在本章的讨论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。