简单(直接)选择排序的稳定性？

Question

有的教材说他不稳定
有的教材说所有时间复杂度为O(n*n)的简单排序都是稳定的 简单排序包括起泡、插入、简单选择等 并说稳定的排序方法可以有不稳定的实现算法例如：简单排序
严蔚敏的书上的算法是不稳定的
但严蔚敏的书又说所有时间复杂度为O(n^2)的简单排序算法都是稳定的 简单排序包括 起泡 简单选择 直接插入等 简单选择排序时间复杂度是O(n^2)
所以严蔚敏自相矛盾
有的书为了说明稳定的排序方法能找到不稳定的实现方法 特别举例说简单选择排序就是这样 但没有给出程序

按所有我能找到的数据结构教材定义给出的算法 简单选择排序确实都是不稳定的 为何有些书声称它稳定 是否是简单选择排序的排序思想还不统一？

Answer 1

简单选择排序是不稳定排序。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

扩展资料：

简单选择排序的最优情况：

最好情况下，即待排序记录初始状态就已经是升序排列了，则不需要移动记录。

对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。

排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法。

参考资料来源：百度百科-简单选择排序

参考资料来源：百度百科-排序算法稳定性

Answer 2

举个栗子:(要求从小到大排序)
8 5 8 7 9
简单选择排序:
第二次外循环8和8的相对顺序就发生了改变,违反了稳定性的定义,故不稳定;
冒泡排序:
两两元素之间比较,并不会改变相对顺序,故稳定;
当然,稳定是相对既有条件而言的,这就是另一个问题了.

Answer 3

举的例子都非常的差，非常容易给人造成误解，看我的例子就可以了，5，1，2，1*，从小到大排序，5最大，会和队尾元素交换，变为1*，1，2，5。
其他人答案不好的一点在于，以2,4,4*，3为例，很容易让人误解，只要选择的时候，选择最后的那个4*与3交换，不就依然符合稳定性了么，所以其它例子都不要看了

Answer 4

按照找最小值，与无序区首部交换的思想则不稳定：

排序前：
2,4,4*，3
排序后：
2,3,4*，4本回答被网友采纳

Answer 5

朴素的直接选择排序是不稳定的，这毫无疑问。当然可以写成稳定的版本。
稳定的排序：直接插入排序、冒泡排序、归并排序
不稳定的排序：希尔排序、直接选择排序、堆排序、快速排序