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

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之前。

Answer 2

我认为这是一种快速的方式。在这里，我们可以看到以下步骤：

• 数组(pivotValue)中引用元素的随机选择，其中对数组的元素进行重新排序。
• 移动所有大于右侧引用的值，以及较低支持的所有值。
• 重复算法，用于排序数组的左和右，而每个元素不会出现在其位置上。

为什么我这么想：

它肯定不是气泡排序，因为它比较数组的前两个元素，所以第一步应该是2 5 6 1 3 4

它不是插入排序，因为它是一个顺序算法。在第一步中，我们看到比较了第一个和最后一个元素。

它不是一个选择排序，因为它找到最低值并将其移动到顶部，因此，第一步应该是1 5 2 6 3 4

它不是合并排序，因为数组被划分为两个子数组。在这种情况下，我们看到交互“第一”和“第二”部分。

Answer 3

要解决这个问题，您所要做的就是为每个排序算法创建一个函数，但是包括一个语句，用于在每个交换后打印出数组。然后将您的打印友好排序算法应用于初始数组5、2、6、1、3、4，并查看哪种排序方法产生相同的输出。此外，这将帮助您比较所有不同的方法。