【专题名称】

算法分析与设计专题（程序员）

【主要内容概述】

本讲主要介绍作为一个程序设计人员应该掌握的算法分析与设计的基础知识，有助于专业软件开发人员了解程序的算法结构、

【专题知识重点】

算法特性和基本概念、算法评价、常用的算法分析和算法之间的比较

【专题授课内容】

1）算法特性和基本概念

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

Ø 确切性： 算法的每一步骤必须有确切的定义；

Ø 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；

Ø 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

Ø 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

Ø 有穷性： 一个算法必须保证执行有限步之后结束；

Note：

    ①如果只满足前四条的只能叫做计算过程，算法必须是有穷内终止运行。

    ②由于研究算法的目的最终是为了有效地求出问题的解，那就需要将算法投入到计算机上运行，因此对算法的讨论不能只研究到它能在有穷步内终止就结束，而应对有穷 性作进一步的研究，即对算法的效率作出分析。

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。

计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。

不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

采用时间的渐近表示，从计算时间上可以把算法分成两类。凡可以用多项式来对其计算时间限界的算法，称为多项式时间算法；而计算时间用指数函数限界的算法称为指数时间算法。其中有六种多项式时间算法最为常见，其关系为：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)；指数时间算法一般有：O(2n)<O(n!)<O(nn)。

2）算法评价

对于解决同一个问题，往往能够编写出许多不同的算法。例如，对于数据的排序问题，已经学习过的有：枚举排序、冒泡排序、插入排序、快速排序、希尔排序等多种方法，对于这些排序算法，他们各有优缺点，其算法如何有待用户的评价。因此，对问题求解的算法优劣的评定称为“算法评价”。算法评价的目的，在于从解决同一问题的不同算法中选择出较为合适的一种算法，或者是对原有的算法进行改造、加工，使其算法更优、更好。

一般对算法进行评价主要有四个方面：

①算法的正确性：正确性是设计和评价一个算法的首要条件，如果一个算法不正确，其它方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的运行时间内得到正确的结果。通过对数据输入的所有可能情况的分析和上机调试，以证明算法是否正确。

②算法的简单性：算法简单有利于阅读，也使得证明算法正确性比较容易，同时有利于程序的编写、修改和调试。但是算法简单往往并不是最有效。因此，对于问题的求解，我们往往更注意有效性。有效性比简单性更重要。

③算法的运行时间：时间复杂性，算法的运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行简单操作（如赋值操作，比较操作等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性。它是一个算法运行时间的相对量度，一般用数量级的形式给出。度量一个程序的执行时间通常有两种方法：

一种是事后统计的方法。因为很多计算机内部都有计时功能,有的甚至可精确到毫秒级,不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优劣。因此人们常常采用另一种事前分析估算的方法。

事前分析估算的方法。一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

（1）     依据的算法选用何种策略。

（2）     问题的规模。例如求100以内还是1000以内的素数。

（3）     书写程序的语言。对于同一个算法,实现语言的级别越高,执行效率就越低。

（4）     编译程序所产生的机器代码的质量。

（5）     机器执行指令的速度。

显然,同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行时,效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法“运行工作量”的大小,只依赖于问题的规模（通常用整数量n表示）,或者说,它是问题规模的函数。

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的,则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法,通常的做法是,从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作,以该基本操作重复执行的次数作为算法的时间度量。

一般情况下,对一个问题(或一类算法)只需选择一种基本操作来讨论算法的时间复杂度即可,有时也需要同时考虑几种基本操作,甚至可以对不同的操作赋以不同权值,以反映执行不同操作所需的相对时间,这种做法便于综合比较解决同一问题的两种完全不同的算法。

由于算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以计算基本操作执行次数(或语句频度)的情况下,只需求出它关于n的增长率或阶即可。

④算法所占用的存储空间：空间复杂性，算法在运行过程中临时占用的存储空间的大小被定义为算法的空间复杂性。空间复杂性包括程序中的变量、过程或函数中的局部变量等所占用的存储空间以及系统为了实现递归所使用的堆栈两部分。算法的空间复杂性一般也以数量级的形式给出。

类似于算法的时间复杂度,以空间复杂度作为算法所需存储空间的量度,记作

S(n)=O(f(n))

其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间,否则应同时考虑输入本身所需空间(和输入数据的表示形式有关)。若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。又如果所占空间量依赖于特定的输入,则除特别指明外,均按最坏情况来分析,即以所占空间可能达到的最大值作为其空间复杂度。

算法优化的几种常用方法：

（1）空间换时间算法中的时间和空间往往是矛盾的，时间复杂性和空间复杂性在一定条件下也是可以相互转化的,有时候为了提高程序运行的速度,在算法的空间要求不苛刻的前提下,设计算法时可考虑充分利用有限的剩余空间来存储程序中反复要计算的数据,这就是“用空间换时间”策略,是优化程序的一种常用方法。相应的,在空间要求十分苛刻时,程序所能支配的自由空间不够用时,也可以以牺牲时间为代价来换取空间,由于当今计算机硬件技术发展很快,程序所能支配的自由空间一般比较充分,这一方法在程序设计中不常用到。

（2）尽可能利用前面已有的结论：比如递推法、构造法和动态规划就是这一策略的典型应用，利用以前计算的结果在后面的计算中不需要重复；

（3）寻找问题的本质特征，以减少重复操作：算法的复杂度分析不仅可以对算法的好坏作出客观的评估，同时对算法设计本身也有着指导性作用，因为在解决实际问题时，算法设计者在判断所想出的算法是否可行时，通过对算法作事先评估能够大致得知这个算法的优劣，进而作出决定是否采纳该算法。这样就能避免把大量的精力投入到低效算法的实现中去，特别是现在举行的各级信息学奥林匹克竞赛对程序的运行时间都有着相当严格的限制，掌握好算法复杂度的大致评估方法就显得犹为重要。

3）常用算法分析

1．递归的定义：一个过程(或函数)直接或间接调用自己本身，这种过程(或函数)叫递归过程(或函数)，有直接调用和间接调用两种。

   设计递归算法，主要有两步

　　（1）确定递归公式；

　　（2）确定边界(终了)条件；

　　要注意学会把具体问题分解为几个子问题，如果你分解的这些子问题的形式和算法与原问题相似，那么，你的递归算法就能很快完成。

能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态，这种用自已来定义自己的方法，称为递归定义。

例如：定义函数f(n)为：

        f(n)=n*f(n－1) (n>0)

f(n)= 1(n=0)

 则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。

由上例我们可看出，递归定义有两个要素：

（1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。

如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。

（2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。

如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。

递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简化精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步简化而其结果仍维持原问题的关系, 则采用递归算法编程比较合适.

递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程D, 而D又调用P.

递归算法适用的一般场合为:

（1）数据的定义形式按递归定义.

   如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.

    对应的递归程序为:

         Int Function fib(int n)

         {

            if n = 0 then fib = 1     { 递归边界 }

                     else if n = 1 then fib = 2

                                   else fib= fib(n-2) + fib(n-1)   { 递归 }

        }

       这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.

（2） 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.

（3） 问题解法按递归算法实现. 例如回溯法等.

从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作" 回溯法 ".

2．排序算法：

排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。这里的数据元素是指记录，即若干个数据项，关键字就是选中的数据元素。

排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类：

内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；

外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。

排序问题的复杂性：对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。

为了对有n个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n个元素的信息，因此排序问题的计算复杂性下界为Ω(n)。

如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就是各个元素的具体的值，我们仅能通过比较来确定输入序列<a1,a2,..,an>的元素间次序。即给定两个元素ai和aj，通过测试ai<aj ，ai≤aj ,ai=aj ,ai≥aj ,ai>aj 中的哪一个成立来确定ai和aj间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。

3．各种排序算法比较

  一、插入排序(Insertion Sort)

1） 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2） 排序过程：

【示例】：

[初始关键字] [49] 38 65 97 76 13 27 49

    J=2(38) [38 49] 65 97 76 13 27 49

    J=3(65) [38 49 65] 97 76 13 27 49

    J=4(97) [38 49 65 97] 76 13 27 49

    J=5(76) [38 49 65 76 97] 13 27 49

    J=6(13) [13 38 49 65 76 97] 27 49

    J=7(27) [13 27 38 49 65 76 97] 49

    J=8(49) [13 27 38 49 49 65 76 97]

直接插入排序

void si_sort(int e[], int n)

{     int i, j, t;

       for(i=0; i< n; i++) {

              for(t=e[i], j=i-1; j>=0&&t<e[j]; j--)

                     e[j+1]=e[j];

              e[j+1]=t;

       }

}

二、选择排序

1） 基本思想：

　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2） 排序过程：

【示例】：

  初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 ［38 65 97 76 49 27 49]

第二趟排序后 13 27 ［65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [49 97 65 76]

第五趟排序后 13 27 38 49 49 [97 97 76]

第六趟排序后 13 27 38 49 49 76 [76 97]

第七趟排序后 13 27 38 49 49 76 76 [ 97]

最后排序结果 13 27 38 49 49 76 76 97

选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第一趟从n个记录中选取关键码最小的记录，第二趟从剩下的n-1个记录中选取关键码最小的记录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按关键码有序的序列。

操作方法：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。

【算法】

void SelectSort(S_TBL *s)

{ for(i=1；i<s->length；i++)

{ /* 作length-1趟选取 */

for(j=i+1，t=i；j<=s->length；j++)

{ /* 在i开始的length-n+1个记录中选关键码最小的记录 */

if(s->elem[t].key>s->elem[j].key)

t=j； /* t中存放关键码最小记录的下标 */

}

s->elem[t]<-->s->elem[i]； /* 关键码最小的记录与第i个记录交换 */

}

}

三、冒泡排序(BubbleSort)

1）基本思想：

　　两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

2）排序过程：

　　设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

【示例】：

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

冒泡排序算法实践：

void sb_sort(int e[], int n)

{     int j, p, h, t;

       for(h=n-1; h>0; h=p) {

              for(p=j=0; j<h; j++)

                     if(e[j]>e[j+1]) {

                            t=e[j]; e[j]=e[j+1]; e[j+1]=t;

                            p=j;

              }

       }

}

冒泡排序(Bubble Sort)算法分析：

先来看看待排序列一趟冒泡的过程：设1<j≤n，r[1],r[2],···,r[j]为待排序列，通过两两比较、交换，重新安排存放顺序，使得r[j]是序列中关键码最大的记录。一趟冒泡方法为：

① i=1； //设置从第一个记录开始进行两两比较

② 若i≥j，一趟冒泡结束。

③ 比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤

④ 当r[i].key>r[i+1].key时， r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]；将r[i]与r[i+1]交换；

⑤ i=i+1； 调整对下两个记录进行两两比较，转②

冒泡排序方法：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]，如此重复，直到n个记录按关键码有序的表。

四、快速排序（Quick Sort）

1）基本思想：

　　在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

2）排序过程：

【示例】：

初始关键字 [49 38 65 97 76 13 27 49］

第一次交换后［27 38 65 97 76 13 49 49］

第二次交换后［27 38 49 97 76 13 65 49］

J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］

I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］

J向左扫描 ［27 38 13 49 76 97 65 49］

（一次划分过程）

初始关键字［49 38 65 97 76 13 27 49］

一趟排序之后［27 38 13］ 49 ［76 97 65 49］

二趟排序之后［13］ 27 ［38］ 49 ［49 65］76 ［97］

三趟排序之后 13 27 38 49 49 ［65］76 97

最后的排序结果 13 27 38 49 49 65 76 97

快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。

【算法】

void QSort(S_TBL *tbl,int low,int high) /*递归形式的快排序*/

{ /*对顺序表tbl中的子序列tbl->[low…high]作快排序*/

if(low<high)

{ pivotloc=partition(tbl,low,high); /*将表一分为二*/

QSort(tbl,low,pivotloc-1); /*对低子表递归排序*/

QSort(tbl,pivotloc+1,high); /*对高子表递归排序*/

}

}

【效率分析】

空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。

时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。

理想情况下：每次划分，正好将分成两个等长的子序列，则

T(n)≤cn+2T(n/2) c是一个常数

     ≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)

≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

······

≤cnlog2n+nT(1)=O(nlog2n)

最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

五、堆排序(Heap Sort)

1）基本思想：

  堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

2）堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：

       Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

    堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。

3）排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

  堆排序

void sift(e, n, s)

int e[];

int n;

int s;

{     int t, k, j;

       t=e[s];

       k=s; j=2*k+1;

          while(j<n) {

              if(j<n-1&&e[j]<e[j+1])

                      j++;

                  if(t<e[j]) {

                         e[k]=e[j];

                         k=j;

                         j=2*k+1;

                   }else break;

                   }

                 e[k]=t;

}             

void heapsorp (int e[], int n)

              {     int i, k, t;

                     for(i=n/2-1; i>=0; i--)

                            sift(e, n, i);

                     for(k=n-1; k>=1; k--) {

                            t=e[0]; e[0]=e[k]; e[k]=t;

                            sift(e, k, 0);

                     }

              }

六、几种排序算法的比较和选择

1） 选取排序方法需要考虑的因素：

(1) 待排序的元素数目n；

(2) 元素本身信息量的大小；

(3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。

2） 小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。

(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。

比较一下上面谈到的各种内部排序方法：

首先，从时间性能上说：

1. 按平均的时间性能来分，有三类排序方法：

时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；

时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；

时间复杂度为O(n)的排序方法只有基数排序。

2. 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。

3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。