CS61B 课程笔记（Excmprep 13 Sorting Exam Prep)

1. 识别排序算法

在这一部分中，我们给定了一些排序过程的中间步骤，需要根据这些步骤识别出对应的排序算法。

归并排序的一个显著特点是左右两半不会相互影响，直到最终合并。输入列表：1429, 3291, 7683, 1337, 192, 594, 4242, 9001, 4392, 129, 1000

归并排序的步骤：

快速排序的特点是以第一个元素作为枢轴，然后将小于枢轴的元素放到左边，大于枢轴的元素放到右边。输入列表：1337, 192, 594, 129, 1000, 1429, 3291, 7683, 4242, 9001, 4392

快速排序的步骤：

插入排序每次从前面开始，将当前元素移动到前面已排序部分的正确位置。输入列表：1337, 1429, 3291, 7683, 192, 594, 4242, 9001, 4392, 129, 1000

插入排序的步骤：

堆排序的关键在于构建最大堆，并不断将最大值放置到末尾。输入列表：1429, 3291, 7683, 9001, 1000, 594, 4242, 1337, 4392, 129, 192

堆排序的步骤：

假设有一个未排序的数组，经过若干次选择排序后我们得到了部分排序后的结果。对于给出的关系写出 <，> 或 ? 表示元素之间的关系是否确定：

False：快速排序的最坏情况是$ Θ(N²)$，当每次划分都非常不均匀时会发生这种情况。

输入数组很小或几乎有序。插入排序在数组已经排序的情况下的最好时间复杂度为 $Θ(N)$。

示例：5, 4, 3, 2, 1。任何降序排列的数组都会导致最坏情况。

False：堆排序并不稳定。稳定性意味着相等的元素在排序后仍保持原有的相对顺序，但堆的操作可能破坏这种顺序。

这里是对给定的排序过程进行特性分析的题目，考察的是不同排序算法的运行时间特性、元素交换次数以及元素比较行为等。

你需要根据排序算法的性质，选择正确的排序算法。可以从下列答案中选择：

注意：每个问题的答案可能有多个，并且同一个答案可能多次使用。若题目给出的条件不符合任何排序算法，则选择 "N"。

A, B, C 受 $ (NN) $ 的下界限制：
- 这是经典的比较排序算法的理论下界，所有基于比较的排序算法（如快速排序、归并排序、选择排序）在最坏情况下都受该下界的限制。
- 答案: A, B, C
B, E 具有比快速排序最坏情况更好的最坏情况运行时间：
- 快速排序在最坏情况下的时间复杂度是 $O(N^2)$ ，但归并排序和堆排序的最坏时间复杂度是 $O(N\log N)$ 。
- 答案: B, E
C 在最坏情况下执行 $ (N)$ 次元素交换：
- 选择排序的特点是在每次迭代中都会找到最小的元素并将其交换到正确位置。无论输入数据如何，选择排序在最坏情况下都执行 $ N-1 $ 次交换，因此时间复杂度是 $\Theta(N)$ 。
- 答案: C
A, B, D 从不比较相同的两个元素两次：
- 归并排序和插入排序每次比较时，不会再次比较相同的元素。快速排序（Hoare 分区法）在左右指针交替时，也不重复比较相同的元素。
- 答案: A, B, D
N 在某些输入下的最佳情况运行时间为 $ (N)$ ：
- 没有任何常规的比较排序算法在最佳情况下运行时间可以达到 $ (N) $。比较排序的最佳运行时间为 $ O(N) $，因此选择N。
- 答案: N