为什么选择排序不是稳定？ [英] Why is Selection Sort not stable?

问题描述

这可能是微不足道的，但我不明白为什么选择的默认实现排序是不是稳定？

This might be trivial, but I don't understand why the default implementation of Selection Sort is not stable?

在每次迭代中你会发现剩下的数组中最小元素。当发现这个最小的，你可以选择第一个最低你会发现，只有更新它，当一个元素实际上是比它小。因此，所选择的元素在每次迭代是第一个最小的 - 这意味着，这是第一次在previous排序顺序。所以，我的理解，当前的排序不会破坏由previous排序平等的元件所产生的订单。

At each iteration you find the minimum element in the remaining array. When finding this minimum, you can choose the first minimum you find, and only update it when an element is actually smaller than it. So, the chosen element at each iteration is the first minimum - meaning, it's first on the previous sort order. So, to my understanding, the current sort will not destroy an order generated by a previous sort on equal elements.

我在想什么？

推荐答案

一个小例子：

让在B = B

＆LT; B>，＆LT; B>，＆LT;一>，＆LT; C>（用＆LT; B＆LT; C）

< B > , < b > , < a > , < C > (with a < b < c)

一个周期的序列进行排序，但是B和b的顺序后已经改变：

After one cycle the sequence is sorted but the order of B and b has changed:

＆LT;一>，＆LT; B>，＆LT; B>，＆LT; C>

< a > , < b > , < B > , < c >

但你却可以实现，而不是切换选择排序，如果你稳定，插入最小值。但是，要成为有效的，你应该有一个支持插入低成本的数据结构或以其他方式，你最终与二次复杂性。

But you can however implement Selections Sort stable if you, instead of switching, insert the minimum value. But for that to be efficient you should have a data structure that supports insertion at a low cost or otherwise you end up with quadratic complexity.

这篇关于为什么选择排序不是稳定？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！