数组排序算法浅析

张紫琳



数组排序算法浅析

张紫琳

摘要：数组排序是程序设计的一项重要内容，通过运用数组排序的算法，我们能够将很多问题便捷化。在计算机编程中排序是经常遇到的一个问题，所有的数据只有经过一定的排序才会更有意义。在众多算法中，本文对顺序排序、冒泡排序和选择排序这三种基本的排序算法进行详细介绍。

关键词：数组；排序算法；浅析

数组排序就是将数组中的元素按照某种特定的顺序进行排列，如升序或降序。数组排序方法很多，有冒泡排序、顺序排序、选择排序等。本文对一个长度为N的整型数组a，以升序排列为例，对顺序排序、选择排序和冒泡排序的算法进行解析，并在最后加以比较。

一、顺序排序

顺序排序的主要思想是每一轮比较结束后都可以确定某一元素；在一轮的比较过程中，将要确定的位置上的元素与其后所有的元素进行比较；对于一个长为N的数组，需进行N－1轮比较。其第一轮的比较过程如下：

该轮中，a[0]与a[1]～a[n-1]的所有元素进行比较，比较过程中，如果发现哪个元素比a[0]小，则与a[0]进行交换。一轮比较之后，确定a[0]为数组中最小的元素。相同方法，依次确定a[1]、a[2]、a[3]…a[n-2]。

顺序排序主要特点描述

由上表，可以写出其实现代码

for(i=0；i

{ for(j=i+1；j

if(a[i]>a[j])

{t=a[i]；a[i]=a[j]；a[j]=t；} }

可以发现当数组原有的顺序是降序，要实现其升序排序时，每一轮中的交换的次数将会非常多，严重影响排序效率。所以对该方法进行改进：先找出数组中最小值，再与相应位置上的元素进行交换，这就是选择排序。

选择排序的主要过程描述

二、选择排序

选择排序的主要思想是每次从待排序的数据元素中选出最小的一个元素，放在待排序数列的起始位置，直到全部待排序列的数据元素全部排列完毕。

第一轮的比较过程如下：

选择排序的实现代码

for(i=0；i

{k=i；

for(j=i+1；ja[j]) k=j；

if(k!=i){t=a[k]；a[k]=a[i]；a[i]=t；} }

选择排序相较于顺序排序有更高的执行效率，而且思想同样利于理解。

三、冒泡排序

冒泡排序的主要思想是“相邻元素”之间的比较，如果前面的元素大于后面元素就把他们互换。一轮比较之后可以确定最后一个元素为最大，第二轮比较之后可以确定最后一个元素为第二大的元素……依次类推，第N－1轮比较，可以确定倒数第二个元素，这个时候数组的排序完成。冒泡排序的过程如下：

冒泡排序的实现代码

for(i=N-2；i>=0；i--)

{for(j=0；j<=i；j++)

if(a[j]>a[j+1])

{t=a[j]；a[j]=a[j+1]；a[j+1]=t；}}

四、算法浅析

顺序排序算法，思想简单易于理解且适于任何的数组，无论什么情况下都可以使用；但是顺序排序效率较低，可以采用选择排序法进行改进；即使如此选择排序的效率依然受到比较次数的影响，所以对于比较元素比较少的数组，可以采用冒泡排序法。

如果数组中99%的数值已经排序好，即只有很少的元素需要进行排序，可以选择冒泡排序法；如果你所要排序的数据数目相对较少并满足100个以下，你就可以采用选择排序法；如果上述几种情况都不满足，那么就选普遍适用的排序算法即顺序排序法即可。

五、结语

以上所述只是三种常见排序，在众多的排序算法中各有优缺点，每一种算法只有在某一种情况下才表现的最好，我们应当合理的根据实际情况选择算法。

参考文献：

[1]张巍.基于PageRank算法的搜索引擎优化策略研究[D].四川大学，2005.

[2]郭敏杰.基于云计算的海量网络流量数据分析处理及关键算法研究[D].北京邮电大学，2014.

[3]谭浩强.C程序设计.清华大学出版社，2010.

（作者单位：江苏省宿城中等专业学校）