8.6 内部排序算法的比较及应用·习题

教材导航 · 返回本节知识

复习入口

8.6 内部排序算法的比较及应用 · 8.6.1 内部排序算法的比较 · 8.6.2 内部排序算法的应用

本节共24题:选择题21题,综合应用题3题。每题答案紧接题目折叠显示。

文字转录进度:24/24题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P382 · 解析P384 · 目视转录

若要求排序稳定,且关键字为实数,则应选( )。

A. 直接插入排序

B. 选择排序

C. 基数排序

D. 快速排序

查看答案与解析

答案:A。

稳定性排除 B、D。按本章所述基数排序实现,不能直接对 float、double 实数排序,排除 C。

单项选择题 02

原书题目P382 · 解析P384 · 目视转录

时间复杂度 O(nlog⁡2n)O(n\log_2n) 且稳定的算法是( )。

A. 堆排序

B. 快速排序

C. 归并排序

D. 直接插入排序

查看答案与解析

答案:C。

堆、快速不稳定;直接插入时间复杂度为 O(n2)O(n^2)。

单项选择题 03

原书题目P382 · 解析P384 · 目视转录

n 个结点序列中已有十分接近有序的情况,直接插入、归并、快速排序的时间复杂度依次为( )。

A. O(n),O(n),O(n)O(n),O(n),O(n)

B. O(n),O(nlog⁡2n),O(nlog⁡2n)O(n),O(n\log_2n),O(n\log_2n)

C. O(n),O(nlog⁡2n),O(n2)O(n),O(n\log_2n),O(n^2)

D. O(n2),O(nlog⁡2n),O(n2)O(n^2),O(n\log_2n),O(n^2)

查看答案与解析

答案:C。

各算法的时间、空间复杂度及稳定性可参见本章表8.1。

单项选择题 04

原书题目P382 · 解析P384 · 目视转录

下列算法中,属于稳定排序的是(①),平均时间复杂度为 O(nlog⁡2n)O(n\log_2n) 的是(②),最好情况下可达线性时间的是(③)。(多选。)

Ⅰ. 冒泡排序

Ⅱ. 堆排序

Ⅲ. 选择排序

Ⅳ. 直接插入排序

Ⅴ. 希尔排序

Ⅵ. 归并排序

Ⅶ. 快速排序

查看答案与解析

答案:①Ⅰ、Ⅳ、Ⅵ;②Ⅱ、Ⅵ、Ⅶ;③Ⅰ、Ⅳ。

应从原理理解稳定性。堆与归并最好、最坏时间为同一数量级,均 O(nlog⁡2n)O(n\log_2n)。

单项选择题 05

原书题目P382 · 解析P384 · 目视转录

按辅助空间比较,堆排序、快速排序、归并排序关系为( )。

A. 堆排序<快速排序<归并排序

B. 堆排序<归并排序<快速排序

C. 堆排序>归并排序>快速排序

D. 堆排序>快速排序>归并排序

查看答案与解析

答案:A。

堆空间 O(1)O(1);快速平均 O(log⁡2n)O(\log_2n)、最坏 O(n)O(n);归并 O(n)O(n)。

单项选择题 06

原书题目P382 · 解析P384 · 目视转录

排序趟数与初态无关的是( )。

Ⅰ.快速 Ⅱ.简单选择 Ⅲ.冒泡 Ⅳ.基数

A. Ⅰ、Ⅲ

B. Ⅱ、Ⅳ

C. Ⅰ、Ⅱ、Ⅳ

D. Ⅰ、Ⅳ

查看答案与解析

答案:B。

冒泡趟数1~n−1,与初态有关;简单选择每趟选一个最大或最小值,固定n−1;基数每趟分配收集,固定d趟。快速的划分次数与枢轴和划分均衡性有关,初始基本有序时可能极不均衡。

单项选择题 07

原书题目P382 · 解析P384 · 目视转录

排序趟数与初态有关的是( )。

A. 直接插入排序

B. 二路归并排序

C. 快速排序

D. 堆排序

查看答案与解析

答案:C。

直接插入固定n−1趟,二路归并固定⌈log₂n⌉趟,堆建好后需n−1趟输出并调整,均与初态无关。

单项选择题 08

原书题目P382 · 解析P384 · 目视转录

对 n 个元素排序,趟数肯定为 n−1 的是( )。

A. 直接插入和快速

B. 冒泡和快速

C. 简单选择和直接插入

D. 简单选择和冒泡

查看答案与解析

答案:C。

简单选择与直接插入始终n−1;冒泡1~n−1;快速约log₂n~n−1,取决于初态及划分方法。

单项选择题 09

原书题目P382 · 解析P384 · 目视转录

序列初态 {1,2,3,4,5,10,6,7,8,9},要使元素比较次数最少,应采用( )。

A. 插入排序

B. 选择排序

C. 希尔排序

D. 冒泡排序

查看答案与解析

答案:A。

选择比较次数与初态无关,先排除。基本有序时插入比较少,本题仅n−1+4次,希尔、冒泡均远大于此。

单项选择题 10

原书题目P382 · 解析P385 · 目视转录

相同元素个数、不同初态的序列,总比较次数相同的是( )。

A. 折半插入排序和简单选择排序

B. 基数排序和归并排序

C. 冒泡排序和快速排序

D. 堆排序

查看答案与解析

答案:A。

简单选择总比较次数确定。原书认为折半插入每趟比较为 O(log⁡2m)O(\log_2m),m为当前已排序子序列长度,因此比较次数也确定。基数不是基于比较的排序,其他算法比较次数与初态有关。

单项选择题 11

原书题目P382 · 解析P385 · 目视转录

一般情况下,以下查找效率最低的数据结构是( )。

A. 有序顺序表

B. 二叉排序树

C. 堆

D. 平衡二叉树

查看答案与解析

答案:C。

堆适合排序,但查找时整体无序,效率不及其他查找结构。

单项选择题 12

原书题目P382 · 解析P385 · 目视转录

多核CPU可同时执行独立任务,归并排序各归并段可并行。下列不能并行执行的有( )。

Ⅰ.基数 Ⅱ.快速 Ⅲ.冒泡 Ⅳ.堆

A. Ⅰ、Ⅲ

B. Ⅰ、Ⅱ

C. Ⅰ、Ⅲ、Ⅳ

D. Ⅱ、Ⅳ

查看答案与解析

答案:A。

基数每趟利用前趟已排好的序列,无法按各趟并行;快速各划分子序列互不影响,可并行;冒泡每趟处理所有未排序元素,无法按此方式并行;堆中左右子堆执行互不影响,可以并行。

单项选择题 13

原书题目P383 · 解析P385 · 目视转录

【2009 统考真题】{11,12,13,7,8,9,23,4,5} 是某算法第二趟结果,该算法只能是( )。

A. 冒泡排序

B. 插入排序

C. 选择排序

D. 二路归并排序

查看答案与解析

答案:B。

冒泡、选择每趟有元素最终就位,题中两端的 {11,12}、{4,5} 并非最终位置,排除。归并第二趟前4个元素应有序,但11,12,13,7不有序,排除。

单项选择题 14

原书题目P383 · 解析P385 · 目视转录

【2010 统考真题】对 (2,12,16,88,5,10) 排序,前三趟为:

  1. 2,12,16,5,10,88
  2. 2,12,5,10,16,88
  3. 2,5,10,12,16,88

可能采用的是( )。

A. 冒泡排序

B. 希尔排序

C. 归并排序

D. 基数排序

查看答案与解析

答案:A。

每趟从前向后比较使最大值沉底,符合冒泡。归并第一趟仍为(2,12,16,88,5,10),基数第一趟为(10,2,12,5,16,88),希尔也不符合。

单项选择题 15

原书题目P383 · 解析P385 · 目视转录

【2012 统考真题】每趟处理所有未确定最终位置的元素。下列每趟结束均至少确定一个元素最终位置的方法是( )。

Ⅰ.简单选择 Ⅱ.希尔 Ⅲ.快速 Ⅳ.堆 Ⅴ.二路归并

A. 仅Ⅰ、Ⅲ、Ⅳ

B. 仅Ⅰ、Ⅲ、Ⅴ

C. 仅Ⅱ、Ⅲ、Ⅳ

D. 仅Ⅲ、Ⅳ、Ⅴ

查看答案与解析

答案:A。

简单选择每趟选最小值放最终位置;希尔只使子表局部有序,不能保证;快速使枢轴最终就位;堆每次交换根与表尾,确定其最终位置;二路归并仅合并有序段,不能保证最终就位。

单项选择题 16

原书题目P383 · 解析P385 · 目视转录

【2017 统考真题】内部排序选择归并而非插入,可能理由是( )。

Ⅰ.归并代码更短 Ⅱ.归并占用空间更少 Ⅲ.归并运行效率更高

A. 仅Ⅱ

B. 仅Ⅲ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅰ、Ⅲ

查看答案与解析

答案:B。

归并代码更复杂、空间 O(n)O(n),插入空间 O(1)O(1);但归并时间 O(nlog⁡2n)O(n\log_2n),插入 O(n2)O(n^2)。

单项选择题 17

原书题目P383 · 解析P385 · 目视转录

【2017 统考真题】将顺序存储更换成链式存储,时间效率会降低的是( )。

Ⅰ.插入 Ⅱ.选择 Ⅲ.冒泡 Ⅳ.希尔 Ⅴ.堆

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅲ、Ⅳ

D. 仅Ⅳ、Ⅴ

查看答案与解析

答案:D。

插入、选择、冒泡在两种存储下均为 O(n2)O(n^2)。希尔、堆均利用顺序存储的随机访问特性,链式存储不支持,时间复杂度会增加。

单项选择题 18

原书题目P383 · 解析P385 · 目视转录

【2019 统考真题】选择排序算法,除时空效率外,还需考虑( )。

Ⅰ.数据规模 Ⅱ.存储方式 Ⅲ.稳定性 Ⅳ.初始状态

A. 仅Ⅲ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅱ、Ⅲ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

查看答案与解析

答案:D。

小规模可选 O(n2)O(n^2) 简单算法,大规模宜 O(nlog⁡2n)O(n\log_2n),大到内存放不下需外部排序,Ⅰ正确。有些算法如堆仅适用顺序存储,Ⅱ正确。有稳定性要求应排除不稳定算法,Ⅲ正确。基本有序时直接插入效率高,冒泡、直接插入可达 O(n)O(n),归并仍为 O(nlog⁡2n)O(n\log_2n),Ⅳ正确。

单项选择题 19

原书题目P383 · 解析P385 · 目视转录

【2020 统考真题】对大部分已有序数组,直接插入比简单选择效率更高,原因是( )。

Ⅰ.直接插入比较次数更少。

Ⅱ.直接插入辅助空间更少。

Ⅲ.直接插入移动次数更少。

A. 仅Ⅰ

B. 仅Ⅲ

C. 仅Ⅰ、Ⅱ

D. Ⅰ、Ⅱ和Ⅲ

查看答案与解析

答案:A。

有序时直接插入比较n−1次,简单选择比较n(n−1)/2次,Ⅰ正确。两者空间都 O(1)O(1),Ⅱ错误。全有序时移动均0;通常直接插入需依次挪位,简单选择仅交换找到的最小值,后者移动较少,Ⅲ错误。

单项选择题 20

原书题目P383 · 解析P386 · 目视转录

【2022 统考真题】采用直接插入而非快速排序,可能原因是( )。

Ⅰ.大部分已有序 Ⅱ.元素数量很少 Ⅲ.要求空间 O(1)O(1) Ⅳ.要求稳定

A. 仅Ⅰ、Ⅱ

B. 仅Ⅲ、Ⅳ

C. 仅Ⅰ、Ⅱ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

查看答案与解析

答案:D。

算法适合初态适合数量空间稳定性
直接插入大部分有序较少O(1)稳定
快速基本无序较多平均O(log₂n)不稳定

四项均可能是理由。

单项选择题 21

原书题目P383 · 解析P386 · 目视转录

【2023 统考真题】下列不稳定的算法是( )。

Ⅰ.希尔 Ⅱ.归并 Ⅲ.快速 Ⅳ.堆 Ⅴ.基数

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅴ

C. 仅Ⅰ、Ⅲ、Ⅳ

D. 仅Ⅲ、Ⅳ、Ⅴ

查看答案与解析

答案:C。

稳定的有插入、冒泡、归并、基数;不稳定的有简单选择、快速、希尔、堆。

综合应用题

综合应用题 01

原书题目P384 · 解析P386 · 目视转录

关键字 {3,7,6,9,7,1,4,5,20},排序的最小交换次数是多少?

查看答案与解析

直接插入交换更多,采用简单选择。按原书过程:

步骤序列交换
初始3,7,6,9,7,1,4,5,20
11,7,6,9,7,3,4,5,201与3
21,3,6,9,7,7,4,5,203与7
31,3,4,9,7,7,6,5,204与6
41,3,4,5,7,7,6,9,205与9
51,3,4,5,6,7,7,9,206与7

最小交换5次。注意求的是交换次数,并非移动次数或比较次数。

综合应用题 02

原书题目P384 · 解析P386 · 目视转录

顺序表用数组A[]表示,元素存于下标1~m+n,前m个递增有序、后n个递增有序,设计使全表有序的算法。

  1. 基本思想。
  2. C/C++实现及关键注释。
  3. 时间与空间复杂度。
查看答案与解析
  1. 视为已完成前m个元素插入的表,从m+1开始将后n个依次插入前面的有序表。
  2. 实现如下。
void Insert_Sort(ElemType A[], int m, int n) {
    int i, j;
    for (i = m + 1; i <= m + n; i++) {
        A[0] = A[i];                // 哨兵
        for (j = i - 1; A[j] > A[0]; j--)
            A[j + 1] = A[j];
        A[j + 1] = A[0];
    }
}
  1. 原书给出最坏比较与移动次数均为 O(mn)O(mn),时间 O(mn)O(mn)、空间 O(1)O(1)。也可把两段归并,时间 O(m+n)O(m+n)、空间 O(m+n)O(m+n)。

综合应用题 03

原书题目P384 · 解析P386 · 目视转录

数组中存有元素 K₁,K₂,…,Kₙ,要求把Kₙ放在排序后的正确位置。编写算法,关键字比较次数不超过n。

查看答案与解析

以末元素Kₙ为枢轴,进行一趟快速划分,先从前向后,再从后向前查找。

int Partition(ElemType K[], int n) {
    int i = 1, j = n;
    ElemType pivot = K[j];
    while (i < j) {
        while (i < j && K[i] <= pivot)
            i++;
        if (i < j)
            K[j] = K[i];
        while (i < j && K[j] >= pivot)
            j--;
        if (i < j)
            K[i] = K[j];
    }
    K[i] = pivot;
    return i;
}

返回枢轴最终位置。