姜忠華，徐文麗，劉家文，朱豪杰

（1.電子科技大學(xué) 物理電子學(xué)院，四川 成都610054；2.電子科技大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都 610054）

排序是計(jì)算機(jī)科學(xué)中最重要的研究課題之一，由于它具有極高的理論及實(shí)用價(jià)值 ，在2000年被列為對(duì)科學(xué)和工程計(jì)算的研究與實(shí)踐影響最大的十大問題之一[1-3]?；镜呐判騿栴}一般是指給定一個(gè)數(shù)據(jù)項(xiàng)集 ，使其中的數(shù)據(jù)按遞增或遞減排列，數(shù)據(jù)項(xiàng)可以是具有線性順序的任意對(duì)象[4-5]。

排序算法一般分為整體排序和先局部再整體。整體排序一般比較慢，排序時(shí)間復(fù)雜度為O（n2）；而先局部再整體的方法能使排序性能提高，比如：希爾排序、歸并排序、基數(shù)排序等，但如果運(yùn)用不好局部性原理反而會(huì)增加排序復(fù)雜度，所以正確運(yùn)用局部規(guī)律是提高排序速度的關(guān)鍵。比如，快排在無序的情況效果最好，而有序、倒序時(shí)用快排則會(huì)導(dǎo)致數(shù)據(jù)大量的交換，使整個(gè)排序的速度非常慢[6-8]。

1 歸并排序

歸并排序也是一種先局部排序再整體排序的一種方法，其首先將要?dú)w并的兩部分?jǐn)?shù)據(jù)有序，然后再將兩個(gè)有序部分進(jìn)行歸并（即將數(shù)據(jù)按順序存放在臨時(shí)空間，然后再拷貝回排序數(shù)據(jù)空間）。歸并排序在數(shù)據(jù)無規(guī)律的情況下，歸并排序性能較好[9]。但數(shù)據(jù)只有少量無序時(shí)，歸并的比較次數(shù)也不會(huì)變化。因此無論是在最好還是最壞的情況下，歸并的時(shí)間復(fù)雜度都是O（nlog2n）。歸并排序最后需要不斷將兩部分已經(jīng)有序的數(shù)據(jù)進(jìn)行合并，合并過程中需要大量的拷貝數(shù)據(jù)，因此相對(duì)其他快速算法而言，合并需要較長(zhǎng)的時(shí)間。但對(duì)排序有穩(wěn)定性要求時(shí)，其他快速算法是（比較排序的方法）無法做到的。

影響歸并排序的性能主要有兩個(gè)方面：首先歸并排序是將序列分成均勻的兩部分，對(duì)兩部分分別排序之后再合并而成，即使在已經(jīng)有序的情況下也是如此，有時(shí)強(qiáng)制性的將數(shù)據(jù)劃為兩部分會(huì)帶來不必要的運(yùn)算，比如在已經(jīng)有序（正序、逆序）或部分已經(jīng)有序的數(shù)據(jù)歸并過程中，再不需要強(qiáng)行將其劃分成幾個(gè)部分；在歸并過程中，將兩組數(shù)據(jù)進(jìn)行比較后，按順序依次將數(shù)據(jù)拷貝到另一個(gè)臨時(shí)空間中，最后再把數(shù)據(jù)拷貝回待排序的空間，這些拷貝將耗費(fèi)CPU大量的時(shí)間，將會(huì)在第4部分的實(shí)驗(yàn)結(jié)果中體現(xiàn)出來。

2 實(shí)現(xiàn)思想及方法

智能歸并排序是根據(jù)數(shù)據(jù)本身的特性來劃分歸并的組，而不是強(qiáng)制地劃分為均勻的兩部分；為了減少每次歸并后須將臨時(shí)空間數(shù)據(jù)復(fù)制回原數(shù)據(jù)空間所耗費(fèi)的時(shí)間，采用將數(shù)據(jù)的原數(shù)據(jù)空間和臨時(shí)存放數(shù)據(jù)空間交替作為排序的目標(biāo)方法。

2.1 劃分歸并的組

針對(duì)數(shù)據(jù)排序前已經(jīng)部分或者整體有序時(shí)，歸并時(shí)則不需將已經(jīng)有序的數(shù)據(jù)進(jìn)行拆分，而是用一組數(shù)據(jù)記錄待排序數(shù)據(jù)中連續(xù)非遞減的范圍，根據(jù)其范圍分為不同的組，在分組的內(nèi)部已經(jīng)有序，然后將這些有序的組按照歸并的方法不斷進(jìn)行歸并，最終實(shí)現(xiàn)數(shù)據(jù)完全有序。

僅按照非遞減進(jìn)行組，就會(huì)存在很大的局限性。比如在大量的數(shù)據(jù)是逆序的情況時(shí)，就會(huì)退化為歸并排序，為了使在逆序的情況也能達(dá)到較好的性能，在進(jìn)行歸并之前也記錄下逆序的數(shù)據(jù)的范圍，然后將逆序的數(shù)據(jù)通過旋轉(zhuǎn)方法（按照數(shù)據(jù)順序不斷進(jìn)行頭尾交換）轉(zhuǎn)換為正序的數(shù)據(jù)，然后再將旋轉(zhuǎn)過后的最后一個(gè)數(shù)據(jù)和下一個(gè)數(shù)據(jù)比較，如果還能滿足非遞減規(guī)律，則繼續(xù)比較，直到不滿足非遞減規(guī)律為止。

2.2 原數(shù)據(jù)空間和臨時(shí)存放數(shù)據(jù)空間

本算法通過交替使用原數(shù)據(jù)空間和臨時(shí)存放數(shù)據(jù)空間作為排序的目標(biāo)方法，來減少歸并后須將臨時(shí)空間數(shù)據(jù)復(fù)制回原數(shù)據(jù)空間所耗費(fèi)的時(shí)間，即首先將臨時(shí)存放空間作為歸并存放目標(biāo)，當(dāng)歸并完成后的結(jié)果已全部存放在臨時(shí)空間時(shí)，再將臨時(shí)空間作為排序目標(biāo)，而原數(shù)據(jù)空間作為歸并存放的臨時(shí)數(shù)據(jù)空間，依次循環(huán)下去，從而節(jié)約了數(shù)據(jù)在原數(shù)據(jù)空間與臨時(shí)存放數(shù)據(jù)空間往返復(fù)制所需的時(shí)間。

3 算法描述

4 算法的時(shí)間復(fù)雜度

智能歸并排序算法最壞的情況時(shí)退化為2路歸并。時(shí)間復(fù)雜對(duì)為（nlong2n），但在實(shí)際情況中很少存在退化為2路歸并的情況，即使在均勻分布時(shí)其效果也可以將最初的n/2塊無序數(shù)據(jù)塊變?yōu)閚/3塊局部有序的數(shù)據(jù)組，從而具有較快的歸并速度。智能歸并的算法對(duì)數(shù)據(jù)局部正序或局部逆序的情況時(shí)都有較好的性能。

歸并排序是一種快速算法中穩(wěn)定算法，智能歸并排序算法并沒有破壞其穩(wěn)定性，保持了歸并算法的優(yōu)勢(shì)，并且又能較好地利用數(shù)據(jù)本身的一些規(guī)律，從而實(shí)現(xiàn)了智能化的劃分歸并的組。

5 實(shí)驗(yàn)結(jié)果及分析

在 Inter（R）Core（TM）2 Duo CPU E7500@2.93 GHz，4 GB RAM的硬件條件下，采用不同的快速算法對(duì)1 000 000個(gè)數(shù)據(jù)進(jìn)行排序，其所耗CPU的時(shí)間（ms）對(duì)比如表1所示。

表1 不同算法對(duì)排序所需時(shí)間的對(duì)比Tab.1 Contrast of sorting time to different algorithms

從表1可以看出，智能歸并排序算法具有相當(dāng)大的優(yōu)勢(shì)。在整體或者局部正序、逆序的情況下，智能歸并排序算法具有較好的性能，并且當(dāng)已經(jīng)有序（正序、逆序）能夠進(jìn)行判別，從而有效地避免了不必的要排序。即使在最壞的情況，即隨機(jī)分布的時(shí)候也可將原數(shù)據(jù)拆分為總數(shù)的（1/3）塊已經(jīng)有序的組，此時(shí)智能歸并排序所耗的時(shí)間大概是歸并排序所耗時(shí)間的2/3，也同時(shí)由于快速排序。

通過表1的列4，列5對(duì)比可以看出，數(shù)據(jù)拷貝需要花費(fèi)更長(zhǎng)的CPU時(shí)間，通過不斷地將臨時(shí)數(shù)據(jù)空間和原數(shù)據(jù)空間交換作為排序的目標(biāo)空間能節(jié)約相當(dāng)長(zhǎng)的一部分拷貝所需的時(shí)間。從傳統(tǒng)快速排序所耗的時(shí)間可以看出，在正序分布、逆序分布及等值分布時(shí)，由于空間復(fù)雜度為O（n2），所以導(dǎo)致棧溢出錯(cuò)誤。在其局部有序（波型分布、峰型分布及谷型分布）時(shí)由于選擇的中間值沒有加以預(yù)處理的原因，其耗時(shí)較長(zhǎng)，當(dāng)然可以通過加以預(yù)處理可使其達(dá)到較好的性能[4-6]，在此處不予討論。

6 結(jié)束語

從理論和試驗(yàn)的結(jié)果可以看出，智能歸并排序算法由于能較好的利用數(shù)據(jù)本身具有的規(guī)律，并減少歸并排序數(shù)據(jù)的拷貝時(shí)間，使得排序的時(shí)間復(fù)雜度上明顯優(yōu)于傳統(tǒng)歸并排序算法，并且在隨機(jī)排序的情況下，其排序性能也明顯優(yōu)于快速排序。并且智能歸并排序本身又具有歸并排序，所以這種排序方法也具有穩(wěn)定性的優(yōu)勢(shì)。因此該方法對(duì)基排序有很大的意義[3-7]。

[1]Dongarra J J，Sullivan F.The top 10 algorithms in 20th century[J].IEEE Computing in Science&Engineering，2000（2）:22-23.

[2]YAN Wei-min，WU Wei-min.Data Structures[M].Beijing:Tsinghua University Press，1992.

[3]周立林，鄭建秀.快速排序的改進(jìn)算法[J].上饒師范學(xué)院學(xué)報(bào)，2001，21（6）：12-13.ZHOU Li-lin，ZHENG Jian-xiu.The improved algorithm on the quicksort[J].Journal of Shangrao Normal College，2001，21（6）：12-13.

[4]Thompson C D，Kung H T.Sorting on a mesh-connected parallel computer[J].Communications of the ACM， 1977，20（4）：263.

[5]HUO Hong-wei， XU Jin.Quick sortalgorithm[J].Microelectronics and Computer，2002（6）：6-9.

[6]Borodin A，Hopcroft J E.Routing， merging and sorting on parallel models of computation[C]//Proc.Fourteenth Annual ACM Symp.on Theory of Computing，SomFrancisco， CA，1982：338-344.

[7]Todd S J P.The peterlee relational test vehicle—a system overview[J].IBM Systems Journal，1976（15）：285.

[8]FU Qing-xiang，WANG Xiao-dong.Algorithms and data structures[M].Beijing:Electronics Industry Press，1998.

[9]Batcher K E.Sorting networks and their applications[C]//Proc.AFIPS Spring Joint Summer Computer Conf.ACM，New York:Goodyear Aerospace Corporation， Akron， Ohio:1968 （32）：307-314.