选择排序算法的改进与应用

黄逸

摘 要：选择排序是内部排序算法中的一种，在每一轮目标元素（最大值或最小值）的确定过程中，有关的比较运算结果并没有得到很好的利用。针对上述问题，文章提出了一种改进的选择排序算法，新算法利用临时数组储存比较运算中的有价值信息，在此基础上，提前完成有关的元素交换。实验表明，改进的选择排序算法计算效能有了一定的提升。

关键词：选择排序；内部排序；数组

排序就是将一个数据元素集合或序列重新排列成一个按某项值有序的序列，通常是按照某种规则把数据的顺序重新整理，排序在计算机的信息处理过程中有着极为重要的应用。一般地说，根据待排序元素能否一次性地在内存中完成所有的排序任务，可以把排序算法分为内部排序和外部排序。内部排序无需对外存进行访问，根据不同的原则对内部排序进行分类，大致可分为插入排序、交换排序、选择排序、归并排序和计数排序共五大类[1]。为了改善现有的选择排序算法的计算效能，设计实现了一种改进的选择排序算法，理论分析和实验过程均表明了改进算法的正确性和有效性。

1 改进的选择排序算法的设计与实现

1.1 选择排序算法的效率分析

与冒泡排序一样，选择排序的核心工作也是元素之间的比较和交换。冒泡排序与选择排序的元素比较次数是相同的，但由于选择排序的元素交换次数比冒泡排序少，所以选择排序的执行效率更为高效[2]。

利用C语言描述选择排序算法（从大至小）的程序代码如下：

#include

int main（）

{

int i， j， k， N；

printf（"请输入待排序序列的元素个数＼n"）；

scanf（"%d"， &N;）；

float a[N] ，temp；

for（ i=0； i

for（i=0； i

{ k=i；

for（ j=i+1； j

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

if（ i ！= k）

{ temp=a[i]； a[i]=a[k]； a[k]=temp；}

}

for（ i=0； i

}

如上述程序所示，选择排序算法的工作原理是：第一轮从所有N个数中选出最大的数，即先将a[0]与后面的各个元素a[j]进行比较，凡是遇到比a[0]大的数就记下它的位置j，经过一轮比较（共N-1次）后，最大的数就能被挑选出来，最后可将它与a[0]交换位置。于是，经过第一轮的比较之后，最大数就存放在a[0]中；第二轮从余下的N-1个数中选出最大的数存放在a[1]中，即将a[1]与后面的各个元素a[j]进行比较，凡是遇到比a[1]大的数就记下它的位置j，经过这一轮比较（共N-2次）后，次大的数就能被挑选出来，将它与a[1]进行交换；以此类推，到N-1轮时，可把所剩余两个数中的较大数存放在a[N-2]、而较小数则存放在a[N-1]中。

下面结合某一序列的排序过程，说明选择排序算法所存在的效率问题。如表1所示，待排序序列的元素共有10个，因此，第一轮需进行9次比较，而记录最大数位置的j变量共发生了3次变更，最终的结果是完成了a[0]与a[8]的数据交换操作。根据选择排序算法的工作原理可以得知：除了完成最终的数据交换操作之外，一些有价值的比较信息（如记录最大数位置的变更信息“j=0→j=1”和“j=1→j=4”）却被丢弃掉。

1.2 选择排序算法的改进设计

如前所述，对某一排序任务而言，冒泡排序与选择排序所执行的比较运算次数是相同的，但由于在排序过程中后者对元素的交换次数远小于前者，故选择排序具有更高的效率。受这一思想的启发，可以利用各轮次已掌握的最大数位置变更信息对有关的元素进行交换，以便提前完成各元素的数据交换[3]。仍然以表1的第一轮排序任务为例，首先利用临时数组储存有关最大数发生变更的位置信息（如j={1，4}），在完成a[0]=a[8]old的基础上，依次地对发生位置变更的元素进行相应的元素交换，即a[1]=a[4]old、a[4]=a[1]old。依照上述改进思路对表1的排序任务重新排序，得到如表2所示的结果。

對比表1和表2，不难发现，改进的选择排序算法在第一轮次中便完成了a[1]元素的排序。由于改进的选择排序算法能提前完成各元素的数据交换，于是为提前结束轮次排序提供了可能。

利用C语言描述改进的选择排序算法（从大至小）的程序代码如下：

#include

int main（）

{

int i， j， k， p，q，u，v，N，sum；

printf（"请输入待排序序列的元素个数＼n"）；

scanf（"%d"， &N;）；

float a[N]，b[N] ，temp；

for（ i=0； i

sum=0；/*用于储存元素交换的次数*/

for（i=0； i

{ k=i；

p=0；/*用于储存最大数位置变更的次数*/

for（ j=i+1； j

if（ a[j] < a[k]）

{

b[p]=k；/*储存上一次的最大数位置变更位置*/

p=p+1；/*最大數位置变更的次数增1*/

k=j；

}

if（ i ！= k）；/*记录最大数的位置信息发生变更*/

{

for（q=0；q

{

sum=sum+1；

if （q！=p）

{ u=b[q]；v=b[p-q-1]；

temp=a[u]； a[u]=a[v]； a[v]=temp；

}

else

{temp=a[i]； a[i]=a[k]； a[k]=temp；}

}

}

else

{

if（sum>N）/*提前结束选择排序*/

{

for（ j=i+1； j

{

if（ a[j] < a[j+1]） break；

}

if（j=N） break；

}

}

}

for（ i=0； i

}

2 并行排序的实验及分析

实验的硬件环境是：Intel core i5-6600K四核CPU、DDR4 2133 MHz 16 GB RAM、金士顿SUV400S37/240G固态硬盘；软件环境为：Windows 7专业版64位、Microsoft visual studio 2015 C++；实验中需要进行对比的算法有冒泡排序算法、选择排序算法和改进的选择排序算法。实验过程中，用rand（）函数随机产生一个长度为100的实数序列，然后分别用上述3种算法对该序列中的元素进行排序；实验重复1 000次，取平均计算耗时作为度量各种算法的效能。具体的实验结果如图1所示。

从图1可以发现，冒泡排序算法所需的计算耗时最多、选择排序算法次之，而改进的选择排序算法为最小。事实上，由于改进的选择排序算法充分利用了各轮次的既有比较信息，为提前结束选择排序提供了条件，因而较选择排序算法而言，减少了近22.53%计算耗时的开销。

3 结语

排序算法在信息处理的过程中有着重要的地位，一些经典的排序算法存在结构简单和易于使用的优点，但在执行效率上仍然需要改进。以选择排序算法为例，通过对各轮次的记录最大数位置的变更信息进行处理，设计实现了一种改进的选择排序算法，实验验证了改进算法的正确性和有效性。

[参考文献]

[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2007.

[2]谭浩强.C语言程序设计[M].4版.北京：清华大学出版社，2010.

[3]彭军，向毅.数据结构与算法[M].北京：人民邮电出版社，2013.

Abstract：Selection sort is a kind of internal sorting algorithm. In the process of determining the target element（maximum or minimum）in each round， the results of comparison operation are not well utilized. In order to solve the above problems， an improved selection sorting algorithm is proposed in this paper， which uses a temporary array to store valuable information in the comparison operation. Experimental results show that the computational efficiency of the improved algorithm has been improved.

Key words：selection sort； internal sorting； array