浙江广播电视大学 文本 辅导与练习9_数据结构

数据结构（本）课程精导与然习一第9章 中央电大工学院王在风2008年05月16日 第9章排序 教材中对各种排序方法的算法讲得已经非常清楚，因此本章辅导主要针对排序的概念以 及各种排序算法进行分析。从而方便同学们对各种排序进行比较。 一、相关术语 内部持序、外部排序、排序的稳定性、直接插入排序、新半插入排序、交换排序、冒 泡持序，快速排序、这择排序、直接选释排序、堆排序，归并排序。 二、排序的基本概念 (一)排序 所谓持序，就是要整理文件中的记录。使之按关健字递增（或递减）次序带列起米。其确 切定文如下： 输入：n个记录R,R,,R,其相应的关键字分别为K,K:,,K 输出：R,Ra,,Ram使得KiSK2s.SKm(暖K2K2≥K 1.鼓#序对象文件 敲排序的对象…文件由一组记录相成。 记承则由若干个数据项成城)组成。其中有一项可用来标识一个记录。称为关键字项。 该数据项的值称为关健字气Ky) 注意：在不易产生湿清时，将关健字项简称为关健字。 2,排序运算的依形-关键学 用来作排序运算依据的关健字，可以是数字类型，也可以是字符类型。 关键字的选取应根据月题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各 科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用准考证号”作为关 健字。若要按属考生的总分数持名次，则活用”总分数作为关键字。 (二》排序的稳定性 当特挂序记录的关键字均不相同时，排序结果是惟一的，否则挂序结果不隆一

数据结构（本）课程辅导与练习－第 9 章 中央电大工学院 王春凤 2008 年 05 月 16 日 第 9 章 排序 教材中对各种排序方法的算法讲得已经非常清楚，因此本章辅导主要针对排序的概念以 及各种排序算法进行分析。从而方便同学们对各种排序进行比较。 一、相关术语 内部排序、外部排序、排序的稳定性、直接插入排序、折半插入排序、交换排序、冒 泡排序、快速排序、选择排序、直接选择排序、堆排序、归并排序。 二、排序的基本概念 （一）排序 所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确 切定义如下： 输入：n 个记录 R1，R2，…，Rn，其相应的关键字分别为 K1，K2，…，Kn。 输出：Ril，Ri2，…，Rin，使得 Ki1≤Ki2≤…≤Kin。(或 Ki1≥Ki2≥…≥Kin)。 1．被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。 该数据项的值称为关键字(Key)。 注意：在不易产生混淆时，将关键字项简称为关键字。 2．排序运算的依据--关键字 用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各 科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关 键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。 （二）排序的稳定性 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一

在待挂序的文件中，若存在多个关键字相月的记录，经过排序后这些具有相月关键字的 记录之间的相对次序保持不变。该排序方法是魏定的：若具有相同关健字的记录之间的相对 次序发生变化，则称这种排序方法是不穆定的。 注意 排序算法的稳定性是针对所有输入实例而言的，即在所有可能的输入实例中，只要有一 个实例使得算法不裤足稳定性要求，则该排序算法就是不稳定的。 (三)排序方法的分类 1,按是香涉及数裙的内、外存交换分 在排序过程中，若整个文件都是故在内存中处理，排序时不涉及数据的内、外存交换， 则移之为内廊排序（简称内排序反之，若排序过程中要进行数据的内、外存交换，则称之 为外都排序。 注意 ①内排序适用于记录个数不很多的小文作 ②外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件. 2,按策略划分内部排序方法 可以分为五类：插入排序、选择排序、交换排序、白并挂序和分配排序。 (四)排序算法分析 1.排序算法的基本操作 大多数排序算法都有两个基本的操作： ()比较两个关健字的大小： (2)改变指向记录的指针或移动记录本身， 注意： 第2)种基本操作的实现依赖于待排序记录的存储方式。 2,特钟文件的常用存储方式 《1)以顺序表（或直接用向量）作为存储结构

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的 记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对 次序发生变化，则称这种排序方法是不稳定的。 注意： 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一 个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 （三）排序方法的分类 1．按是否涉及数据的内、外存交换分 在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换， 则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之 为外部排序。 注意： ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。 2．按策略划分内部排序方法 可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。 （四）排序算法分析 1．排序算法的基本操作 大多数排序算法都有两个基本的操作： (1) 比较两个关键字的大小； (2) 改变指向记录的指针或移动记录本身。 注意： 第(2)种基本操作的实现依赖于待排序记录的存储方式。 2．待排文件的常用存储方式 （1）以顺序表(或直接用向量)作为存储结构

排序过程：对记录本身进行物理重排〔即通过关键字之间的比较判定，将记素移到合适 的位置) (2)以链表作为存储结构 排序过程：无颈移动记录，仅需修改指针。通常将这类挂序称为链成链式)排序 (3)用顺序的方式存储特排序的记录。但同时建立一个辅助表（如包括关键字和指向 记录位置的指针组成的索明表) 排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录 本身)。适用于难于在链表上实现。仍雷避免作序过程中移动记录的伟序方法。 3。排序算法性能评价 (1)评价持序算法好坏的标准 评价持序算法好环的标准主要有两条： ①执行时间和所需的辅助空间 ②算法本身的复杂程度 (2)排序算法的空向复条度 若排序算法所需的辅助空何并不依赖于问题的规模，即辅助空间是O(),则称之为就 随挂序In-PlaceSou: 卡就地排序一般要求的辅助空间为O): (3)排序算法的时间开销 大多数排序算法的时间开销主要是美健字之闻的比较和记录的移动：有的持序算法其执 行时何不仅依赖于门思的规模，还取读于输入实例中数据的状老。 三、直接播入排序算法分析 1。算法的时间性能分析 对于具有n个记录的文件，要进行ml墙排序. 各种状者下的时闻复桑度： 初始文件状态 正序 反序 无序平均 第1墙的关健字比较 1+1 (-2)2

排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适 的位置） （2） 以链表作为存储结构 排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序； （3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向 记录位置的指针组成的索引表) 排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录 本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。 3．排序算法性能评价 （1） 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条： ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 （2） 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模 n，即辅助空间是 O(1)，则称之为就 地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为 O(n)。 （3） 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执 行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。 三、直接插入排序算法分析 1．算法的时间性能分析 对于具有 n 个记录的文件，要进行 n-1 趟排序。 各种状态下的时间复杂度： 初始文件状态 正序 反序 无序(平均) 第 i 趟的关键字比较 i+1 （i-2）/2

次数1 总关健字比较次要 nl (+2M-1W2 Rm/4 第1墙记录移动次数 +2 (-2)2 总的记录移动次要 0 (n-IXn+4V2 m24 时间复杂度 0(n 0() 0(2) 注意： 初始文件按关键字递增有序，简称正序。 初始文件按关键字递减有序，简称反序”。 2.算法的空间复杂度分析 算法所需的辅助空间是一个监视哺，辅助空间复桑度S)OI)。是一个就地排序。 3。直接插入排序的稳定性 直接插入排序是稳定的排序方法。 四、冒泡排序算法分析 (1)算法的最好时间复杂度 若文件的初始状态是正序的，一植扫播即可完成排序。所需的关键字比较次数C和记 录移动次数M均达到最小值： Can=n-1 Mm-0. 冒泡排序最好的时间复杂度为O): (2)算法的最坏时间复杂度 若初始文件是反序的，需要进行m1植排序。每随排序要进行1次关键字的比较 (1<-),且每次比较都经演移动记录三次米达到交换记录位置，在这种情况下，比较和移 动次数均达到最大值： Cam=n(n-1)2=C(m) M-3n(n-1)/2-O(m)

次数 1 总关键字比较次数 n-1 (n+2)(n-1)/2 ≈n2 /4 第 i 趟记录移动次数 0 i+2 （i-2）/2 总的记录移动次数 0 (n-1)(n+4)/2 ≈n2 /4 时间复杂度 0（n） O（n 2） O（n 2） 注意： 初始文件按关键字递增有序，简称"正序"。 初始文件按关键字递减有序，简称"反序"。 2．算法的空间复杂度分析 算法所需的辅助空间是一个监视哨，辅助空间复杂度 S(n)=O(1)。是一个就地排序。 3．直接插入排序的稳定性 直接插入排序是稳定的排序方法。 四、冒泡排序算法分析 （1）算法的最好时间复杂度 若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 C 和记 录移动次数 M 均达到最小值： Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为 O(n)。 （2）算法的最坏时间复杂度 若初始文件是反序的，需要进行 n-1 趟排序。每趟排序要进行 n-i 次关键字的比较 (1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移 动次数均达到最大值： Cmax=n(n-1)/2=O(n2 ) Mmax=3n(n-1)/2=O(n2 )

国泡排序的最坏时间复杂度为0()。 (3)算法的平均时间复象度为O) 風然冒泡排序不一定要谜行】遵，但由于它的记录移动次数较多，故平均时间性能比 直接插入持序要差得多。 (4)算法稳定性 冒泡排序是就地排序，且它是稳定的。 五、快速排序算法分析 快速挂序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k1次关键 字的比较。 (1)最坏时间复杂度 最坏情况是每次划分透取的基准都是当前无序区中关键字最小州或最大)的记录，划分的 结果是基准左边的子区间为空（或右边的子区间为空，而划分所得的另一个非空的子区间中 记录数目，仅仅比划分前的无序区中记录个数减少一个。 因此，快速排序必须做n1次划分。第i次划分开始时区间长度为n+1,所需的比较次 数为n-Im-),故总的比较次数达到最大值： Com n(p-I2-O(n') 如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记 承己按递增序成递减序)排列时，每次划分所取的基准设是当前无序区中关健字最小（成最大） 的记豪。则快速排序所需的比较次数反而最多。 (2)最好时间复杂度 在最好情况下，每次划分所取的基落都是当前无序区的中值”记录，划分的结果是基准 的左、右两个无序子区间的长度大致相等。总的关键字比较次数： ((nlgn) 注意： 用递自树米分析最好情况下的比较次数更简单，因为每次划分后左、右子区何长度大致 相等，故递归树的高度为O1g),而递自树每一层上各结点所对应的划分过程中所需要的关 健字比较次数总和不超过n,故整个排序过程所需要的关键字比较总次数COg. 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复染度应为 0(r),最好时间复杂度为O(nlgn)

冒泡排序的最坏时间复杂度为 O(n2 )。 （3）算法的平均时间复杂度为 O(n2 ) 虽然冒泡排序不一定要进行 n-1 趟，但由于它的记录移动次数较多，故平均时间性能比 直接插入排序要差得多。 （4）算法稳定性 冒泡排序是就地排序，且它是稳定的。 五、快速排序算法分析 快速排序的时间主要耗费在划分操作上，对长度为 k 的区间进行划分，共需 k-1 次关键 字的比较。 （1）最坏时间复杂度 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的 结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中 记录数目，仅仅比划分前的无序区中记录个数减少一个。 因此，快速排序必须做 n-1 次划分，第 i 次划分开始时区间长度为 n-i+1，所需的比较次 数为 n-i(1≤i≤n-1)，故总的比较次数达到最大值： Cmax = n(n-1)/2=O(n2 ) 如果按上面给出的划分算法，每次取当前无序区的第 1 个记录为基准，那么当文件的记 录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大) 的记录，则快速排序所需的比较次数反而最多。 （2） 最好时间复杂度 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准 的左、右两个无序子区间的长度大致相等。总的关键字比较次数： 0(nlgn) 注意： 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致 相等，故递归树的高度为 O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关 键字比较次数总和不超过 n，故整个排序过程所需要的关键字比较总次数 C(n)=O(nlgn)。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 0(n2 )，最好时间复杂度为 O(nlgn)

(3)基准关键字的选取 在当简无序区中选取划分的基准关键字是决定算法性能的关健， ①三者取中"的规则 ”三者取中“规则，即在当前区间里，将该区间首、尾和中侧位置上的关键字比较，取三 者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区饲的第！个记录进行交 换，此后的划分过程与上面所给的Partition算法完全相同. ②取位于ow和ieh之间的随机数kon≤k≤eh),用Rk作为基准 选取基准最好的方法是用一个随机函数产生一个取位于ow和g助之同的面机数 Mow≤k≤high),用Rk]作为基准，这相当于强迫Row.hieh中的记录是随机分布的。用此 方法所得到的快速排序一般称为随机的快道排序。具体算法【参见敦材】 注意： 随机化的快建排序与一般的快速排序算法差别很小。但随机化后，算法的性陵大大地提 高了，尤其是对初始有序的文件，一般不可能导致最环情况的发生。算法的随机化不仅仅适 用于快速排序。也适用于其它需要数据随机分布的算法。 (4)平均时间复杂度 尽管快速排序的最坏时间为O),但就平均性能而言，它是基于关键字比较的内部排 序算法中速度最快者，快速排序亦因此商得名。它的平均时间复杂度为Olg): (5)空同复杂度 快速排序在系统内部雷要一个栈来实观递归。若每次划分较为均匀，则其递归树的高度 为Ogn,故运归后需栈空阿为Og.最坏情况下，递归树的高度为O叫，所需的栈空向 为0n: (6)稳定性 快速排序是非稳定的 六、直接选择挂序算法分析 (1)关键字比较次数 无论文件初始状态如何，在第1墙持序中选出最小关健字的记录，香酸次比较，因 此，总的比较次数为： n-1w2-0n2)

（3）基准关键字的选取 在当前无序区中选取划分的基准关键字是决定算法性能的关键。 ①"三者取中"的规则 "三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三 者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第 1 个记录进行交 换，此后的划分过程与上面所给的 Partition 算法完全相同。 ②取位于 low 和 high 之间的随机数 k(low≤k≤high)，用 R[k]作为基准 选取基准最好的方法是用一个随机函数产生一个取位于 low 和 high 之间的随机数 k(low≤k≤high)，用 R[k]作为基准，这相当于强迫 R[low..high]中的记录是随机分布的。用此 方法所得到的快速排序一般称为随机的快速排序。具体算法【参见教材】 注意： 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提 高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适 用于快速排序，也适用于其它需要数据随机分布的算法。 （4）平均时间复杂度 尽管快速排序的最坏时间为 O(n2 )，但就平均性能而言，它是基于关键字比较的内部排 序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为 O(nlgn)。 （5）空间复杂度 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度 为 O(lgn)，故递归后需栈空间为 O(lgn)。最坏情况下，递归树的高度为 O(n)，所需的栈空间 为 O(n)。 （6）稳定性 快速排序是非稳定的 六、直接选择排序算法分析 （1）关键字比较次数 无论文件初始状态如何，在第 i 趟排序中选出最小关键字的记录，需做 n-i 次比较，因 此，总的比较次数为： n(n-1)/2=0(n2 )

(2)记录的移动次数 当初始文件为正序时，移动次数为0 文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3到). 直接透择排序的平均时间复柔度为O力： (3)直接选择排序是一个就地排序 《4)稳定性分析 直接选择排序是不稳定的 七、堆排序的算法分析 堆排序的封间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。它们均是通 过调用Heapify实现的。 堆排序的最坏时间复桑度为Olg。堆排序的平均性能较接近于最坏性能。 由于建给堆所需的比较次数较多，所以堆排序不适直于记承数较少的文件。 堆排序是就地排序，辅助空间为O): 它是不意定的排序方法。 八、各种内都排序方法的比较和透择 1,按平均时间将排序分为四类 (1)平方阶0(n)排序 一般称为简单排序。例如直接插入，直接选择和冒泡排序： (2)线性对数阶0lgn)排序 如快速、生和归并排序 (3)0n“)阶排序 ￡是介于0和1之间的常数，即0K￡<1，如希尔排序： (4)线性阶O()排序 如桶、箱和基数排序

（2）记录的移动次数 当初始文件为正序时，移动次数为 0 文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值 3(n-1)。 直接选择排序的平均时间复杂度为 O(n2 )。 （3）直接选择排序是一个就地排序 （4）稳定性分析 直接选择排序是不稳定的 七、堆排序的算法分析 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通 过调用 Heapify 实现的。 堆排序的最坏时间复杂度为 O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为 O(1)。 它是不稳定的排序方法。 八、各种内部排序方法的比较和选择 1．按平均时间将排序分为四类 （1）平方阶(O(n2 ))排序 一般称为简单排序，例如直接插入、直接选择和冒泡排序； （2）线性对数阶(O(nlgn))排序 如快速、堆和归并排序 （3）O(n1+￡ )阶排序 ￡是介于 0 和 1 之间的常数，即 0<￡<1，如希尔排序； （4）线性阶(O(n))排序 如桶、箱和基数排序

2.各种排序方法比较 简单持序中直接插入最好，快速排序最快，当文件为正序时，直接拓入和冒泡均最住。 3玉，影响并序效果的因素 因为不月的抖序方法适应不料的应用环境和要求，所以选择合适的排序方法应棕合考虑 下列因素： ①待排序的记录数目n: ②记录的大小（规模）： ③关键字的结构及其初始状态： ①对稳定性的要求： 回语言工具的条件： 同存储结构： ⑦时间和辅助空间复杂度等。 4。不同条件下，排序方法的选择 (I)若n较小（如n心50，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好：否测因为直接选择移动的记录数少于直接插人， 应选直接选释排序为宜。 (2)若文件初始状态基本有序指正序)，则应选用直接插人，冒泡咸随机的快速排序为直 (3)若n较大，则应采用时间复桑度为Qg)的排序方法：快速排序，堆排序或自并排 序。 快速持序是目前基于比较的内部持序中被认为是最好的方法，当待序的关健字是随机 分布时，快速排序的平均时间最复： 堆排序所需的辅助空问少于快速排序，并且不会出现快速排序可能出现的最坏情况。这 两种排序都是不稳定的。 若要求排序稳定，则可选用自并排序。但本章介邱的从单个记录起进行两两自并的排序 算法并不值得提四，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求 得较长的有序子文件，然后再两两白并之。因为直接插入排序是稳定的，所以改速后的白并 推序仍是稳定的

2．各种排序方法比较 简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。 3．影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑 下列因素： ①待排序的记录数目 n； ②记录的大小(规模)； ③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构； ⑦时间和辅助空间复杂度等。 4．不同条件下，排序方法的选择 (1)若 n 较小(如 n≤50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人， 应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜； (3)若 n 较大，则应采用时间复杂度为 O(nlgn)的排序方法：快速排序、堆排序或归并排 序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机 分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这 两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序 算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求 得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并 排序仍是稳定的

九、练习愿 单项选择题 1.设有1000个无序的元素，希望用最快的速度桃选出其中前0个最大的元素，最好选 用()排序法。 A起泡排序 B.快速持序 C堆排序 D.基数排序 2对数据元素序列(49.72,68,13,38.30,97,27)进行排序，前三墙排序结果时 的结果依次为第一崎：49,72.68,13,38.50,97,27：第二墙：49,68,72.13,38， 50,97.27:第三崎：13,49.68,72,38.50,97,27。该排序采用的方法是(》。 A插入排序法B.选择排序法C.冒泡样序法D.堆积排序法 3一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始 堆是《)。 A79,46,56,38.40,80 B.84,79,56.38,40,46 C.84,79,56.46,40.38 D.84,56,79.40,46,38 4.一组记录的关量码(6,9.5638,0,84)，则利用快速排序的方法，以第一个 记录为基准得到的一次刻分结果为()。 A38,40,46,56,79,84 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40.38,46.84,56,79 5.下述几种排序方法中，要求内存量最大的是()： A新入排序 B.选择排序 C.快速排序 D.归并排序 6外排序是指()。 A在外存上进行的排序方法 B.不看要使用内存的排序方法 C数据很大，需要人工干预的排序方法 D.排序前后数据在外存，持序时数据调入内存的持序方法

九、练习题 单项选择题 1.设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选 用（ ）排序法。 A.起泡排序 B.快速排序 C.堆排序 D.基数排序 2.对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时 的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38， 50，97，27；第三趟：13，49，68，72，38，50，97，27。该排序采用的方法是（ ）。 A. 插入排序法 B. 选择排序法 C. 冒泡排序法 D.堆积排序法 3.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始 堆是（ ）。 A.79，46，56，38，40，80 B.84，79，56，38，40，46 C.84，79，56，46，40，38 D.84，56，79，40，46，38 4.一组记录的关键码（46，79，56，38，40，84），则利用快速排序的方法，以第一个 记录为基准得到的一次划分结果为（ ）。 A.38，40，46，56，79，84 B.40，38，46，79，56，84 C.40，38，46，56，79，84 D.40，38，46，84，56，79 5.下述几种排序方法中，要求内存量最大的是（ ）。 A.插入排序 B.选择排序 C.快速排序 D.归并排序 6.外排序是指（ ）。 A.在外存上进行的排序方法 B.不需要使用内存的排序方法 C.数据很大，需要人工干预的排序方法 D.排序前后数据在外存，排序时数据调入内存的排序方法

7.请指出在顺序表！2,5、7、10.14、15,18、23、35,41、52！中，用二分法查找关 健码2需做多少次关键码比较，() A2B.3 C.4 D.5 8就排序算法所用的辅助空同而言，蝶排序、快速排序、归并排序的关系是《)· A堆挂序归并排序>快速排序D峰排序>快速排序>归并排序 9.一组记录的关键字序列为(25,48,16,35,79,82,23,40,36,72)，其中， 含有5个长度为2的有序表，按白并排序的方法对该序列进行一植自并后的结果为(》。 A.16,25,35,48.23,40,79.82,36,72 B.16,25,35,48,79,82,23,36,40,72 C.16,25,48,35,9.82,23,36.40,72 D.16,25,35,48,79,23,36,40,82,72 10.已知10个数据元素为(54,28,16,34,73,62,95,60,26.43》，对该数列从 小到到大持序。经过一墙冒泡排序后的序列为《)。 A,16,28,34,54,73,62,60.2643,95 B.28,16,34,54,62.73,60,26.43,95 C.28,16,34,54,62.60,73,26,43,95 D.16,28,34,54,62,60,73.26,43,95 练习题答案 单项选择圈 1,C2.A3.B4.C5,D6,D7,C8,A9,A10,B

7.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关 键码 12 需做多少次关键码比较。 （ ） A.2 B.3 C.4 D.5 8.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（ ）。 A.堆排序 归并排序> 快速排序 D.堆排序> 快速排序> 归并排序 9. 一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中， 含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ ）。 A．16，25，35，48，23，40，79，82，36，72 B．16，25，35，48，79，82，23，36，40，72 C．16，25，48，35，79，82，23，36，40，72 D．16，25，35，48，79，23，36，40，82，72 10.已知 10 个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从 小到到大排序，经过一趟冒泡排序后的序列为（ ）。 A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95 C．28，16，34，54，62，60，73，26，43，95 D．16，28，34，54，62，60，73，26，43，95 练习题答案 单项选择题 1．C 2．A 3．B 4．C 5．D 6．D 7．C 8．A 9．A 10．B