题2

题2

题目

Q:以下排序算法中时间复杂度为 且稳定的是 ( ).
A. 堆排序 B. 快速排序 C. 归并排序 D. 直接插入排序

分析

A:堆排序不稳定的
快排是通过分治来排序的，快排快在它是粗略分堆，然后划分子问题，再处理这个堆
我认为归并不一定是稳定，因为划分的时候可能刚好把两个相同的元素分开了，但是归并排序是稳定的

解

C
堆排序和快速排序不是稳定排序算法，而直接插入排序算法的时间复杂度为 。
归并排序稳定性的关键在于元素合并的过程，而非划分的过程。

1. 划分阶段不影响稳定性： 归并排序的划分阶段只是将数组逻辑上分成两个子数组，并没有改变元素的相对位置。 即使两个相同的元素被分到不同的子数组，也不会影响最终的排序结果。
2. 合并时保证稳定性： 归并排序的核心在于合并两个已排序的子数组。 在合并过程中，对于值相同的元素，会优先选择左侧子数组的元素放入合并后的数组。 由于划分时保持了原数组的顺序，因此相同元素在原数组中的相对位置就决定了它们在合并后数组中的相对位置，保证了稳定性。
   举个例子，假设有两个待合并的子数组：

[3, 5, 5, 7] 和 [2, 5, 6, 8]

其中左侧子数组中有两个相同的元素 5。 在合并过程中，当比较到第一个 5 时：

• 由于左侧子数组的 5 比右侧子数组的 6 小，所以将左侧子数组的 5 放入合并后的数组。
• 接下来，比较到第二个 5 时，由于左侧子数组的 5 等于右侧子数组的 5， 仍然会优先选择左侧子数组的 5 放入合并后的数组。
  这样就保证了两个 5 在合并后的数组中依然保持了原有的相对顺序。
• 归并排序的划分阶段不影响稳定性，因为只是逻辑上的划分，没有改变元素的相对位置。
• 归并排序的合并阶段保证了稳定性，因为它对值相同的元素，会优先选择左侧子数组的元素，从而保持了元素在原数组中的相对位置。

Q:快排不稳定的原因？
A: 快速排序的关键是 分区（partition） 操作。分区操作会选择一个元素作为 基准（pivot），然后将数组分成两半，左半部分包含所有小于基准的元素，右半部分包含所有大于基准的元素。
不稳定的原因：
1. 不同位置的相同元素： 假设我们要排序的数组里有相同元素 a，在数组中有多个 a。快速排序分区的时候，可能会将 不同位置的相同元素 a 分到不同的分区。
2. 相对位置变化： 分区操作结束后，我们需要递归地对两个分区进行排序。在递归排序过程中，相同元素 a 的相对位置可能会发生变化。
举个例子：
假设我们要排序的数组是: [2, 5, 3, 5, 1]。
如果我们选择 3 作为基准，分区后会变成： [2, 1, 3, 5, 5]。
你会发现，原本在数组位置 1和 3 的 5，经过分区后分别在位置 3 和 4 了，它们的相对位置发生了改变。 虽然最终它们在排序后会排在正确的位置，但 不稳定性 意味着相同元素之间的相对顺序可能不再保持。