0

我已经看到了一个关于应用于一组 Internet 事务的选择和插入排序稳定性的示例：

在此处输入图像描述

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

在此处输入图像描述

我的意思是，据我所知，选择排序会在无序部分右侧部分中选择元素的索引，并将其放入左侧部分的前面。在第一通芝加哥 09:00:00 处于正确位置，没有其他芝加哥时间更少。然后我们传递到 Phoenix 09:00:03，因此我们在右侧检查一个较小的元素（即 Chicago 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)

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

4

1 回答 1

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

于 2013-09-22T14:57:51.760 回答