The Efficiency Analysis of Various Sort Programs

ika_酱 2010-03

南中国第一产业大学 信息学院软件工程系

 

 

【摘要】排序算法是计算机算法运算中最重要的，一个好的排序不仅可以使信息查找的效率提高，而且直接影响计算机的工作效率。本文通过对几种常用排序算法的讨论，并予以编程实现，采取对数据的测试与比较，验证算法的优越。

 

【关键词】排序；算法；效率；分析

 

[Abstract]Sorting algorithm is the most important part of computer programing. An excellent sort not only can improve the efficiency of searching information, but also directly influences computer’s working efficiency. In this article, several sorting algorithm commonly used would be discussed.

 

[Key words] sort, algorithm, efficiency, analysis

 

在日常生活中经常需要对所收集到的各种数据信息进行处理, 这些数据处理中经常用的核心运算就是排序。例如图书馆理员将书籍按照编号排序放置在书架上, 方便读者查找; 打开计算机的资源管理器, 可以选择不同类型来排列图标等等。排序已经广泛应用在几乎所有领域。在当今的计算机系统中, 花费在排序上的时间占系统CPU 运行时间的比重很大。

 

1 概述

1.1 排序的基本概念

排序（本文提及的排序均为内部排序）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

排序的确切定义如下：

假设含n个记录的序列为

{R₁，R₂，……，R_n}

其相应的关键字序列为

{K₁，K₂，……，K_n}

需确定1，2，…，n的一种排列p₁，p₂，…，p_n，使其相应的关键字满足如下的非递减（或非递增）关系

K_p1 ≤ K_p2 ≤ …… ≤ K_pn

 

即使n个记录的序列成为一个按关键字有序的序列

{R_p1，R_p2，……，R_pn}

这样一种操作称为排序。

 

内部排序的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境（如记录的初始排列状态等）下使用。如果排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和计数排序等五类；如果按内部排序过程中所需的工作量来区分，则可分为3类：（1）简单的排序方法，其时间复杂度为O（n²）；（2）先进的排序方法，其时间复杂度为O（n log n）；（3）基数排序，其时间复杂度为O（d·n）。

 

1.2 排序基本操作

通常，在排序的过程中需进行下列两种基本操作：

（1）比较两个关键字的大小；

（2）讲记录从一个位置移动至另一个位置。

前一个操作对大多数排序方法来说都是必须的，而后一个操作可以通过改变记录的存储方式来予以避免。

 

1.3 数据元素常用的存储方式

（1）顺序存储，以顺序表作为存储结构；

（2）链式存储，以链表作为存储结构；

（3）索引存储，用顺序的方式存储待排序的记录，但同时建立一个索引表。

 

1.4 排序算法性能评价

（1）时间复杂度；

（2）空间复杂度；

（3）执行时间开销。

要全面分析一个算法，应该考虑它在最好情况下的代价（正序）、最坏情况下的代价（逆序）和平均情况下的代价。

 

 

2 算法描述

2.1 直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。它的基本思想是，将待排序的记录集分成两部分，第一部分已排好序，第二部分未排好序。排序中，每次都是从第二部分中取出一条记录，将其插入到第一部分，并使其保持有序。初始时，任取一条记录作为第一部分，而其他记录作为第二部分。显然，随着排序过程的进行，第一部分不断扩大，第二部分不断缩小。总有一次，第二部分变为空，而第一部分包含所有记录并且是有序的。

从空间来看，直接插入排序只需要一个记录的辅助空间；从时间来看排序的基本操作为：比较两个关键字的大小和移动记录。该算法是稳定的，且时间复杂度为O(n²)。

 

2.2 希尔排序

    希尔排序（Shell’s Sort）又称“缩小增量排序”，它也是一种属插入排序类的方法。它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

        

2.3冒泡排序

冒泡排序（Bubble Sort）是一个最简单的交换排序方法，它和气泡从水中往上冒的情况有些类似。具体做法是：先将第一个记录的键值和第二个记录的键值比较，如a[0]>a[1]，则将二者记录交换，然后比较第二个和第三个记录的键值，以此类推直到第n-1个记录和第n个记录进行比较交换，称为一趟冒泡。一趟冒泡后，键值最大的记录传到了最末尾的位置。重复上述过程，直到有一趟比较之后没有出现记录交换。

 

2.4 快速排序

快速排序（Quick Sort）是冒泡排序的一种改进。快速排序的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两部分记录继续进行排序，以达到整个序列有序。

 

2.5 简单选择排序

设待排序的记录集中记录的下标（位置）为0～(n-1)，则简单选择排序的基本做法是：首先从位置为0～(n-1)的记录中选出键值最小的记录，将它与位置为0的记录交换，然后从位置为1～(n-1)的记录中选出键值最小的记录，将它与位置为1的记录交换……最后从位置为n-2与n-1的记录冲选出最小者，将它与位置为n-2的记录交换。至此，所有的记录都按非递减顺序排列了。

 

2.6 堆排序

    堆排序是一种树形选择排序。其特点是在排序过程中，将元素看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。

 

3实验

3.1实验设计

排序算法的时间开销主要是花费在元素的比较和移动这两方面上，可以通过测定各算法在不同规模数据量（10、30、50、100、500、1000、2500、5000）时正序、逆序和随机数的情况下移动次数和比较次数，分析算法的效率。

 

3.2实验环境

计算机软硬件配置

 

 

3.3实验数据

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4效率分析

4.1图表分析

 

 

 

 

4.1.1正序

分析图4-1和4-2，直接插入排序、冒泡排序、希尔排序和简单选择排序等相对简单容易实现的算法的移动次数均为0，而堆排序和快速排序则仍需要对元素进行移动的操作；在比较次数方面直接插入排序和冒泡排序远远优于其他排序。

整体来说在最好情况下，直接插入排序和冒泡排序实现时的效率是最高的。

 

 

 

 

 

 

4.1.2逆序

分析图4-3和4-4，直接插入排序、冒泡排序和简单选择排序等在正序情况中表现优越的算法此时的表现却是差强人意，特别当数据量比较大的时候，无论是比较次数还是移动次数都远远超过堆排序、希尔排序和快速排序等。

整体来说在最坏情况下，堆排序和快速排序展现出非常高的效率。

 

 

 

 

4.1.3随机数

分析图4-5和4-6，当数据量很大时，冒泡排序和简单选择排序的效率是最差的，堆排序的效率最好，快速排序次之。

整体来说一般情况下，堆排序和快速排序的效率都很高。

 

 

4.2算法时间复杂度

衡量一个算法的时间度量是用时间复杂度来衡量，表示为：

T ( n) = O( f ( n) )

 

“O”的形式定义为:若f (n) 是正整数n 的一个函数,则xn = O(f (n) ) 表示存在一个正的常数M ,使得当n ≥n0 时都满足xn ≤M f (n) 。

    它表示算法执行时间是问题规模n 的某个函数，执行时间的增长率和f ( n) 的增长率相同. 下表列出了常用排序算法在理论层次上的比较。

 

 

 

由上表平均时间复杂度可知，希尔排序、快速排序和堆排序的速度较快。一般情况下，从算法结构的复杂性看，速度慢的排序算法结构都比较简单、直接。希尔排序、快速排序和堆排序均可视为对某一种排序方法的改进，算法结构一般都较为复杂。进一步分析，有：

 

 

①   数据规模n较小时，则采用简单的排序方法比较合适，如直接插入排序或简单选择排序。

②   当记录的初始状态已基本有序时，可用简单的排序方法，入直接插入排序或冒泡排序。

③   当数据规模n较大时，应选用速度快的算法。快速排序被认为是目前基于比较的排序方法中较好的方法。当待排记录是随机分布时，快速排序的平均时间最短，但可能出现最坏情况。

④   堆排序不会出现像快速排序那样的最坏情况，且其所需的辅助空间也较少。

 

 

5 小结

排序算法的性能分析和选择是一个复杂而又实际的问题，由上述分析可知，各种排序算法各有优缺点，很难举出一个在各方面都是最优的一个算法。本文只是对六种常见的排序算法进行简单的初级的讨论分析，待排序的数据的规模和数据初始特性是十分重要的选取合适算法的标准，在实际应用中应根据经验和实际情况合理选择算法，或者将一些算法例如快速排序和插入排序等结合起来综合运用。

 

 

 

 

 

6 参考文献

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

[2]齐德昱．数据结构与算法．北京：清华大学出版社，2003

[3]张乃孝．算法与数据结构（第2版）．北京：高等教育出版社，2009

[4]周慧琴．常用内排序算法的分析与比较．忻州师范学院专科部，2009

[5]方斌，邓丽霞．六种排序算法时间性能的实验分析．郧阳师范高等专科学校学报，2005

[6]白红义．常用内排序算法的分析与比较．宁夏交通学校，2008