五种排序的分析与实现方法

摘 要 排序是数据处理应用中最普遍的一种操作。本文举例对冒泡排序法、插入排序法、选择排序法、快速排序法、希尔排序法进行了分析并说明了实现方法。在解决实际问题的过程中，应根据不同的情况，选择合适的排序算法。

【关键词】排序 算法 时间复杂度 程序 元素

排序（Sorting）也称为分类，是将一组含有几个元素的无序的数据排列成有序的序列。排序是数据处理中最普遍应用的一种操作，经过排序的数据可采用优化的算法提高程序执行的效率；增加数据输出的清晰度，便于信息检索；同时经过排序后的数据往往还含一些特殊的意义，为用户提供有价值的信息。排序算法除了在数据处理中具有一定的实际价值外，掌握排序的算法及其依据的原则，可以给学习程序设计人员以启迪，以便在实际应用中能够灵活运用更简洁、更高效的程序设计算法。

1 排序问题

对于程序设计的排序问题可以归纳为：

（1）已知一个具有n个记录的文件F；

（2）记录{R1，R2，…，Rn}都包含许多数据项；

（3）记录{R1，R2，…，Rn}都包含一个关键项Ka；

（4）任意两个记录之间Ra和Rb的次序关系唯一地由两个关键项Ka和Kb的值确定；

（5）利用等于、先于、后于三种次序关系，将F中的记录物理次序重新排列。

2 排序方法

为了便于描述，将文件F设定为含N个整型数据的数组，重点讨论排序算法。含多个数据项的按同样算法实现。

2.1 冒泡排序法（Bubble Sort）

冒泡排序法是一种简单的、基本的排序方法。它的思想是重复地扫描要排序的数列，一次比较两个相邻元素，如果他们的顺序违背规则就把他们进行交换。这样进行若干遍处理，直到全部排好为止。

例如：将{29，23，15，47，05}按从小到大排列

初始关键字： 29 23 15 47 05

第一趟排序后：23 15 29 05 [47]

第二趟排序后：15 23 05 [29 47]

第三趟排序后：15 05 [23 29 47]

第四趟排序后：05 [15 23 29 47]

结 果：05 [15 23 29 47]

从上例可以看出，在该排序中，若需排序的数据为正序，则只进行一次排序即可。若需排序的数据为逆序，则需进行N-1轮排序。需排序的序列为一随机数列，则比较的次数是上述两种情况的平均数值，时间复杂度为0（N2）。

用C程序实现冒泡排序算法的函数：

void Bubble_Sort（int a[]，int N）

{for（int j=0；j

for（int i=0；i

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

{int temp=a[i]；

a[i]=a[i+1]；

a[i+1]=temp；}}

}

2.2 插入排序法（Insert Sort）

插入排序法是一种比较直观的排序方法。它的思想是以第一元素作为有序序列，从第二个元素开始，依次将每一个元素插入到这个有序的序列中，从而使全部数据有序。

例如：将{29，23，15，47，05}按从小到大排列

初始关键字： 29 23 15 47 05

第一趟排序后：[29] 23 15 47 05

第二趟排序后：[23 29] 15 47 05

第三趟排序后：[15 23 29] 47 05

第四趟排序后：[15 23 29 47] 05

结 果：[05 15 23 29 47]

从上例可以看出，在该排序中，若需排序的数据为正序，则比较的次数为N-1次。若需排序的数据为逆序，则最多比较的次数（N+2） （N-1）/2次。需排序的序列为一随机数列，则比较的次数是上述两种情况的平均数值，时间复杂度为0（N2）。

用C程序实现插入排序算法的函数：

void Insert_Sort（int a[]，int N）

{for（int i=1；i

{int temp=a[i]；

int index=i-1；

while（index>=0&&temp

{a[index+1]=a[index]；

index--；}

a[index+1]=temp；}

}

2.3 选择排序法（Selection Sort）

选择排序法是一种程序简洁、流程清晰的排序方法。它是对交换排序法的一个改进算法。它的思想是在对数据的扫描过程中，每轮都从需排序的数据中寻找关键字最小的元素，与第一个元素进行交换位置，在剩余的元素中再找出一个最小的元素与第二个元素进行交换位置，直到全部排好为止。

例如：将{29，23，15，47，05}按从小到大排列

初始关键字： 29 23 15 47 05

第一趟排序后：[05] 23 15 47 29

第二趟排序后：[05 15] 23 47 29

第三趟排序后：[05 15 23] 47 29

第四趟排序后：[05 15 23 29] 47

结 果：[05 15 23 29 47]

从上例可以看出，在该排序的方法中要进行N-1轮选择，每轮选择要比较N-i次。选择排序法比冒泡排序法速度快，时间复杂度为0（N2）。

用C程序实现选择排序算法的函数：

void Selection_Sort（int a[]，int N）

{for（int i=0；i

{int M=i；

for （int j=i+1；j

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

if（M！=i）

{int temp=a[i]；a[i]=a[M]；a[M]=temp；}}

}

2.4 快速排序法（Quick Sort）

快速排序法是对冒泡排序法的改进，是一种高效的排序算法。它的思想是通过一轮排序将待排序的数据分成两个子序列，前一个子序列中的数据均不大于后一个序列中的元素。分别对两个子序列进行排序，直到全部排好为止。

例如：将{29，23，15，47，05}按从小到大排列

初始关键字： 29 23 15 47 05

第一趟排序后：[23 15 05] 29 [47]

第二趟排序后：[15 05] 23 29 47

第三趟排序后：[05] 15 23 29 47

结 果：[05 15 23 29 47]

从上例可以看出，在该排序的方法中，需开辟一个栈的存储空间来实现递归方法进行排序，时间复杂度为0（log2N）。

用C程序实现快速排序算法的函数：

void Quick_Sort（int a[]，int left，int right）

{int L=left；

int R=right；

int x=a[（left+right）/2]；

while（L

{while （a[L]

while（a[R]>x） --R；

if（L>=R） break；

int t=a[L]；a[L]=a[R]； a[R]=t；

++L； --R；}

if（L==R） L++；

if（left）；

if（L

}

2.5 希尔排序法（Shell’s Sort）

希尔排序又称“缩小增量排序”，属于插入排序法，在时间效率上进行了较大的改进。它的思想是将一组待排序的数据分为若干个子序列分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

例如：将{29，23，15，47，05}按从小到大排列

初始关键字： 29 23 15 47 05

取3个子序列：29 05 15 47 23

取2个子序列：15 05 23 47 29

取1个子序列：05 15 23 29 47

结 果：[05 15 23 29 47]

从上例可以看出，在该排序的方法中，虽然对每个子序列采用的是插入排序，每进行一次比较有可能移去整个线性表中多个逆序，改善了整个排序过程的性能。

用C程序实现希尔排序算法的函数：

void Shell_Sort（int*a，int N）

{int k=N/2；

while（k>0）

{for（int i=k；i

{int temp=a[i]；

int j=i-k；

while（j>=0&&temp

{a[j+k]=a[j]；

a[j]=temp；

j=j-k；}}}

}

3 结束语

冒泡排序法和选择排序法程序简单、算法清晰、易于理解，在执行的过程中反复进行数据的判断和交换，效率较低，适用于小规模的排序；插入排序法简单并且高效，在比较的同时挪位，工作量减少很多，每轮比较都必不可少，所以很难进一步优化程序；快速排序法是效率比较高的排序方法，通过递归等复杂的算法实现高效排序，适用于规模较大的排序工作；希尔排序在插入排序的基础上作了较大的改进，每进行一次排序有可能移去表中多个逆序，提高了程序的执行效率。没有最好的算法，只有最合适的。在解决实际问题的过程中，应根据不同的情况，选择合适的排序算法。

参考文献

[1]谭浩强.程序设计与开发技术[M].北京：清华大学出版社，1991.

[2]严蔚敏等.数据结构[M].北京：清华大学出版社，2007.

[3]张乃孝.算法与数据结构[M].北京：高等教育出版社，2008.

[4]胡学刚.数据结构[M].北京：高等教育出版社，2004.

作者简介

1.孙晓妍（1977-），女，辽宁省营口市人，营口职业技术学院讲师，硕士。研究方向为计算机软件教学。

2.吕岩（1970-），女，辽宁省营口市人，营口职业技术学院教授，硕士。研究方向为计算机软件。

作者单位

营口职业技术学院 辽宁省营口市 115000