一种快速排序算法的实现及其应用✴

黎佩南（中国西南电子技术研究所，成都610036）

一种快速排序算法的实现及其应用✴

黎佩南
（中国西南电子技术研究所，成都610036）

介绍了一种快速的排序方法——堆排序。以一个简单的实例结合完全二叉树说明了该算法的原理，给出了利用C语言实现该算法的代码，从时间复杂度和辅助存储空间的角度分析了与其他排序算法相比较的优劣。实验表明，在对大量数据进行排序时，堆排序算法效率较高。

排序算法；快速排序；堆排序；时间复杂度；辅助存储空间

1 引言

排序（Sorting）是将一个数据元素的任意序列，按关键字的升序或降序重新排列成一个有序序列的过程［1］。有序序列为记录的查找、插入和删除提供了方便，可以有效提高效率。在现代工程中，排序被广泛应用于数据库管理、网络路由分配、信号处理、生物工程、人工智能、计算机图形、计算机辅助设计、模式识别及统计学等各个领域。在计算机出现之前，排序是一项非常复杂而繁琐的工作，完全依赖于人工，人们需要对每一份数据进行逐一对比，要求参与者精神高度集中，而大量数据的排序往往会耗费相当长的时间。在计算机出现后，由于其响应快速、计算精密，排序已经实现了完全由计算机自动完成。本文介绍了一种快速的排序方法——堆排序（Heap

Sort），并利用C语言实现了该算法的代码。该算法的特点是速度较快，占用的辅助空间小，尤其适用于大数据量记录的排序。

2 排序算法简介

排序的方法有很多，按排序时访问的介质，排序可分为内部排序（整个排序过程不需要访问外部存储器）和外部排序（参加排序的记录数量很大，排序过程不可能在内存中完成，需访问外部存储器）。随着计算机硬件技术的飞速发展，内存空间不断扩展，外部排序的应用已大大减少。内部排序按所用策略不同，分为插入排序、选择排序、交换排序、归并排序和基数排序等［2］。

2.1 插入排序

常用的插入排序算法有直接插入排序和希尔排序。直接插入排序是最简单的排序方法，基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

希尔排序先将整个待排记录序列分割为若干子序列分别进行直接插入排序，待正序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

2.2 交换排序

常用的交换排序算法有起泡排序和快速排序。

起泡排序又称冒泡排序，也是一种简单的排序算法，在排序过程中，关键字较小的记录随着不断交换逐渐前移。

快速排序是对起泡排序的一种改进，通过一次排序将记录分割成独立的两部分，其中一部分的关键字均比另一部分小，再分别对这两部分记录进行排序，达到整个序列有序。

2.3 选择排序

常用的选择排序算法有直接选择排序和堆排序。

直接选择排序是通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录，并与第i（1≤i≤n）个记录交换。

堆排序是一种基于完全二叉树对叶子节点进行不断筛选的排序过程。

2.4 归并排序

将两个或两个以上的有序表组成一个新的有序表，先将n个数据看成n个长度为1的表，将相邻的表成对归并，得到长度为2的有序表，再将相邻表归并为长度为4的有序表，依次做下去，直到所有数据均合并到一个长度为n的有序表中［3］。

2.5 基数排序

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的算法［2］。

插入排序、交换排序、选择排序及归并排序适用于单关键字的序列排序，基数排序则适用于多关键字的序列排序。

3 堆排序算法

堆排序算法是一种基于完全二叉树和堆的排序算法。下面首先介绍完全二叉树和堆的定义。

完全二叉树是一种具有下列性质的二叉树：若已知某个结点编号为i，则有：若i=1，该结点为根结点；若结点i有左孩子，则其编号为2×i；若结点i有右孩子，则其编号为2×i+1。且N个结点的编号从1到N是连续的［4］。

堆的定义如下：n个元素的序列｛k1，k2，k3，…，kn｝，当且仅当满足下列关系时，称之为堆［4］。

若将和此序列对应的一维数组看作是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端节点的值均不大于（或不小于）其左、右子节点。因此，若序列｛k1，k2，k3，…，kn｝是堆，则堆顶元素（即该完全二叉树的根）必为该序列中n个元素的最小值或最大值。图1和图2分别是两个完全二叉树，对应的一维数组分别为｛96，83，27，38，11，09｝和｛12，

36，24，85，47，30，53，91｝。

在输出堆顶的最大（或最小）值之后，剩余的n -1个元素的序列重新建成一个堆，则得到n个元素中的次大（或次小）值，如此反复执行，便能得到一个有序序列，这个过程就是堆排序。因此，实现堆排序需要解决两个问题：一是如何由一个无序序列建成一个堆；二是如何在输出堆顶元素后，调整剩余元素成为一个新堆。下面分别描述两个过程。由于建堆的过程需要一直用到过程2，因此首先介绍过程2。

3.1 推出堆顶及筛选

下面以图2所示堆为例来说明这一过程。

将堆顶的12推出，以堆底的91代替，如图3（a）所示，此时根节点的左、右子树均为堆，因此只需自上向下调整即可。此时比较堆顶元素及其左、右子树的根节点，由于右子树根节点比左子树根节点及堆顶元素都小，因此将右根子树节点与堆顶元素交换，剩余的调整过程在右子树中进行，如图3（b）所示。可以看见，在经过多次调整之后，剩余的数又形成了一个新的堆，如图3（c）所示。堆顶至叶子的调整过程称之为“筛选”。重复执行“推出堆顶数据→筛选”的过程，就可以得到一个有序的队列。

3.2 建堆

从一个无序序列建堆的过程实际上就是一个反复“筛选”的过程。若将次序列看做一个完全二叉树，则最后一个非终端节点是第n／2个元素，因此“筛选”只需从第n／2个元素开始。下面将图2中的树稍作修改，以此为例说明建一个升序堆的过程。初始序列树如图4所示。

筛选从第4个元素，即91开始，91大于其子节点24，将两者交换，结果如图5所示；再筛选第三个元素53，结果如图6所示；再筛选第二个元素85，结果如图7所示；再筛选根节点36，结果如图8和9所示。

经过以上变换，一个符合条件的初始堆就建成了，堆顶元素12为堆中最小值，推出堆顶12后，再调整剩余的元素，就可以形成一个有序的序列。

通过以上分析可以看出，堆排序算法运行时间主要耗费在建初始堆和反复“筛选”的过程中。对深度为k的堆，“筛选”算法中进行的关键字比较次数最多为2（k-1）次，n个节点的完全二叉树深度为lg n+1，调整新建堆时总共比较的总次数最多为

2（lg（n-1）+lg（n-2）+lg（n-3）+…+lg2）＜2 n lg n

由此可见，在最坏的情况下，其时间复杂度为n lg n［5］。同时，该算法在整个排序过程中，只需要一个额外的存储控件，因此在进行大数据量元素的排序时，堆排序算法是一个较好的选择，但是堆排序算法相对来说较为复杂，记录数较少时不值得提倡。

4 代码实现

下面给出利用C++Builder实现堆排序的代码。

4.1 筛选

代码如下：

void Sift（int iRootIndex，int iNodeCount）

／／iRootIndex为当前根节点在序列中的位置，iNodeCount为剩余节点数量

｛

int iLeftLeave，iRightLeave；／／根节点的左右子节点

bool bFinish=false；／／排序完成标志

int iRoot；／／根节点值

int iTemp；／／临时变量，保存原始根节点

／／获取当前根节点值

iTemp=DataList［iRootIndex］；

iRoot=DataList［iRootIndex］；

／／获取根节点的子节点

iLeftLeave=iRootIndex；

iRightLeave=2*iLeftLeave；

／／重新排列堆

while（iRightLeave＜=iNodeCount＆＆！bFinish）

｛

／／语句1：若存在右子树，且右子树根的值较小，则沿右子树筛选，否则沿左子树筛选

if（iRightLeave＜iNodeCount＆＆DataList［iRightLeave］＞DataList［iRightLeave+1］）

iRightLeave=iRightLeave+1；

／／语句2：若根节点的值较小，筛选完成，否则继续筛选

if（iTemp＜=DataList［iRightLeave］）

bFinish=true；

else

｛

iLeftLeave=iRightLeave；

iRightLeave=2*iLeftLeave；

｝

｝

／／根节点插入恰当位置

DataList［iLeftLeave］=iRoot；

｝

4.2 堆排序

代码如下：

void HeapSortAsdc（void）

｛

／／对DataList中的数据从第n／2个记录开始进行筛选建堆

for（i=（（i＞iCount-1）／2）；i＞=0；i--）

Sift（i，iCount-1）；

for（i=iCount-1；i＞=1；i--）

｛

／／将堆顶数据与最后一个数据互换，使堆顶数据被推出

Exchange（DataList，0，i）；

／／调整剩余的数据，使之成为一个堆

Sift（0，i-1）；

｝

｝

说明：

（1）DataList是一个整型数组，事先已装载了待排序的数据，iCount为DataList中元素的个数；

（2）Exchange（i，j）用于实现数组相应位置数据的交换；

（3）上述算法是针对整数进行排序，若要实现对其他类型，如浮点数、字符的排序，只需将DataList改为相应的数组；

（4）该算法由标准C语言实现，可以用于DSP、MATLAB及VxWorks嵌入式操作系统等；

（5）由于每次推出的堆顶元素都被排在序列的首部，因此上述代码实现的是降序排序，只需将语句1和语句2中相应的大于或小于比较符进行相应修改，即可实现升序排序；

（6）以上代码是将待排序数据存放在数组中，在排序过程中需要进行记录的移动，适用于记录较小（即每个记录占用的空间较小）的情况，若记录很大，移动记录的时间消耗也较大，这时可利用链表和指针来存储数据，以修改指针代替移动记录，以提高效率。

5 算法比较与分析

排序算法多种多样，在实际应用中选择哪种算法，主要是参考其时间复杂度（Time Complexity）和空间复杂度（Space Complexity）。时间复杂度是指完成一个算法所需要的时间的量度，空间复杂度是对一个算法在运行过程中临时占用存储空间的大小的量度，这两者都是衡量一个算法优劣的重要参数。下面用表1来简单比较各种排序方法。

由表1可以看出，因其本身的时间复杂度和占用的辅助空间，每种排序算法各有其优缺点及适应性。为了更直观地说明堆排序在时间复杂度上的优势，在一台主频2.8 GHz、内存512 MB的计算机上，利用C实现了直接插入排序、希尔排序、起泡排序和堆排序等算法，并对不同数量的记录进行了排序，实验结果如表2所示。

由表2可以看出，简单的算法，随着记录数的增加，时间的消耗将会大大增加，此类算法只适用于记录数较少的序列。而堆排序算法虽然复杂度高，在对记录较少的序列排序时，未免显得大材小用，但是在对大量数据进行排序时，优势非常明显。例如在工程中常常使用的数据库检索排序，当记录数达到一定的数量级，如万条时，排序时间往往成为瓶颈，过长的等待时间使用户难以忍受，而堆排序算法的高效性很好地解决了这个问题。在实际应用中，还可以将堆排序与其他算法结合使用，以使时间和空间的效率达到最优。

［1］Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，et al.算法导论［M］.潘金贵，顾铁成，李成法，等，译.北京：机械工业出版社，2006. Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，et al.Intruduction to Algorithms［M］.Translated by PAN Jingui，GU Tie-cheng，LI Cheng-fa，et al.Beijing：China Machine Press，2006.（in Chinese）

［2］严蔚敏，李冬梅，吴伟民.数据结构［M］.北京：人民邮电出版社，2011. YAN Wei-min，LI Dong-mei，WU Wei-min.Data Structure［M］.Beijing：People′s Posts and Telecommunications Press，2011.（in Chinese）

［3］王莉.常用内部算法的比较与选择［J］.软件导刊，2006（1）：45-46. WANG Li.Comparison and Selection of Common Internal Algorithm［J］.Software Guide，2006（1）：45-46.（in Chinese）

［4］李爱华，刘晓红，张衍杰.基于完全二叉树概念的算法设计与分析［J］.山东理工大学学报（自然科学版），2006，20（3）：56-58. LIAi-hua，LIU Xiao-hong，ZHANG Yan-jie.Based on completely two forks trees conceptalgorithm design and analysis［J］.Journal of Shandong University of Technology：Science and Technology，2006，20（3）：56-58.（in Chinese）

［5］辛运帏，刘王景，陈有祺.数据结构与算法［M］.北京：高等教育出版社，2006. XIN Yun-wei，LIU Jing，CHEN You-qi.Data Structure and Algorithms［M］.Beijing：Higer Education Press，2006.（in Chinese）

Realization and Application of a Quick Sort Algorithm

LI Pei-nan
（Southwest China Institute of Electronic Technology，Chengdu 610036，China）

A quick sortmethod called heap sort is introduced.The principle of this method is discussed by using a simple example together with completecinary tree.The codes for the method realized by C are provided.The advantages an disadvantages are analysed in comparison with other sort methods in term of time frame and assist memory space.Experiment indicates when sorting mass data，the heap sort has better efficiency.

sort algorithm；quick sort；heap sort；time complexity；assist memory space

the B.S.degree in 1994.She is now an engineer.Her research direction is satellite-borne product design.

1001-893X（2012）02-0225-05

2011-07-29；

2011-12-27

TP31

A

10.3969／j.issn.1001-893x.2012.02.022

黎佩南（1972—），女，重庆人，1994年获学士学位，现为工程师，主要研究方向星载产品设计。

Email：minicat234＠sohu.com

LI Pei-nan was born in Chongqing，in 1972.She