龙源期刊网 http://www.qikan.com.cn
简单选择排序算法稳定性探究及其改进
作者：钟全 鲁法明 彭延军 来源：《软件导刊》2016年第02期
摘要摘要：稳定性是度量排序算法质量的一个重要指标。简单选择排序是一种常见的排序算法，但其稳定性存在较大争议。结合实例探讨经典简单选择排序算法稳定性，并进行改进，在时间复杂度和空间复杂度不变的前提下，提出一种稳定的简单选择排序算法。 关键词关键词：算法设计；排序算法；选择排序；算法稳定性 DOIDOI：10.11907/rjdk.1511569 中图分类号：TP301.6
文献标识码：A文章编号文章编号：16727800（2016）002006003 0引言
排序算法的稳定性是度量排序算法质量的一个重要指标，指两条关键字相等的记录R、S在排序前与排序后应该保持次序上的先后关系不变。简单选择排序简单易懂，但其稳定性存在争议。大部分常见排序算法在是否满足稳定性方面都有明确的结论。例如，直接插入排序、折半插入排序、冒泡排序、树形选择排序、归并排序、基数排序等都是稳定的排序算法；而希尔排序、快速排序、堆排序等是不稳定的。
文献[1]在选择排序的专题内容中给出的简单选择排序算法是不稳定的，但是进行内部排序方法比较时所有时间复杂度为平方级的简单排序方法都是稳定的。文献[1]指出，选择排序方法本身是一种稳定的排序方法，但经典的简单排序算法却表现出不稳定现象，是由于经典算法采用了交换记录的策略，适当改变该策略就可以得到一个稳定的简单选择排序算法。但是，如何调整经典选择排序的交换策略，文献[1]中并没有给出具体方法。常见程序设计、数据结构以及算法方面的教材中对简单选择排序算法的稳定性问题也都缺乏深入完整的讨论[23]。文献[4]指出经典选择排序算法是不稳定的，同时给出了一个改进的简单选择排序算法以保证稳定性。但文献[5]所提方法提高了经典选择排序算法的空间复杂度。本文在不改变简单选择排序时间复杂度和空间复杂度的前提下，对简单选择排序算法进行改进，提出一种稳定的同等复杂度的简单选择排序算法。
1简单选择排序算法及其性能分析 1.1经典简单排序算法
龙源期刊网 http://www.qikan.com.cn
设待排序记录数组为R[1...n]，对其按照关键字key由小到大进行排序。经典的简单选择排序算法思想为：将排序过程分为n趟，第一趟从R[1]开始，通过n-1次比较，从所有n条记录中选出关键字最小的记录，记为R[IndexOfMin]，交换R[1]和R[IndexOfMin]；第二趟从R[2]开始，通过n-2次比较，从第2条到最后一条共n-1条记录中选出关键字最小的记录，同样记为R[IndexOfMin]，交换R[2]和R[IndexOfMin]；以此类推，上述过程重复n-1趟，完成排序。经典简单选择排序算法C语言伪代码如下： void SelectSort（RcdType R[]， int length）
//R是存放待排序记录的数组，记录从1号元素开始存放，length标识待排序记录个数 //假设由小到大进行排序 {
for（i=1； i {
IndexOfMin=i； for（j=i+1； j
if（R[j].key < R[IndexOfMin].key ） IndexOfMin=j； if（IndexOfMin！=i） {
temp=R[i]；
R[i]=R[IndexOfMin]； R[IndexOfMin]=temp； } } }
龙源期刊网 http://www.qikan.com.cn
1.2简单选择排序算法复杂度分析
简单选择排序过程基本操作分为比较、交换两类。排序过程中，需要进行的记录移动次数较小。当原始记录按照所要求顺序排列时，交换次数为0；当原始记录排序顺序与要求顺序相反时，交换次数最多达到（n-1）次，对应的赋值次数为3（n-1）。就比较次数而言，无论原始序列是何种情况，第1趟排序过程中需要比较n-1次，第2次需比较n-2次；以此类推，第i次需要比较n-i次，最后一趟比较1次。因此，总的比较次数为 n*（n-1）/2。由此可知，简单选择排序算法的总时间复杂度为O（n2）。
就空间复杂度而言，由上述简单选择排序伪代码可见，无论待排序记录有多少条，简单选择排序算法只有i、j、IndexOfMin和temp四个辅助变量。因此，简单选择排序算法的空间复杂度是常数阶的，空间复杂度为O（1）。 1.3稳定性分析
结合实例说明经典简单选择排序算法是不稳定的。假设：将以下序列从小到大排序，3， 3*，3**，2（当中， *用来区分关键字相同的不同记录）。按照经典的简单选择排序，当i=1执行第一次循环时，最小记录为最后一条记录2，它对应的下标IndexOfMin取值为4。此时，将R[1]与R[4]互换得2，3*，3**，3。第二趟和第三趟选择排序不发生任何交换。因此，最后所得有序序列仍然为2，3*，3**，3。可见，两条相等的记录3与3*在排序前后的顺序发生了改变，经典的简单选择排序算法不稳定。 2改进的简单选择排序及其性能分析 2.1改进的简单选择排序算法
为了保证简单选择排序的稳定性，本文方法基本思路如下：找到最小记录R[IndexOfMin]后，不将该元素与无序快首记录（即第i条记录）直接交换，而在第i+1条记录到最小记录之间寻找与R[i]关键字相等的记录。每找到一条就将它与R[i]互换。如此，最多经过n-i次交换，R[i]就成为IndexOfMin之前、离IndexOfMin最近的与无序块首记录关键字相等的记录，而其它记录的相对顺序不发生改变。此时再将R[i]与R[IndexOfMin]交换，则排序算法将保持稳定性。
首先给出改进后的简单选择排序算法的伪代码，结合实例说明其稳定性，并对改进后算法的时间复杂度和空间复杂度进行分析。改进后的简单选择排序算法如下，加粗部分是为了保证算法稳定性而新增的代码。其目的是将无序块首记录后面的、与无序块首记录关键字相等的最后一条记录交换到无序块的首位置，同时保证其它与无序块首记录关键字相等的记录保持次序先后关系上的不变。结合实例说明这一过程。 void SelectSort（RcdType R[]， int length）
龙源期刊网 http://www.qikan.com.cn
//R是存放待排序记录的数组，记录从1号元素开始存放，length标识待排序记录个数 //假设由小到大进行排序 {
for（i=1； i {
IndexOfMin=i； for（j=i+1； j if（R[j].key IndexOfMin=j； if（IndexOfMin！=i） {
for（k=i+1； k {
if（R[k].key==R[i].key） {
temp= R[k]； R[k] = R[i]； R[i] = temp； } }
temp=R[i]；
R[i]=R[IndexOfMin]；
龙源期刊网 http://www.qikan.com.cn
R[IndexOfMin] =temp； } } }
以序列3，3*，3**，2由小到大排序过程为例说明改进算法的执行过程。第一趟排序过程中，IndexOfMin取值为最小记录2的下标4。此后，改进的算法并未将该记录与无序快首记录交换，而是执行如下交换过程：第1次，3*与3交换，得序列3*，3，3**，2；第2次，3*与3**交换，得序列3**，3，3*，2；最后一次，最小记录与无序块首记录交换，即2与3**交换，由此得到记录序列2，3，3*，3**。最后两趟选择排序过程中，记录未发生任何交换，最后所得有序序列为2，3，3*，3**。由此可见，与经典的简单选择排序算法不同，改进后的算法并未改变三条关键字均为3的记录的相对次序。
再如，对记录序列12，15，12*，11，15*，15**，10，15***，9，20，17，15****，111，16，15*****由小到大进行排序。15条记录中记录12出现2次，记录15出现了6次。第一趟排序过程中，IndexOfMin的取值为9，在首记录12与最小记录9交换之前，两者之间的元素12与12*先进行一次交换，从而12*成为了首记录。此后，12*与最小记录9交换得到9，15，12，11，15*，15**，10，15***，12*，20，17，15****，111，16，15*****。第二趟选择排序过程中，最小值为10，IndexOfMin的值为7在15与10交换之前，首先15与15*交换，然后15*与15**交换，最后15**再与10交换。以此类推，最终可得记录序列9，10，11，12，12*，15，15*，15**，15***，15****，15*****，16，17，20，111。由此可见，取值为12或者15的记录在排序前后相对次序未发生改变，满足稳定性的要求。 2.2改进的简单选择排序算法性能分析
改进的算法只在第一层循环（i对应的循环）内加了一个与第二层循环（j对应的循环）并列的循环。从循环结构嵌套的角度来分析，外层循环执行n-1次，内层的两个循环中，j对应的循环至多执行n-1次，新增的循环也至多执行n-1次，由此可知，整个算法中基本操作的执行次数为（n-1）*[（n-1）+（n-1）]，所以改进后的简单选择排序的时间复杂度并未提高。 就具体的基本操作次数而言，改进后的简单选择排序算法需要的基本操作只包括比较和交换两类。当原始记录按照所要求顺序排列时，条件IndexOfMin！=i始终不成立，此时改进后的算法时间性能最优，交换次数为0，比较次数与改进前的简单选择排序算法相同，均为n*（n-1）/2。当原始记录排列顺序恰巧与要求顺序相反时，j所对应的循环下执行的比较次数为 n*（n-1）/2；k所对应的循环下每次都判断条件与否的比较次数最多为（n-2）+ （n-3）+…+1=（n-1）*（n-2）/2；最坏情况下每次比较都要发生交换，再加上k所对应循环外的一次交换，最坏情况下交换次数为（n-1）*（n-2）/2 +（n-1）= n*（n-1）/2。由此可见，相比改进前的简单选择排序算法而言，为了保证排序算法的稳定性，改进后算法比较操作和交换操作的
龙源期刊网 http://www.qikan.com.cn
次数最多均增加（n-1）*（n-2）/2次。结合上节例2，第一趟选择排序过程中，经典的选择排序算法进行了14次比较和1次交换。而改进后算法在进行14次比较之后IndexOfMin值为8，还需进行7次比较，以判断是否存在k使得R[k].key==R[i].key成立，此时共进行了21次比较，中间过程中两个12交换1次、最小元素9与首元素再交换1次，共2次交换，所以，比较次数和交换次数均有所增加，但如前文所述，改进后算法最大时间复杂度与改进前保持不变，都是O（n2）。
此外，就改进后算法的空间复杂度而言，相比改进前算法，无论待排序记录有多少条，新算法只是引入了一个计数器变量k，所以改进后算法的空间复杂度也保持不变，仍然是常数空间复杂度，即空间复杂度依然是O（1）。
最后，根据简单选择排序算法的改进原理，每趟简单选择排序过程中，最小记录只是与其左侧最后一个与无序块首记录相等的记录发生了交换，交换后该记录仍然位于原本在其前面的、与其关键字相等的记录后面；同时，其它记录的相对次序保持不变。所以改进的简单选择排序算法是稳定的。结合2.1节的两个实例也可说明这一过程。 3结语
本文对简单选择排序算法的稳定性问题进行了探讨，在对现有研究进行综述的基础上，结合实例指出经典的简单选择排序算法是不稳定的；对经典的简单选择排序算法进行改进，在保持时间复杂度和空间复杂度不变的前提下，提出一个稳定的简单选择排序算法。 参考文献参考文献：
[1]严蔚敏.数据结构[M].北京：人民邮电出版社，2011. [2]宁正元.数据结构[M] .北京：中国水利水电出版社， 2000.
[3]ROBERT SEDGEWICK，KEVIN WAYNE.算法[M].谢路云，译.北京：人民邮电出版社，2014.
[4]红黑联盟.算法学习——选择排序的稳定性讨论（C++实现）[EB/OL].http：//www.2cto.com/kf/201504/387650.html. 责任编辑（责任编辑：陈福时）
