第223章（2 / 2）

3. 归并排序

- 时间复杂度：时间复杂度始终为 。

- 稳定性：归并排序是稳定的排序算法。在合并两个有序子序列时，如果两个子序列中有相同的元素，按照顺序将左边子序列中的元素先放入合并后的序列，从而保证了相同元素的相对顺序不变，符合题目要求，c选项正确。

4. 直接插入排序

- 时间复杂度：时间复杂度为 ，在最好情况下（序列已经有序）时间复杂度为 ，但不满足在 时间内完成排序的 要求，所以d选项不合适。

答案：c

栈的特点及输出序列可能性分析

栈是一种后进先出（Last In First out，LIFo）的数据结构，元素进栈和出栈的顺序遵循这个特点。

我们可以通过模拟栈的操作过程来分析各个选项是否可行：

选项A

输入序列为 a ， b ， c ， d ， e ，如果按照进栈一个元素就马上出栈一个元素的操作方式，就可以得到输出序列为 a ， b ， c ， d ， e ，是完全可行的，符合栈的操作规则。

选项b

可以先将 a ， b ， c ， d 依次进栈，此时栈内元素从栈底到栈顶依次为 a ， b ， c ， d ，然后依次出栈得到 d ， c ， b ， a ，接着将 e 进栈再出栈，最终输出序列就是 d ， e ， c ， b ， a ，这种操作符合栈的后进先出特点，是可行的。

选项c

若要输出 d ，则需要先将 a ， b ， c ， d 依次进栈，然后 d 出栈；接着若要输出 c ，此时栈内剩下 a ， b ， c ， c 出栈符合规则；再要输出 e ，但是 e 还未进栈，必须先将 e 进栈才能输出，而按照这个输出序列此时要输出 a 了，也就是在 e 还没进栈操作之前就输出了其他元素，不符合栈后进先出的原则，所以该输出序列是不可能实现的。

选项d

可以先将 a ， b ， c ， d ， e 全部依次进栈，此时栈内元素从栈底到栈顶依次为 a ， b ， c ， d ， e ，然后再依次出栈，就能得到输出序列 e ， d ， c ， b ， a ，是符合栈操作规则的。

综上，选择c选项，它是栈的不可能输出的序列。