几种排序算法的序列

Question

我在麻省理工学院的一些期中或期末考试中看到，下面的问题以同样的方式重复和重复。

我们在一个排序算法的某个步骤中显示了一个数组。

5,3,1,9,8,2,4,7 2，3，1，4，5，8，9 1,2,3,4,5,8,9,7 1，2，3，4，5，8，7 9 1,2,3,4,5,7,8,9

使用了哪种插入排序/快速排序/合并排序/ Exchange排序？

我是如何找到这个问题的解决方法的？

编辑:我认为这是快速排序，因为每个级别，有些元素比枢轴低，而有些元素更大.

Answer 1

在这种情况下，你可以找到一些模式，如果你认为有一个或b)与简单消除。让我们试着消除：

1)插入排序不能是插入排序，因为插入排序从一开始就开始，并将范围0，k作为已检查值的排序子数组。然后，它一个接一个地继续，因此我们首先将3 5 插入到、5、等之前，就像我们最初将[5]视为大小为1的排序子数组一样，并将3作为整个数组中的下一个值插入到其中。

2)合并排序将首先排序邻居，就像它首先递归地将整个数组视为单个元素数组一样，然后返回递归树并合并邻居，如下所示：

[3,5],[1,9],[2,8],[4,7]
[1,3,5,9],[2,4,7,8]
[1,2,3,4,5,6,7,8]

[]显示在每个步骤中对哪些部分进行排序。

这意味着，经过一次传递后，邻居将被排序为。

3) exchange排序也有不同的顺序--第二行应该以3开头，因为您将交换5和3，然后是5和1等。因此，经过一次测试后，如果我的泡沫类型适合我的话，我们就会从5,3,1,9,8,2,4,7进入3,1,5,8,2,4,7,9。我们比较每对和交换if元素在i+1大于在i。这样，最后一个元素将是最大的。

4)正如您公正地指出的，这是一种快速排序，因为在每一步中，我们都可以清楚地看到数组是围绕某个值4旋转的，然后您将左半部围绕2旋转，右半部分在5左右旋转等等。

黑体部分是我刚才所说的模式，既然你知道它们，你可以很容易地检查它是哪一个:-)

Answer 2

它应该是快速排序，这不仅是因为分区的证据，而且也是一个有趣的事实:在某种程度上，数组的一部分发生了变化。

现在，让我们讨论每种算法：

插入排序将为您提供一个必须对前几个元素进行排序的模式，但显然我们没有这个模式；

如果前一个元素大于后一个元素，则气泡排序(exchange )将继续交换邻居，因此最后一个k元素将在k迭代之后排序。基于这两个事实，在每次迭代之后，我们将不会有一个b < a存在的相邻b < a。然而，序列并不遵循这一点，比如第一个序列中的术语(3，1)仍然存在于第二个序列中。

Merge sort首先将数组拆分为2+2+2子数组，然后将其合并为4+4，最后是一个由8个元素组成的排序数组，因此完全应该采取3个步骤，但这里有4个步骤，所以不会进行合并排序。