哪种排序算法产生这些步骤？

Question

这是今天考试中的一个多项选择题,并且(至少)其中一个答案应该是真的,但对我来说,他们看起来都错了.

分类步骤为:
5 2 6 1 3 4
4 2 6 1 3 5
4 2 5 1 3 6
4 2 3 1 5 6
1 2 3 4 5 6

可用的答案是:冒泡排序,插入排序,选择排序,合并排序和快速排序.

Answer 1

没有一个。

• 冒泡排序：没有。经过 k 步后，最后 k 个元素应该是排序后的 k 个最大元素。
• 插入排序：无。经过 k 步后，应该对前 k 个元素进行排序。
• 选择排序：无。经过 k 步后，前 k 个元素应该是最小的，已排序。
• 合并排序：没有。经过 k 步后，一个值只能移动2^k - 1位置。（5 在 k=1 时移动 5 个位置）
• 快速排序：没有。无论枢轴是什么，1 和 6 是极值，它们都可以保持在这个初始位置。

关于快速排序：为了明确这是不可能的，让我们枚举第一步的每个枢轴的结果：

• 5 [2134] - 5 - [6]：。（2134 可以任意顺序）
• 2：[1] - 2 - [5634]
• 6：[52134] - 6
• 1：1 - [52634]
• 3：[21] - 3 - [564]
• 4：[213] - 4 - [56]

看到所有这些与OP的输出不兼容的一种明显方法是，在每种情况下， 都1在 之前6，无论您如何实现枢轴或分区。