，这是正确的吗？

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)的相对顺序。但这并不意味着选择排序是稳定的。毕竟，即使是一个停止的时钟，一天两次都是正确的。