《习题讲解-8-排序》由会员分享，可在线阅读，更多相关《习题讲解-8-排序（13页珍藏版）》请在金锄头文库上搜索。
1、排序章志勇算法的稳定性 直接选择排序、快速排序、希尔排序、堆排序是 不稳定的排序算法， 冒泡排序、插入排序、归并排序和基数排序是稳 定的排序算法。 算法的稳定性 冒泡排序就是把小的元素往前调或者把大的元素往后调。比 较是相邻的两个元素比较，交换也发生在这两个元素之间。 插入排序是在一个已经有序的小序列的基础上，一次插入一 个元素。当然，刚开始这个有序的小序列只有1个元素，就 是第一个元素。 归并排序是把序列递归地分成短序列，递归出口是短序列只 有1个元素(认为直接有序)或者2个序列(1次比较和交换),然 后把各个有序的段序列合并成一个有序的长序列，不断合并 直到原序列全部排好序。 算法的稳定性
2、 基数排序是按照低位先排序，然后收集；再按照高位排序 ，然后再收集；依次类推，直到最高位。 算法的时间复杂度 直接插入 O( n) O(n2) O(n2) 希尔 不确定 O(n1.3) O(n2) 快速 不确定 O(nlogn) O(n2) (基本有序） 简单选择 O(n2) O(n2) O(n2) 堆排序 不确定 O(n logn) O(nlogn) 归并 O(nlogn) O(nlogn) O(nlogn) 基排序 O(dn) O(dn) 冒泡 O( n) O(n2) O(n2) 算法的稳定性 简单选择排序是给每个位置选择当前元素最小的，比如给 第一个位置选择最小的，在剩余元素里面给第二个
3、元素选 择第二小的，依次类推 希尔排序是按照不同步长对元素进行插入排序， 当刚开始元素很无序的时候，步长最大，所以插 入排序的元素个数很少，速度很快；当元素基本 有序了，步长很小，插入排序对于有序的序列效 率很高。 堆的结构是节点i的孩子为2*i和2*i+1节点，大顶 堆要求父节点大于等于其2个子节点，小顶堆要求 父节点小于等于其2个子节点。 排序 1某内排序方法的稳定性是指(D)。【南京理工大学】 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录 C平均时间为0（n log n）的排序方法 D以上都不对。 2下面给出的四种排序法中(D )排序法是不稳定性排序 法。【北
4、京航空航天大学 1999】 A插入 B冒泡 C二路归并 D堆积 3若需在O(nlog2n)的时间内完成对数组的排序，且要 求排序是稳定的，则可选择的排序方法是（C ）。【中 国科技大学 1998】 A快速排序 B堆排序 C归并排序 D直接插入排序 4稳定的排序方法是（B） 【北方交通大学 2000】 A直接插入排序和快速排序 B折半插入排序和起泡排序 C简单选择排序和四路归并排序 D树形选择排序和shell排序 5下列排序方法中，哪一个是稳定的排序方法？（B） 【北方 交通大学2001】 A直接选择排序 B二分法插入排序 C希尔排序 D快速排序 6若要求尽可能快地对序列进行稳定的排序，则应选（
5、B）【北 京邮电大学 2001】 A快速排序 B归并排序 C冒泡排序。 7如果待排序序列中两个数据元素具有相同的值，在排序前后 它们的相互位置发生颠倒，则称该排序算法是不稳定的。（CE ）就是不稳定的排序方法。【清华大学 1998 】 A起泡排序 B归并排序 CShell排序 D直接插入排 序 E简单选择排序 8若要求排序是稳定的，且关键字为实数，则在下列排序方法 中应选（ A ）排序为宜。【中科院计算所 2000 】 A直接插入 B直接选择 C堆 D快速 E基数 9若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是 稳定的，则可选择的排序方法是（C ）。 【中国科技大学，中 科院
6、计算所 1998】 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入 排序 10下面的排序算法中，不稳定的是（CDF）【北京工业大学 】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E. 基数排序 F.堆排序。 11下列内部排序算法中： 【北京工业大学 2000】 A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排 序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（CD ）（2）不稳定 的排序算法是（ADF）（3）在初始序列已基本有序（除去n个元 素中的某k个元素后即呈有序，kn）的情况下，排序效率最高 的算法是（B）（
7、4）排序的平均时间复杂度为O(nlogn)的算法 是（ACF ）为O(nn)的算法是（BDE ） 12排序趟数与序列的原始状态有关的排序方法是(CD)排序法。 【北京航空航天大学 1999 】（A） A插入 B. 选择 C. 冒泡 D. 快速 13下面给出的四种排序方法中，排序过程中的比较次数与排序 方法无关的是。( A ) 【北京航空航天大学 2000 】 A选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积 排序法 14对下列四种排序方法，在排序中关键字比较次数同记录初始 排列无关的是( BD )。【南京理工大学 2000 】 A直接插入 B. 二分法插入 C. 快速排序 D. 归
8、并排序 15在下列排序算法中,哪一个算法的时间复杂度与初始排序无 关（ D）。【北京理工大学 2001 】 A 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择 排序 16比较次数与排序的初始状态无关的排序方法是(D )。【北 方交通大学】 A直接插入排序B起泡排序 C快速排序 D简单选择排序 17数据序列（8，9，10，4，5，6，20，1，2）只能是下列排 序算法中的(C )的两趟排序后的结果。合肥工业大学 1999 】 A选择排序 B.冒泡排序 C.插入排序 D.堆排序 18数据序列（2，1，4，9，8，10，6，20）只能是下列排序 算法中的( A )的两趟排序后的结果。
9、【合肥工业大学 2000 】 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 19对一组数据（84，47，25，15，21）排序，数据的排列次 序在排序的过程中的变化为【南京理工大学 1997 】 （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 )。A. 选择 B. 冒泡 C. 快速 D. 插入 20对序列15，9，7，8，20，-1，4进行排序，进行一趟后数 据的排列变为4，9，-1，8，20，7，15；则采用的是（C）排 序。【南京理工大学 1998 】 A.
10、 选择 B. 快速 C. 希尔 D. 冒泡 21若上题的数据经一趟排序后的排列为9，15，7，8，20，-1 ，4，则采用的是（ C ）排序。 【南京理工大学 1998 】 A选择 B. 堆 C. 直接插入 D. 冒泡 22下列排序算法中( B )不能保证每趟排序至少能将一个元素放 到其最终的位置上。【合肥工业大学 2001 】 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 23下列排序算法中( C )排序在一趟结束后不一定能选出一个 元素放在其最终位置上。【南京理工大学 2001】 A. 选择 B. 冒泡 C. 归并 D. 堆 24下列序列中，（ C ）是执行第一趟快速排序
11、后所得的序列 。 【福州大学 1998】（D)A. 68，11，18，69 23，93，73 B. 68，11，69，23 18，93，73 C. 93，73 68，11，69，23，18 D. 68， 11，69，23，18 93，73 25有一组数据（15，9，7，8，20，-1，7，4） 用快速排序 的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。 【南京理工大学 1996 】 A下面的B，C，D都不对。 B9，7，8，4，-1，7，15，20 C20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15， 20 26一组记录的关键码为（46，79，56，3
12、8，40，84），则利 用快速排序的方法，以第一个记录为基准得到的一次划分结果为 （ C ）。 【燕山大学 2001 】 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) 27. 在下面的排序方法中，辅助空间为O（n）的是(D) 。【南京 理工大学】 A希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 28下列排序算法中，在待排序数据已有序时，花费时间反而最 多的是( C )排序。【南京理工大学 2001 】 A 冒泡 B. 希尔 C. 快速 D. 堆 29.下列
13、排序算法中，在每一趟都能选出一个元素放到其最终位 置上，并且其时间性能受数据初始特性影响的是：（ B ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是 （C）算法，最费时间的是（ D）算法。【南开大学 2000 】 (B) A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序 31. 就平均性能而言，目前最好的内排序方法是(D )排序法。【 西安电子科技大学 1998 】 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 32如果只想得到1000个元素组成的序列中第5个最小元素之前 的部分排序的序列，用（ D ）方法最快。 【清华大学 1998】 A起泡排序 B快速排列 CShell排序 D堆排序 E简单 选择排序
