C语言排序或查找的性能分析

有关排序和查找的一个主要问题就是速度。这个问题经常被人们忽视，因为与程序的其余部分相比，排序或查找所花费的时间几乎可以被忽略。然而，对大多数排序或查找应用来说，你不必一开始就花很多精力去编制一段算法程序，而应该先在现成的算法中选用一种最简单的(见3．1和3．4)，当你发现所用的算法使程序运行很慢时，再换用一种更好的算法(请参见下文中的介绍)。

下面介绍一种判断排序或查找算法的速度的方法。

首先，引入一个算法的复杂度的概念，它指的是在各种情况(最好的、最差的和平均的)下排序或查找需要完成的操作次数，通过它可以比较不同算法的性能。

算法的复杂度与排序或查找所针对的数据集的数据量有关，因此，引入一个基于数据集数据量的表达式来表示算法的复杂度。

最快的算法的复杂度O(1)，它表示算法的操作次数与数据量无关。复杂度O(N)(N表示数据集的数据量)表示算法的操作次数与数据量直接相关。复杂度O(logN)介于上述两者之间，它表示算法的操作次数与数据量的对数有关。复杂度为O(NlogN)(N乘以logN)的算法比复杂度为O(N)的算法要慢，而复杂度为O(N²)的算法更慢。

注意：如果两种算法的复杂度都是O(logN)，那么logN的基数较大的算法的速度要快些，在本章的例子中，logN的基数均为10。

        表3．1  本章所有算法的复杂度
-----------------------------------------------------------------
    算    法    最好情况    平均情况    最坏情况
-----------------------------------------------------------------
  快速排序      O(NlogN)    O(NlogN)    O(N2)
  归并排序      O(N)        O(NlogN)    O(NlogN)
  基数排序      O(N)        O(N)        O(N)   
  线性查找                  O(N)
  折半查找                  O(NlogN)
  哈希查找                  O(N/M)*
  健树查找                  O(1)**
-----------------------------------------------------------------
* M是哈希表项的数目
** 实际上相当于有232个哈希表项的哈希查找

表3. 1列出了本章所有算法的复杂度。对于排序算法，表中给出了最好的、平均的和最差的情况下的复杂度，平均情况是指数据随机排列的情况；排序算法的复杂度视数据的初始排列情况而定，它一般介于最好的和最差的两种情况之间。对于查找算法，表中只给出了平均情况下的复杂度，在最好的情况(即要找的数据恰好在第一次查找的位置)下，查找算法的复杂度显然是O(1)；在最坏的情况(即要找的数据不在数据集中)下，查找算法的复杂度通常与平均情况下的复杂度相同。

需要注意的是，算法的复杂度只表示当N值变大时算法的速度变慢的程度，它并不表示算法应用于给定大小的数据集时的实际速度。算法的实际速度与多种因素有关，包括数据集的数据类型以及所用的编程语言、编译程序和计算机等。换句话说，与复杂度高的算法相比，复杂度低的算法并不具备绝对的优越性。实际上，算法的复杂度的真正意义在于，当N值大于某一数值后，复杂度低的算法就会明显比复杂度高的算法快。

为了说明算法的复杂度和算法的实际执行时间之间的关系，表3．2列出了本章所有例子程序的执行时间。本章所有例子程序均在一台以Linux为操作系统的90MHz奔腾计算机上由GNU C编译程序编译，在其它操作系统中，这些例子程序的执行时间与表3．2所列的时间是成比例的。

                 表3. 2  本章所有例子程序的执行时间
---------------------------------------------------------------------------
    例子程序    算  法      2000      4000      6000      8000      10000
---------------------------------------------------------------------------
    例3．1     qsort()      0．02     0．05     0．07     0．11     0，13
    例3．2a    快速排序     0．02     0．07     0．13     0．18     0．20
    例3．2b    归并排序     0．03     0．08     0．14     0．18     0．26
    例3．2c    基数排序     0．07     0．15     0．23     0．30     0．39
    例3．4     bsearch()    0. 37     0．39     0．39     0．40     0．41
    例3．5     折半查找     0．32     0．34     0．34     0．36     0．36
    例3．6     线性查找     9．67     20．68    28．71    36．31    45. 51
    例3．7     键树查找     0．27     0．28     0．29     0．29     0．30
    例3．8     哈希查找     0．25     0．26     0．28     0．29     0．28
---------------------------------------------------------------------------

注意：

(1)表中所列的时间以秒为单位。

(2)表中所列的时间经过统一处理，只包括排序或查找所花费的时间。

(3)2000等数值表示数据集的数据量。

(4)数据集中的数据是从文件／usr／man／manl／gcc．1(GNUC编译程序中的一个文件)中随机提取的词。

(5)在查找算法中，要查找的数据是从文件／usr／man／manl／g++．1(GNUC++编译程序中的一个文件)中随机提取的词。

(6)函数qsort()和bseareh()分别是C标准库函数中用于快速排序算法和折半查找算法的函数，其余例子程序是专门为本章编写的。

在阅读完以上内容后，你应该能初步体会到如何根据不同的情况来选用一种合适的排序或查找算法。在Donald E．Knuth所著的《The Art Of Computer Programming，Volume 3，Sorting and Searching》一书中，作者对排序和查找算法进行了全面的介绍，在该书中你将读到更多关于复杂度和复杂度理论的内容，并且能见到比本章中所提到的更多的算法。

公用代码：本章中的许多例子程序是可以直接编译运行的。在这些例子程序中，许多代码是相同的， 这些相同的代码将统一在本章的末尾列出。