排序算法时间复杂度的研究

第 20卷第 5期 2004年 10月 商 丘 师 范 学 院 学 报 JOURNAI OF SHANGQIU TEACHERS COLLEGE V01．20 No．5 October，2004 排序算法时间复杂度的研究 陈树平。，梁咏梅 (1．商丘师范学院 计算机系，河南 商丘 476000；2．商丘工业学校，河南 商丘 476000) 摘 要：算法设计的好坏直接影响计算机的运行时间，计算机排序方法较多，时间复杂度差别较大．本文从理论 上研究 了线性排序(选择法、冒泡法、计数法)、比较排序、堆排序和快速排序等几种常用的排序算法的时间复杂度． 关键词：排序；算法；时间复杂度 ；程序；元素 中图分类号 ：TP311．11 文献标识码 ：A 文章编号 ：1672—3600{2004)05—0074—04 Research of sorting algorithems time complexity CHE N Shu—ping ，LIANG Yong—mei (1．Department of Coi'nputer，Shanqiu Teachers CoUpe，Shangqiu 476000。China；2．Shangqiu Industrial Selxx~l。Shan~ u 476000，China) Abstract：The design of algorithms composition indirectly influences running time of computer．There are many sorting algorithms，but time complexity of so rting algorithms have a great difference．A few of sorting algorithms LINER SORT(SELECTSORT，BUBBLE SORT)，COUNTSORT，SORTING BY COMPARISONS，HE AP— SORT and QUICKSORT’time complexity was researched． Key words：so rting；algorithms；time complexity；program ；element 0 引 言 排序问题是在计算机中经常出现的问题，通常我们将排序分为内部排序和外部排序。外部排序一般是对大量的数据排 序，数据不能同时放入计算机内存，在排序期间数据在内存和外存之间进行交换；内部排序是在排序期间，将数据放入计算机 内存的排序方法．本文主要研究内部排序算法．内部排序我们可以用线性排序(选择法、冒泡法、计数法)、比较排序、堆排序、快 速排序等多种方法实现。这些算法执行效率差别较大。我们通常用时间复杂度和空间复杂度来衡量算法效率．空间复杂度比 较简单，在目前计算机存储空间越来越大的情况下，我们更关心算法的时间复杂度．尽管目前计算机运行速度高得惊人，但如 果算法设计得不好，也不可能从根本上改变程序运行的效率，仍可能使程序运行速度缓慢．例如 A 算法的时间复杂度是 0(n)，B算法的时间复杂度是0(n )。如果A算法在1 S的时间能解决1000个问题。B算法只能解决10个问题。1 h A可以解 决3．6 X 10 个同样的问题，而 B只能解决 153个．如果将计算机的速度提高 1000倍，那么A在同样的时间内。可以解决1000 个同样的问题，而B只能解决 10倍同样的问题。所以我们应该在重视计算机速度的提高的同时，更应该注重研究程序的算法． 为了便于数据的统计和查找，我们往往对一些给定的数据按照某种规律进行重新组织，我们称为排序．例如将学生的考 试成绩按分数高低(或低到高)排名次，对于英文字典，按英文字母出现的先后顺序，排列英文单词，便于人们查阅．计算机排 序就是对给定的 n个元素Al、A2、⋯⋯、A 。每个元素 A 都有一个关键字K“按照关键字值的规律(从大到小或者从小到大) 进行顺序排列的一种关系． 收稿 日期 ：2003—09—26；修回日期：2003—12—02 作者简介：陈树平(1963一)，男，河南宁陵人，商丘师范学院副教授，主要从事计算机网络和数据库方面的研究 维普资讯 http://www.cqvip.com 第 5期 陈树平，等：排序算法时间复杂度的研究 75 1 线性排序 线性排序是不增加数组的排序空间，不改变排序数组的性质而只交换或标记数组的排序，如选择排序、冒泡法和计数法 都是线性排序算法 ． 1．1 选择排序 选择排序就是选择一个元素依次和后边的元素 比较，每一次得到一个较大元素．基本思想是对 ，1个元素，先选择第 1个元 素和第 2个元素进行比较，如果第 1个元素大于第 2个元素，则用第 1个元素再和第3个进行比较，否则如果第 1个元素小于 第2个元素，则将第 1个和第2个交换后，再用第 1个元素和第 3个比较；直到第 1个和第 个元素比较，如果第 1个元素大， 则它是最大者。否则将第 1个和第 个元素交换。第 1个元素仍是最大者．第2次再用第2个元素依次和后边的元素进行比较。 方法同前，结果得到第2个最大元素，依此类推，最后一次得 一1个元素和第 ，1个元素比较，大者放到前边．算法第 1次比较 一 1次，第 2次比较 一2次，最后比较 1次，整个算法的执行时间是： ( 一1)+( 一2)+⋯⋯ +2+1= ( 一1)12≈ n212 时间复杂度是 0( ) 1．2 冒泡法 冒泡法是将相邻的两个元素进行比较，比较结果将较大的元素放在前边，经过多次比较使最大的元素像气泡一样从下边 浮到上面．基本思想是首先将第1个元素和第2个元素进行比较。如果第 1个元素值大，再用第 2个元素与第 3个元素比较，否 则将第 1个元素与第2个元素交换后，再用第2个元素与第3个元素比较，依此类推，元素值大者放前边，第一轮比较结束，将 最小的元素值放到第 个位置，即最后．第二轮再用第1个元素依次和后边的元素比较，直到比较到第 一1个元素，即得到次 最小的元素，其值放在第 一1个位置．最后一轮只需要做第 1和第 2个元素的比较．算法的执行时间要以用下式表示为 萎( ： ≈雩 。 1 一 一 时间复杂度是 O(，l ) 1．3 计数排序 基本思想是对每一个元素增加一个标记以便统计有多少个元素大于该元素，从而找到该元素的正确位置．方法是用每 1 个元素和后边的元素比较，如果后边的元素值大，将该元素的记数标记加 1，否则如果后边的元素值小，将该后边的元素 记数标记加 1，每一轮比较结束，第 1个元素已经准确定位。其标记即为在排序的位置．然后再用第 2个元素依次和后边的比 较，依次类推，直到最后第 一1个元素和第 个元素比较，每个元素的记数标记就对应了该元素的排列位置．算法的执行时间 为 ( 一1)+( 一2)+⋯ +2+1= ( 一1)12≈ n212 时间复杂度是 O( ) 2 比较排序 我们考虑对 n个不知道结构的元素0l，02，⋯，0 进行排序，算法可以用决策二叉树来进行描述，操作过程是每一次对两 个元素进行比较，二叉树的每一个结点表示一个判定，如果判定成立，则走左子树，否则如果不成立，就走右子树．从比较排序 的道理我们很容易得到结论，在最坏情况下，分类 个元素的时间复杂度等于树的深度h． 由二叉树的构造原理，一棵高为 h的二叉树最多有 2 个叶，分类 个不同元素的任意判定树高至少是 log2n!。所以判定 树至少有 !个叶，故有下列不等式成立． 2 ≥ ! 取对数有，h≥ lo ! 由于log2n!描述不直观，所以往往将该式用更加直观的方式进行描述，可以用下面的推理： 1 11 X( 一1)⋯⋯2×1≥ ×( 一1)×⋯ ×(【n／2])≥ (【n／2]) 12 即 log2n!≥log2([n／2]) ／ ：(n／2)lo~([n／2])=(n／2)log2n一(n／2) 如果 ≥ 4，则 log2n≥ log24 11 2，于是(n／4)lo~n≥ hi2 所以 log2n!≥ (n／2)log2n一(n／2)≥ (n／2)logzn一(n／4)log2n=(n／4)log2n 维普资讯 http://www.cqvip.com 76 商 丘 师 范 学 院 学 报 2004正 即 log2n!≥ (n／4)log2n，故在最坏情况下，排序 n个元素的时间复杂度是O(1og2n!)，至少是 0((n／4)1og2n)次 ． Stifling对 n!更加精确的值是(n／e)”，即 log2n!= nlog2(n／e)≈ nlog2n一1．44n． 当 n足够大时，nlog2n一1．44n> (n／4)1og2n，所以更精确地讲，时间复杂度至少是 0(nlog2n一1．44n)． 3 堆排序 堆是具有层次结构的数据结构，它用二叉树表示，如果树的每个结点都大于或等于其儿子结点时，就组成了一个堆．很显 然，根结点标记的值最大．如果对 n个结点进行排序，首先将这 n个结点建成堆，若用A的下标变量来表示结点的标记，当1≤ i≤ n时，有 A(i)=n ．堆元素应该满足这样的规律 ：当 1≤ i≤ n／2时，即结点 A(i)的左儿子是 A(2。i)，右儿子是 A(2 i +1)，且有 A(i)≥ A(2 i)和 A(i)≥ A(2 i+1)，根结点的标记是 A(1)，最后一个结点的标记是 A(n)． 堆排序的基本思想是 ：如果 已经将这 n个排序结点的元素建成堆，显然最大的结点元素是根结点，将根标记的标记和最 后一个叶结点的标记进行交换，并将根结点保存．交换后，再将剩余的 n一1个结点重新组成堆，组成原则是新根结点和左右 两个儿子比较 ，如果 比两个儿子都大，则 自然成堆，否则与最大的儿子交换 ，交换后再与下边的左右儿子 比较，直到组成堆，将 根结点和第 n一1个结点交换，再将剩余的 n一2个结点重新组成堆，再交换，依次类推 ⋯⋯，最后对所有元素排序． 很明显，堆排序可以用两个过程来描述，建堆和交换，可以用下面的过程来进行形式描述 procedure buildheap for i= n tO 1 step一 1 do heap(i，n) endfor procedure heap(i，j) if A(i)不是 叶结点并且 A(i)的一个儿子大于 A(i) then元素 A(k)是 A(i)的最大儿子 ； 交换 A(i)和 A(k)； heap(k，j) endif 堆排序算法可以描述为： begin buildheap for i= n to 2 step一 1 交换 A(1)和 A(i) heap(1，i一1) endfor end 从以上算法不难看出buildheap的执行时间是线性时间，若 T(h)表示在深度为 h的结点上执行 heap算法的时间，c为交 换两变量值的时间，则有 T(h)≤ T(h一1)+c≤ T(h一2)+2c≤ ⋯⋯ ≤ k，故时间复杂度是 O(h)． 由于对每个结点都调用一次 heap(i，n)，所用调用 buildheap就等于对所有结点按高度花费时间之和．如果结点总数是 ， 每次调用 heap(1，i一1)需要时间 ≤ log2n，调用 次 heap算法需要 0(nlog2n)时间，所以算法的时间复杂度是 0(nlog2 )． 4 快速分类 1962年 Hoare提出了快速分类算法，它是 目前为止比较次数最少 、速度最快的一种分类方法．基本 思想是：首先取第一个 记录的值作为控制关键字，并把该记录放到文件中的合适位置 (i)，使得该记录的左端标记都大于 (i)，右端标记都小于 口(i)．这时将文件分成了由记录 口(1)、v(2)、⋯⋯、口(i一1)和 口(i+1)、口(i+2)、⋯⋯、口( )组成的两个子文件，依此再将这 两个子文件继续分类，直到分类完成 ． 假定 s是一个输入队列，快速分类算法可以用递归的方式描述： 维普资讯 http://www.cqvip.com 第 5期 陈树平，等 ：排序算法时间复杂度 的研究 procedure quicksort(S) if S只包含一个元素 返 回 else Begin 从 S中选择一个元素 v作为分类元素；使得 队列 s1中的元素均大于 v； 队列 s2中的元素均等于 v； 队列 s3中的元素均小于 v； quicksort(s1) quicksort(s3) end 依据算法的设计思想，第一次就将 个元素分为大小相同的两个子队列，第一遍执行后，比较次数为 一1，所需时间为 O(n)或者 cn，依此进行分类 ，快速分类的时间复杂度为 O(nlog2n)，可以用下式计算： T( )≤ cr／+2T(n／2)≤ crl+2(crl／2+ T(n／4)≤ ⋯⋯ ≤ cr1．1og2 + T(1)= O( log2 ) 这种算法和二又树类似．对 个元素组成的完全二又树，深度为 1og2n，这是一种理想的情况．但是对于快速分类算法，时 间复杂度的期望值很接近于该值． 如果我们选择的某元素不是将队列分为两个大小相等的队列，而是将元素分为由 i一1和 — 个元素组成的两个队列， 则期望时间复杂度可以表示为 T㈩ ≤ 上 r／耋i= T -1)+T( ] 当 ≥2时 当 i从 1执行到 ，出现两个 T(O)、T(1)、⋯⋯、T( 一1)，故上式可以改写为 T( )≤ c + r／ i =0 T( ) 当 ≥ 2时 ‘ 如果令 b= T(0)= T(1)，当 ≥ 2时，T( )≤ knlog~n，这里 K =2c+2b．当 =2时，很明显有 T(2)≤ 2c+26． 上式容易证明：T( )≤knlog~n，即分类 个元素的平均时间复杂度是0(knlog~n)．我们可以得出结论，快速分类算法的 时间复杂度最低． 5 结 论 上述几种排序算法，对于同一问题 线性排序 的时间复杂度是 O( )，比较排 序时间复杂度是 O(1og2 )，至少是 O(n／4log2 )，堆排序时间复杂度是 O(nlog2 )，快速排序时间复杂度和期望时间复杂度均是 O(knlog~n)．从上我 们可以看 出，如果选择算法不合适，可能会使运行效率出现很大差别．对于排序问题，随着排序元素的数 目增加，算法的选用显得越来 越重要，从时间复杂度我们可以得出结论，在快速排序算法时间增长几倍的情况下，使用线性排序算法可能会使运行时间延 长数 10倍，甚至更长时间，因此我们在处理问题时一定要注重算法的研究． 参考文献： [1] 宋文，吴晟，杜亚军．算法设计与分析[M]．重庆：重庆大学出版社，2001． [2] Michael Sipser(美)，(张立昂，王捍贫，等译)．计算理论导引[M]．北京：机械工业出版社，2000． [3] 王广芳，曹兰斌，黄孝慈．数据结构[M]．长沙：湖南科学技术出版社，1983． [4] 王晓东．计算机算法设计与分析[M]．北京：电子工业出版社，2001． 维普资讯 http://www.cqvip.com