这可能是微不足道的，但我不明白为什么默认实现选择排序 http://en.wikipedia.org/wiki/Selection_sort不稳定？
在每次迭代中，您都会找到剩余数组中的最小元素。当找到这个最小值时，您可以选择找到的第一个最小值，并且仅当元素实际上小于它时才更新它。因此，每次迭代时选择的元素是第一个最小值 - 这意味着它是先前排序顺序中的第一个。因此，据我了解，当前排序不会破坏先前对相等元素进行排序生成的顺序。
我缺少什么？
一个小例子：
设 b = B 为
、、、（其中 a
一个循环后，序列已排序，但 B 和 b 的顺序发生了变化：
、、、
但是，如果您不进行切换，而是插入最小值，则可以实现稳定的选择排序。但为了提高效率，您应该拥有一个支持低成本插入的数据结构，否则您最终会遇到二次复杂度。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
