数据结构第九章内部排序

第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次比较的算法思想。

习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D.简单选择排序E. 起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为 O(n?n) 的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（ 84， 47， 25， 15， 21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21（2） 15 47 25 84 21（3） 15 21 25 84 47（4） 15 21 25 47 84则采用的排序是 ()。

A. 选择B.冒泡C.快速D.插入4．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B.冒泡C.归并D.堆5．一组记录的关键码为（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)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。

A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。

A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。

数据结构测试（长春理工大学精品课）第9章排序一、选择题1．某内排序方法的稳定性是指( )。

查看答案A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法D．以上都不对正确答案是D解释：稳定的排序方法指的是若有相同关键字的记录，待排序时在前面的记录排序后仍然排在前面的排序方法。

收起2．下面给出的四种排序法中( )排序法是不稳定性排序法。

查看答案A. 插入B. 冒泡C. 二路归并D. 堆正确答案是D解释：堆排序是不稳定的，交换时有可能把后面的排在前面。

收起3．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。

( )查看答案A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序法正确答案是A解释：简单选择排序是在待排记录中找到最小的和第一个相交换，再在除了第一个排完的以外找个最小的和第二个相交换，依此类推，n个记录的待排序列需要比较（n-1）+（n-2）+......+0=（n-1）*n/2收起4. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是查看答案( )A. lB. 4C. 3D. 2正确答案是B 收起5．下列四个序列中，哪一个是堆（）。

查看答案A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,15正确答案是C解释：这是一个大根堆，每个结点都比左右孩子小。

收起6．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序是( )。

数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。

内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。

本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

冒泡排序是一种简单直观的排序算法。

它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。

因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。

插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。

选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

以此类推，直到全部待排序的数据元素排完。

选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。

快速排序是一种分治的排序算法。

它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。

快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。

然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。

归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第九章排序（基础知识）8.1 【答案】以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。

(1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序(5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。

8.2 【答案】上题的排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现?8.3 【答案】当R[low..high]中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)?8.4 【答案】若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好?8.5 【答案】若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜?6. 用快速排序算法，对下列数组排序60 56 65 99 22 16 88 100a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]取a[0]为支点（pivot），列出第一轮升序排序后的元素顺序。

8.6 【答案】有序数组是堆吗?8.7 【答案】高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方?8.8 【答案】判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆：(1) (100,86,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,23,40,38,29,61,35,76,28,100).8.9 【答案】将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需要比较2n-1次，请说明这两种情况发生时，两个被归并的表有何特征?7. 将序列101 45 21 532 22 5 232 14 存放在一静态链表中（见下图），并对其按照链式基数排序法进行升序排序。

一、单选题1、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，5，2，37)B.(19，21，37，5，2)C.(19，21，2，5，37)D.(19，21，5，37，2)正确答案：B2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，37，5，2)B.(19，21，2，5，37)C.(19，21，5，37，2)D.(19，21，5，2，37)正确答案：D3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。

A.(113，165，176，197，127，138，149)B.(113，165，176，127，197，138，149)C.(113，127，138，149，165，176，197)D.(149，138，165，197，176，113，127)正确答案：A4、下列各项键值（）序列不是堆的。

A.(5，23，68，16，94)B.(5，23，16，94，68)C.(5，16，23，68，94)D.(5，23，16，68，94)正确答案：A5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。

A.(24，62，36，19)(24，36，62，19)(19，24，36，62)B.(24，62，19，36)(19，24，36，62)C.(62，24，36，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)正确答案：B6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（）。

A.归并排序B.快速排序C.冒泡排序D.选择排序正确答案：A7、对于下列排序，（）的时间效率与关键字初始序列有直接关系。