数据结构之排序绪论

排序的基本概念

排序的定义

排序是将列表中的元素重新排列，以使其按照关键字有序的过程。通常，计算机中的表希望按照关键字有序，以便于查找。排序的确切定义如下：

  • 输入：$ n $ 个记录 $ R_1, R_2, , R_n $，对应的关键字为 $ k_1, k_2, , k_n $。
  • 输出：输入序列的一个重排 $ R_1', R_2', , R_n' $，使得 $ k_1' k_2' k_n' $（其中“<”可以替换为其他比较符号）。

算法的稳定性

  • 稳定性定义：如果待排序表中有两个元素 $ R_i $ 和 $ R_j $ 的关键字相同（即 $ key_i = key_j $），且在排序前 $ R_i $ 在 $ R_j $ 前面，那么使用某一排序算法排序后，若 $ R_i $ 仍然在 $ R_j $ 前面，则称该排序算法为稳定的；否则称为不稳定的。
  • 稳定性的重要性：稳定性并不能完全衡量一个算法的优劣，而是描述算法的性质。当待排序表中的关键字不允许重复时，排序结果是唯一的，这时稳定性就无关紧要。

排序算法的分类

根据数据元素是否能全部在内存中存放，排序算法可以分为两类：

  1. 内部排序：在排序期间，元素全部存放在内存中。
  2. 外部排序：在排序期间，元素无法全部同时存放在内存中，必须根据要求在内存与外存之间不断移动。

一般情况下，内部排序算法在执行过程中进行两种操作：

  • 比较：通过比较两个关键字的大小，确定元素的前后关系。
  • 移动：通过移动元素以达到有序状态。

需要注意的是，并非所有的内部排序算法都依赖于比较操作，例如基数排序就不基于比较。

排序算法的种类

每种排序算法都有各自的优缺点，适用于不同的环境。常见的排序算法可分为以下五大类：

  1. 插入排序
  2. 交换排序
  3. 选择排序
  4. 归并排序
  5. 基数排序

选择题

01. 下述排序方法中，不属于内部排序方法的是()。

  • 选项：

    • A. 插入排序
    • B. 选择排序
    • C. 拓扑排序
    • D. 冒泡排序

  • 答案：C. 拓扑排序

  • 解析：拓扑排序是将有向图中所有结点排成一个线性序列，虽然也是在内存中进行的，但它不属于内部排序方法的范畴，也不符合传统排序的定义。

02. 排序算法的稳定性是指()。

  • 选项：

    • A. 经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
    • B. 经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
    • C. 排序算法的性能与被排序元素个数关系不大
    • D. 排序算法的性能与被排序元素的个数关系密切

  • 答案：A. 经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变

  • 解析：稳定性定义为：若关键字相同的元素在排序后相对位置不变，则称该排序算法为稳定的。绝对位置不变的说法是不正确的，选项 B 是错误的。选项 C 和 D 与稳定性无关。

03. 下列关于排序的叙述中，正确的是()。

  • 选项：

    • A. 稳定的排序方法优于不稳定的排序方法
    • B. 对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同
    • C. 排序方法都是在顺序表上实现的，在链表上无法实现排序方法
    • D. 在顺序表上实现的排序方法在链表上也可以实现

  • 答案：B. 对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同

  • 解析：不同的排序算法可能产生不同的排序结果，尤其在关键字有重复的情况下。选项 A 的说法不严谨，算法的稳定性与优劣无关。选项 C 错误，因为虽然某些排序算法不适用于链表，但不是说无法在链表上实现排序。选项 D 也不一定成立，因为某些排序算法的实现可能依赖于随机访问。

04. 对任意7个关键字进行基于比较的排序，至少要进行()次关键字之间的两两比较。

  • 选项：

    • A. 13
    • B. 14
    • C. 15
    • D. 16

  • 答案：A. 13

  • 解析：对于任意 $ n $ 个关键字的基于比较的排序，最少的比较次数在最坏情况下为 $ _2(n!) $。当 $ n = 7 $ 时：

    $ _2(7!) = _2(5040) ( 13) $

    所以答案是 13 次比较。