在一个例子中关于选择排序的稳定性，这是正确的吗？

Question

我看过一个例子，关于选择和插入排序的稳定性应用于一组互联网事务：

​

​

我已经进行了一次遍历，尝试通过使用位置条件的选择排序来对其进行排序：

​

​

我的意思是，就我所知，选择排序选择元素的索引，在无序的部分，右部分，并把它放在左边部分的前面。在第一次通过芝加哥09:00:00是在正确的位置，没有其他芝加哥的时间更少。然后我们传递到Phoenix 09:00:03，所以我们检查右侧的一个较小的元素(即芝加哥09:00:59)，因为这个元素更小，我们应该得到：

Chicago 09:00:00
Chicago 09:00:59

但是在示例中说，因为我们使用选择排序是不稳定的，而使用插入排序可以是稳定的

在我的比较中，我做错了什么？

我还在这里看到了另一个示例，其中包含了这个示例：

Sort this elements
(4,0)(4,1)(1,0)

好的，如果我使用选择排序，并且我只检查了每个元组的第一个元素，我将得到：

(1,0)(4,1)(4,0)

好吧，它看起来并不稳定，但它告诉我们，如果我们使用插入排序，我们最终会得到：

(1,0)(4,0)(4,1)

但如果我对原始数组稍作修改，如下所示：

(4,1)(4,0)(1,0)

我们只比较第一个元素，插入排序也不稳定，因为我们将以：

(1,0)(4,1)(4,0)

好的，如果我们将这两个元素进行比较，那么选择排序也可以是稳定的，这些证明有什么问题？

Answer 1

在上一个示例中，插入排序是稳定的。排序算法中的稳定性只是意味着具有相同键的项将保持其相对于彼此的相同顺序。

因此，在您的上一个示例中，您有：

(4,1)(4,0)(1,0)

而插入排序的结果是：

(1,0)(4,1)(4,0)

项(4,1)和(4,0)彼此保持了相同的顺序。也就是说，在原始数组中，(4,1)位于(4,0)之前，而在最终数组中，它位于该项之前。排序是稳定的。

此外，使用选择排序对任何特定数组进行排序的结果可能表明选择排序是稳定的。也就是说，不能保证选择排序会改变相等项的相对顺序。例如，以以下内容开头：

(4,1)(1,0)(4,0)

选择排序将生成

(1,0)(4,1)(4,0)

在这种情况下，选择排序不会更改(4,1)和(4,0)的相对顺序。但这并不意味着选择排序是稳定的。毕竟，即使是停了的时钟也是一天两次正确的。