基于C语言的几种排序算法的分析

陈思敏

（武汉科技大学 湖北 武汉 430081）

排序算法（Sorting algorithm）就是以一组记录中的某个或某些关键字的大小为依据，按照一定的排列方式将这组记录有序的排列出来的相应方法。随着科技的不断发展，计算机的应用领域越来越广，但由于计算机硬件的速度和存储空间的有限性，如何提高计算机速度并节省存储空问一直成为软件编制人员努力的方向[1]。排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占用量，进而影响整个软件的性能。

1 排序的概念

在实际中，待排序的序列很少是单个的值，它们通常都是某个记录的一部分，每个记录都有一个关键字key，它是排序的根据。我们通过对这个关键字key进行排序，然后确定每个记录的排列方式，使其成为一个有序的记录。

假设待排序的n个记录为：{R1，R2，……，Rn}

其相应的关键字序列为：

{K1，K2，……，Kn}

排序要做的就是对关键字序列进行重新排列使其满足某一递增或递减关系，从而使得其对应的记录成为一组有序的序列[2]。

2 常用排序算法

2.1 冒泡排序法

冒泡排序（BubbleSort）的基本概念：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序[3]。

按照上述定义，很容易写出冒泡排序的核心代码，以C语言作为示例如下：

冒泡排序是通过n－1趟子排序过程完成的，第i趟子排序从第1个数至第n－i个数，若第i个数比后一个数打，则交换两数。不难知道冒泡排序的效率是低下的，它的时间复杂度为O（n2），不及堆排序或者快速排序的O（n lon2n），但是它的优点也是很明显的，冒泡排序的代码很容易编写，而且具有稳定性[4]。综上所述，只有在少数数据规模比较小的排序中，才用到该种算法。

2.2 快速排序算法

快速排序（QuickSort）算法的是对冒泡排序的一种改进。其基本思想是：先在序列中设置一个基准数，然后通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法的C语言核心代码如下：

在平均情况下该算法的时间复杂度为O（n log2n），在最坏的情况下为O（n2）。实际上，快速排序算法比一些时间复杂度为O（n log2n）的算法要更快一些[5]，因为在大多数架构下其内部循环的实现是高效的。快速排序适合在被排序的序列基本无序的情况下使用。

2.3 插入排序算法

插入排序（InsertionSort）算法的工作原理非常简单，是通过构建一个有序的序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置，然后插入该数据，使得新得到的序列依然有序。

插入排序的C语言核心代码如下：

插入排序在最好的情况下，即待排序数据已经是升序排列了，在这种情况下需要进行比较的次数是（n－1）次，在最坏的情况即待排序数据位降序排列的时候，需要进行比较的次数为n（n－1）/2次，平均来说，排序算法的复杂度为O（n2）。所以插入排序不适合数据量比较大的排序应用。对于需要排序的数据量比较小的时候，插入排序是一个不错的选择。

2.4 归并排序

归并排序（MergeSort）是将两个或两个以上的有序数列合并成一个新的有序数列的方法，即将多个有序的数列合并成一个新的有序数列的方法。在实际处理排序问题时，我们可以将一个待排序数列分成两个或多个待排序的子数列，将这些子序列分别排序之后，再将这些有序的子序列合并为整体的一个有序序列。

归并排序需要进行比较操作的次数介于n log2n/2和n log2n－n+1之间，其算法复杂度为O（n log2n）[6]。归并排序的速度仅次于快速排序，一般针对总体无序，但是各子序列有序的情况下使用。

3 结束语

文中就几种常用的排序方法，从算法的基本思想，到其C语言实现代码，以及算法的时间复杂度和适用情况进行了分析说明。当然，排序算法的种类远不止此几种，没有最好的算法，只有最合适的。在实际应用中，应根据不同的情况，选择合适的排序算法。

[1]潘金贵，顾铁成，曾检，等.现代计算机常用数据结构和算法[M].南京：南京大学出版社，1994.

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

[3]范兴福.C语言程序设计[M].北京：机械工业出版社，2008.

[4]宋美英.基于C语言的冒泡排序算法探讨[J].现代计算机，TANG Yan-qin，LI Qing，LI Wei-wei.The discussion of 2011（23）：37－39.sorting algorithm[J].Modern Computer，2010（12）：64－66.SONG Mei-ying.The discussion of bubble sorting algorithm

[5]唐艳琴，李清，李卫卫.排序算法探讨[J].现代计算机，WANG Li.The comparison and choice of commonly used 2010（12）：64－66.internal sorting algorithm[J].Software Guide，2006（12）：45－46.

[6]王莉.常用内部排序算法的比较与选择[J].软件导刊，based on Clanguage[J].Modern Computer，2011（23）：37－39.2006（1）：45－46.