选择排序算法的分析与改进

熊英++吴尚宇

摘 要 排序算法在商业数据处理及现代科学计算中扮演着十分重要的角色，其中选择排序是其中最简单的算法之一。传统的选择排序是进行n次选择，每次选择均从待排序部分选取最小（大）的元素与待排序部分的第一个元素交换。相比而言，改进后的算法尽可能减少了比较的次数，提高算法的效率，并降低了最好情况下的时间复杂度。

【关键词】选择排序 双向排序 效率 时间复杂度

1 传统的选择排序算法

传统的选择排序算法有两个很好的性质，即：

（1）运行时间对原始输入数据不敏感：每一次选择都是独立的，不受前一次选择的影响也不对后一次的选择提供相关信息。

（2）数据的交换次数是所有排序算法中最小的：传统算法的交换次数是线性的。

1.1 传统选择排序思路

以从小到大排序为例：

第一步：在1～n个数中找到最小数，与第1个数交换，前1个数已排好；

……

第k步：在k～n个数中找到最小数，与第k个数交换，前k个数已排好；

第n-1步：在n-1到n个数中找到最小数，然后与第n-1个数交换，排序结束。

1.2 算法分析

时间复杂度：通过对上面代码的分析，研究排序的轨迹，可以知道对每一个i从0到n-1，都有1次交换和n-1-i次比较，所以总共有n次交换和（n-1）+（n-2）+（n-3）+…+2+1+0=n（n-1）/2～n2/2次比较，因此时间复杂度为O（n2）。

2 改进的选择排序算法

针对传统排序算法中的每一次选择，可以发现每一次选择只能确定一个优先级最高的元素的位置，而实际上在一次选择的循环中，不仅仅可以确定优先级最高的元素位置，同时也可以确定优先级最低的元素位置。

由此可得出改进后的选择排序算法：数组的中间部分为待排序部分，两边均为已排序部分，每一次选择从待排序部分选择优先级最高和最低的两个元素的位置，分别将该两个元素与待排序部分的首部和尾部进行交换（交换的顺序需要特别考虑），由此即实现了双向排序。这样与传统的选择排序相比，比较次数减少了近1/2。

2.1 算法思路

第一步：从1～n个数中同时找到最小数和最大数，将它们分别与第1个数和第n个数交换；

……

第k步：从k～n-k+1个数中同时找到最小数和最大数，将它们分别与第k个数和第n-k+1个数交换；

第n/2步：从n/2～（n/2）+1个数中同时找到最小数和最大数，将它们分别与第n/2个数和第（n/2）+1个数交换，排序结束。

例如对实验数据[10 3 4 7 1 2]的排序过程如下：

第一步：1[3472]10：6个数中1最小，10最大，分别与第1个数和第6个数交换。

第二步：1 2 [4 3] 7 10：4个数中2最小，7最大，分别与第2个数和第5个数交换。

第三步：1 2 3 4 7 10：2个数中3最小，4最大，分别与第3个数和第4个数交换。

2.2 算法分析

时间复杂度：从改进后的算法中，仍研究排序的轨迹，可知交换次数没有改变，仍为n，但比较的次数减少了一半，为n（n-1）/4，提高了效率，但是由于在同一个数量级，时间复杂度仍为O（n2）。

3 算法之再改进

在算法2的基础上再对算法进行改进：由传统的选择排序算法的两个性质可得，可以对算法进行改进，增强其对原始输入数据敏感性。在最优的情况下，即输入数据有序，选择排序仍需要进行相同数量级的比较，这大大降低了选择排序的效率。再改进的选择排序算法结合冒泡排序的思路，在每一次选择交换之前，对待排序部分进行预判：若待排序部分已有序，则结束排序。

预判操作为：比较前一个元素和后一个元素的优先级，如果待排序部分中前一个元素的优先级均高（低）于后一个元素，则认为待排序部分有序。由此分析可知，改进后的选择排序最优时间复杂度为O（n）。

例如对实验数据[9 3 5 6 8 1]进行排序的过程：

第一步：1 [3 5 6 8] 9：预判待排序部分为乱序，进行选择排序。6个数中1最小，9最大，分别与第1个数和第6个数交换。

第二步：预判待排序部分为有序，排序结束。

由此可见，再改进的选择排序算法对原始输入数据的敏感性已得到大幅提升。

3.1 算法分析

时间复杂度：该算法与改进后的算法相比，最好情况下的时间复杂度为O（n），最坏情况下为O（n2）。

4 代码实现

本文中就不再實现传统的选择排序算法代码，以下为再改进后的选择排序算法代码实现：

voidNewSelectSort（）{

for（inti=0；i

boolisordered=true；

for（int j=i；j<=n-i-1；j++）{//预判

if（a[j]>a[j+1]）{

isordered=false；

break；

}

}

if（isordered）break；

int min=i，max=n-i–1；

if（a[min]>a[max]）swap（a[min]，a[max]）；

for（int j=i；j<=n-i-1；j++）//双向选择排序

if（a[min]>a[j]）min=j；

else if（a[max]

swap（a[i]，a[min]）；

swap（a[n–i–1]，a[max]）；

}

}

5 三种选择排序的比较

对三种选择排序的时间复杂度进行比较：

（1）传统选择排序：最好情况时间复杂度：O（n2），最坏情况时间复杂度：O（n2）。

（2）改进选择排序：最好情况时间复杂度：O（n2），最坏情况时间复杂度：O（n2）。

（3）再改进选择排序：最好情况时间复杂度：O（n2），最坏情况时间复杂度：O（n）。

6 结语

文章采用双向排序的方法对传统的选择排序算法进行了效率上的提高，并且结合冒泡排序的思路，对选择排序的最好的情况下的时间复杂度进行了优化，均c/c++语言实现了上述算法，通过大量的实验数据证明上述算法的正确性和可行性。

参考文献

[1]Robert，S，& Kevin，W（2013）. Algorithms[M].北京：人民邮电出版社出版发行，2010.

[2]严蔚敏，陈文博.数据结构及应用算法教程[M].北京：清华大学出版社，2011.

[3]何洪英.双向选择排序算法的实现及性能研究[J].成功（教育），2007.

作者单位

华中师范大学计算机学院 湖北省武汉市 430079