打开文本图片集

摘要：排序算法是计算机科学中最重要的研究问题之一。文章首先介绍了教科书上常见的几种排序算法的思想，然后对各算法的时间复杂度进行分析。本文的重点是比较各算法在不同环境下的时间性能，分析得出在不同环境下适用的排序算法。文章还在算法原来的基础上加以改进，以提高原算法的时间效率。

关键词：排序算法；时间复杂度

1 前言

排序是计算机科学中最重要的研究问题之一 ， 它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。由于它在理论上的重要性 ， 2000年被列为对科学和工程计算研究与实践影响最大的10大问题之 一。其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列[1]。

2 相关算法

2.1插入排序

插入排序的基本思想：每趟将一个待排序的关键字按其值的大小插入到已经安排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止。

由插入排序算法代码，可以选取a[j+1]=a[j];这一句为基本操作。

考虑最坏情况，即整个序列是逆序的，则内层循环条件始终成立，此时对于每一次外层循环，基本操作的执行次数达到最大值，为i次（如当外层循环进行到i=5时，内层循环j取4到0，执行5次）。i取值为1到n-1，由此可得基本操作的执行次数为n（n-1）/2，可以看出时间复杂度为O（n2）。

考虑最好情况，即整个序列已经有序，则内层循环条件始终不成立。此时双层循环变为单层循环，循环内操作皆为常量级，显然时间复杂度为O（n）。

若需要移动的元素较大，则基本操作需要消耗大量时间，因此有必要分析移动元素的次数。分析方式与冒泡排序的分析方式相同，平均情况下要执行n（n-1）/4此移动操作。

2.2冒泡排序

说明：下面的说明中假设数据量大小为n，往后不再赘述。

最简单的排序方法是冒泡排序方法。它是通过一系列的“交换”动作完成的。首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换；然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换。。。。。。一直按这种方式进行下去，最终使整个序列有序。这个过程中，大的关键字像石头一样“沉底”，小的关键字像起泡一样逐渐向上“浮动”，故称冒泡排序。

容易看出该算法总共进行了n（n-1）/2次比较。如果关键字交换过程消耗的时间不多，主要时间消耗在比较上，因而是时间复杂度为O（n²）。

显然冒泡排序在最坏情况下进行n（n-1）/2次交换过程。假设输入序列的分布是等可能的。考虑互逆的两个序列L1=k1，k2，...，kn和L2=kn，kn-1，...，k1。当ki>kj，且ki排在kj前面时，由冒泡算法的思想，排序时定要将kj换到ki前面，即交换一次关键字。对于任意的两个元素ki和kj，不妨设ki>kj，或者在L1中ki排在kj前面，或者在L2中kj排在ki前面，两者必居其一。因此在对L1和L2进行排序是总共需要对这两个元素进行一次交换。n个元素中任意两个元素有Cn2种取法，因此对于这两个互逆序列进行排序，总共需要进行Cn2=n（n-1）/2次交换，平均每个序列需要n（n-1）/4次交换。说明冒泡排序交换关键字的平均次数为n（n-1）/4。

2.3希尔排序

希尔排序又叫缩小增量排序，其本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为1，就是直接插入排序。例如，先以增量5来分割序列，即将下标为0、5、10、15...的关键字分成一组，将下标1、6、11、16...的关键字分成另一组等，然后分别对着些组进行直接插入排序，这就是一趟希尔排序。最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。

希尔排序的时间复杂度和增量选取有关，希尔排序的增量选取规则有很多，这里选取帕佩尔诺夫和斯塔舍维奇（Papernov&Stasevich）提出的：

2k+1、...、65、33、17、9、5、3、1

其中，k为大于等于1的整数，2k+1小于待排序列长度，增量序列末尾的1是额外添加的。此时时间复杂度为O（n1.5）。

2.4选择排序

选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。

选择排序中一个for循环需要执行n-i此比较，因此整个算法需要进行次比较。

每次循环结束都会交换一次关键字，显然选择排序需要进行n-1次交换过程。

2.5快速排序

快速排序通过多次划分操作实现排序。以升序为例，其执行流程可以概括为：每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移到枢轴前边，比枢轴大的移到枢轴后边；当本趟所有子序列都被枢轴按以上规则划分完毕后会得到新的一组更短的子序列，它门成为下一趟划分的初始序列集。

这里，考虑数组的第一个元素作为枢轴元素，输入元素随机。因此A中任一元素作为枢轴元素的概率相等。平均复杂度可由递推方程给出：

可得：T（n）=O（nlogn）

在一般条件下，没有一种基于比较的排序算法能突破这一下界。这一分析证实了快速排序在大多数情况下的良好性能[2]。

2.6堆排序

堆是一种数据结构，可以把对看成一颗完全二叉树，这颗完全二叉树满足：任何一个非叶节点的值都不大于（或不小于）其左右孩子结点的值。

根据堆的定义知道，代表堆的这颗完全二叉树的根节点的值是最大（或最小）的，因此将一个无序序列调整为一个堆，就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后（或最前），这样，有序序列关键字增加1个，无序序列中关键字减少1个，对新的无序序列重复这样的操作，就实现了排序。这就是堆排序的思想。

堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重建堆的过程。

假设高度为k，则倒数第二层右边的结点开始，这一层的结点都要执行子结点比较然后交换（若顺序是对的则不用交换）；倒数第三层则会选择其子结点进行比较和交换，若顺序正确，则不交换，否则要选择一支子树向下调整。

那么总的时间计算为：s=2i-1*（k-i）;其中i表示第几层，2i-1表示该层上有多少个元素，（k-i）表示子树上要比较的次数，如果在最差状况下，即比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；因为叶子层不用交换，所以i从k-1开始到1结束，所以：

S=2k-2*1+2k-3*2+...+2*（k-2）+20*（k-1）

整理得：S=2k-k-1；

又因为k为完全二叉树的深度，根据完全二叉树的性质有2k-1<=n<2k，于是k-1<=logn<k，可以近似地认为k=logn；

综上所述：S=n-logn-1，所以初始化建堆的时间复杂度为O（n）。

循环n-1次，每次都是从根节点往下调整，所以每一次花费的时间为logn，总时间：

logn（n-1）=nlogn-logn；

综上所述，堆排序的时间复杂度为：O（nlogn）。

2.7归并排序

归并排序可以看做一个分而治之的过程：先将整个序列分成两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列归并成一个序列即可。

归并排序的基本操作在函数merge（）中，merge（）的时间复杂度为O（n），时间复杂度为T（n）=O（nlogn）。

3 改进算法

3.1冒泡排序改进

简单的冒泡排序存在这样的缺点：经过几趟排序后，数组的一部分已经有序，每一趟冒泡排序将会在此部分浪费时间。

改进1：每一趟扫描的时候，对那些有序的部分，设置一个标志，如果为true表示发生了交换，否则没有发生交换，表明排序已经完成。

改进2：上述改进存在一定局限性，假设，数组前面300个数据杂乱无章，后700个数据都是排好的，而且比前面300个都要大。这时候只需比较前300个即可。但是上面的改进算法，在对前300个进行排序的时候，每次还都要和后面700个比较。这就显得臃肿了。改进2将标志（flag）变为了具体的位置，这样我们就可以记录末尾的边界。这个边界是排序与不排序的边界。

改进3：在基于冒泡排序的基础上，我们知道，无论是从前向后遍历交换，还是从后向前遍历交换，对程序的逻辑和性能的代价都是不影响的，那么我们就可以让一部分情况下从前向后遍历交换，另一部分情况从后向前遍历交换。

改进4：上述的冒泡排序记录的移动次数都是相同的，并且每次移动记录都是在相邻元素之间移动，假设现在存在三个元素a1，a2，a3，如果我们先比较a1和a2，得到a1<=a2；然后比较a2和a3，得到a2<=a3；则不必比较a1与a3，并且在交换过程中直接交换a1与a3而不用先交换a1与a2再交换a2与a3，此改进可以减少记录的移动次数。

改进效果见结果3-1。

3.2插入排序改进

改进：在插入排序算法的基础上加入折半查找，以减少记录寻找过程中的比较次数。

改进效果见结果3-2。

3.3选择排序改进

改进：之前的算法之中，每跑一趟，只能选出一个最大或者最小的元素，但是归根结底是一个元素。有n个元素就要跑n-1趟。现在，每跑一趟不仅要记录最小元素，还要记录最大元素，这时候需跑N/2趟即可。

改进效果见结果3-3。

3 实验结果与分析

实验结果：

希尔排序在1K个随机数情况下排序时间0.0018秒，在10K个随机数排序0.0714秒，在100K个随机数情况下排序耗时6.8658秒，在200K个随机数下耗时27.4019秒，在1000K随机数下耗时686.301秒，在100K个随机数下正序耗时0.0033秒，倒序13.3648秒；

归并排序在1K个随机数情况下排序时间0.0052秒，在10K个随机数排序0.0194秒，在100K个随机数情况下排序耗时0.1825秒，在200K个随机数下耗时0.366秒，在1000K随机数下耗时1.795秒，在100K个随机数下正序耗时0.0158秒，倒序0.0152秒；

冒泡排序在1K个随机数情况下排序时间0.0042秒，10K个耗时0.2428秒，100K个耗时27.7222秒，200K个耗时111.135秒，1000K个耗时2776.97秒，在100K个随机数下正序耗时0.0003秒，倒序16.8698秒；

直插排序在1K个随机数情况下排序时间0.0013秒，在10K个随机数排序0.0627秒，在100K个随机数情况下排序耗时6.0493秒，在200K个随机数下耗时23.8618秒，在1000K随机数下耗时595.507秒，在100K个随机数下正序耗时0.0004秒，倒序11.948秒；

选择排序在1K个随机数情况下排序时间0.003秒，10K个为0.1263秒，100K个耗时12.2961秒，200K个耗时48.9462秒，1000K个耗时1224.66秒，在100K个随机数下正序耗时12.3169秒，倒序14.1967秒；

堆排序在1K个随机数情况下排序时间0.0003秒，10K个为0.0019秒，100K个耗时0.0212秒，200K个耗时0.0453秒，1000K个耗时0.2542秒，在100K个随机数下正序耗时0.0158秒，倒序0.0152秒；

快速排序在1K个随机数情况下排序时间0.0003秒，10K个为0.0013秒，100K个耗时0.0144秒，200K个耗时0.0325秒，1000K个耗时0.2632秒

由上述的时间性能复杂度分析得出以下总结：

按时间复杂度对排序算法进行分类：

（1）平方阶（O（n2））排序

各类简单排序，如冒泡排序、直插排序、选择排序；

（2）线性对数阶（O（nlogn））排序

快速排序、堆排序、归并排序；

（3）O（n1+§）排序

§是介于0和1之间的常数。希尔排序便是一种；

排序算法的选择

面对不同的环境与要求，选择合适的排序方式是十分重要的。

（1）当n较小，可采用直接插入或选择排序。

当记录规模较小时，采用直接插入排序效率更高，它比选择排序的比较次数更小；当记录规模较大时，因为选择排序中记录的移动次数少于直接插入排序，此时选择排序的效率更高。

（2）若n较大，宜采用时间复杂度为O（nlogn）的排序算法，如快速排序、 堆排序、归并排序。快速排序在数据集有序的情况下会退化为冒泡排序， 堆排序不会出现快速排序可能出现的最坏情况，但它需要建堆的过程， 归并排序同样不会出现最坏情况。

（3）若数据集初始状态基本有序（正序），应选用冒泡或者直接插入排 序。

说明：此处分别对1K与10K数据量的同一个数据集进行测试，算法时间比较采用10K的数据量是由于数据量小的时候比较结果不明显。

结果 3-1冒泡排序改进算法性能比较

冒泡算法在原始版本的情况下，1K随机数记录比较次数499500次，记录移动次数246605，10K随机数耗时为0.2485秒；

冒泡算法在改进版1的情况下，1K随机数记录比较次数499329次，记录移动次数246605，10K随机数耗时为0.2466秒；

冒泡算法在改进版2的情况下，1K随机数记录比较次数497092次，记录移动次数246605，10K随机数耗时为0.2626秒；

冒泡算法在改进版3的情况下，1K随机数记录比较次数499500次，记录移动次数246605，10K随机数耗时为0.2128秒；

冒泡算法在改进版4的情况下，1K随机数记录比较次数1129343次，记录移动次数223043，10K随机数耗时为0.322秒；

结果 3-2插入排序改进算法性能比较

插入排序在原始版本的情况下，1K随机数记录比较次数256143次，记录移动次数255152，10K随机数耗时为0.0669秒；

插入排序在改进版本的情况下，1K随机数记录比较次数243128次，记录移动次数255152，10K随机数耗时为0.0467秒；

结果 3-3选择排序改进算法性能比较

选择排序在原始版本的情况下，1K随机数记录比较次数499500次，记录移动次数1000，10K随机数耗时为0.1315秒；

选择排序在改进版本的情况下，1K随机数记录比较次数250000次，记录移动次数992，10K随机数耗时为0.0785秒；

结语

经过一个多月的努力，我们小组终于完成了本次课程设计以及设计报告的攥写。在本次课程设计中，我们小组对各排序算法进行分析，进行试验设计，再到数据的记录和处理。对算法时间性能的数学表示是本课题的一个难点。小组内各成员不断学习讨论才能得出结果。

通过这次课程设计，我们对各排序算法的认识更加深刻，也对如何进行实验探究有了一定的了解以及掌握度。本次实验还有很多未完善之处，往老师指正。

参考文献

[1]  吴光生， 范德斌. 排序算法研究[J]. 软件导刊， 2007（07）：99-100.

[2]  霍红卫[1]， 许进[2]. 快速排序算法研究[J]. 微电子学与计算机， 2002（6）.