王明芳

摘要:內(nèi)部排序的方法很多,基于不同的運(yùn)行環(huán)境,各種方法有各自的優(yōu)點(diǎn)和缺點(diǎn)。就全面性能而言,無(wú)法指明哪種排序方法是最好的。為了提高計(jì)算機(jī)對(duì)數(shù)據(jù)處理的工作效率,本文對(duì)各種排序的方法和對(duì)應(yīng)的算法進(jìn)行了比較,進(jìn)而選出最為適合的算法。

關(guān)鍵詞:內(nèi)部排序;時(shí)間復(fù)雜度;空間復(fù)雜度

排序就是把一組記錄(元素)按照某個(gè)域的值的遞增或遞減的次序重新排列的過(guò)程。內(nèi)部排序指的是待排序的記錄都存放在計(jì)算機(jī)內(nèi)存中的排序過(guò)程。按排序的規(guī)則不同,可分為五類(lèi):插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序。本文將對(duì)這五種排序方法進(jìn)行比較,從而給出內(nèi)排序的選擇規(guī)則。

1基本思想

1.1插入排序

插入排序的基本思想是:每次將一個(gè)待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置,直到全部記錄插入完成為止。插入排序方法有:直接插入排序和希爾排序。

1.2交換排序

交換排序的基本思想是:兩兩比較待排序記錄的關(guān)鍵字,發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換,直到?jīng)]有反序的記錄為止。應(yīng)用交換排序基本思想的主要排序方法有:冒泡排序和快速排序。

1.3選擇排序

選擇排序的基本思想是:每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄,順序放在已排好序的子文件的最后,直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。

1.4歸并排序

歸并排序是利用“歸并”技術(shù)來(lái)進(jìn)行排序。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。這里,我們以?xún)陕窔w并方法做介紹。兩路歸并的基本思想是排序開(kāi)始時(shí)將待排序列看成n個(gè)已排好序的子序列,每一個(gè)子序列中只含有一個(gè)記錄。將兩個(gè)相鄰的子序按算法merge逐一兩兩合并,得到n/2個(gè)有序子序列。每個(gè)子序列中含有2個(gè)記錄(最后一個(gè)可能只有1個(gè)記錄的子序列),這是第一趟歸并的結(jié)果。第二趟歸并在第一趟歸并的結(jié)果上進(jìn)行,再將相鄰的子序逐一兩兩合并,得n/2/2個(gè)有序子序列。如此類(lèi)推,直到最后歸并得到一個(gè)有序序列為止。

1.5基數(shù)排序

要了解基數(shù)排序,首先要了解桶式排序:如果我們有N個(gè)整數(shù),范圍從1到M(或從0到M-1),我們留置一個(gè)數(shù)組A,大小為M,并初始化為0。于是該數(shù)組有M個(gè)單元(我們稱(chēng)之為桶),開(kāi)始他們都是空的。當(dāng)數(shù)a被讀入時(shí),A[a]增1。當(dāng)所有的輸入被讀進(jìn)時(shí),掃描數(shù)組,打印出排好序的表。這就是所謂的桶式排序。

當(dāng)M很大N很小時(shí),空間嚴(yán)重浪費(fèi)。這就推廣出基數(shù)排序。我們選取某個(gè)較小的數(shù)做為基數(shù),比如10,那么我們就只需要10個(gè)桶。當(dāng)M大于基數(shù),我們采用多趟桶式排序。比如M=1000,那么我們需要3次桶式排序。具體做法是用最低有效位優(yōu)先的方式,將各個(gè)數(shù)放入桶中;然后遍歷各個(gè)桶依據(jù)次最低有效位來(lái)調(diào)整,依次類(lèi)推直到最高有效位。這便是基數(shù)排序的基本思想。

2比較

排序在計(jì)算機(jī)程序設(shè)計(jì)中非常重要,上面講述的各種排序方法各有其優(yōu)缺點(diǎn),適用的場(chǎng)合也不同。以下我們針對(duì)以上各種方法在時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性及算法簡(jiǎn)單性等幾方面進(jìn)行比較。

2.1時(shí)間復(fù)雜度

從平均時(shí)間復(fù)雜度來(lái)考慮,直接插入排序、冒泡排序、直接選擇排序是三種簡(jiǎn)單的排序方法,時(shí)間復(fù)雜度都為O(n2),而快速排序、堆排序、二路歸并排序的時(shí)間復(fù)雜度都為O(nlog2n),希爾排序的復(fù)雜度介于這兩者之間。

若從最好的時(shí)間復(fù)雜度考慮,則直接插入排序和冒泡排序的時(shí)間復(fù)雜度最好,為O(n),其它的最好情形同平均情形相同。

若從最壞的時(shí)間復(fù)雜度考慮,則快速排序的為O(n2),直接插入排序、冒泡排序、希爾排序同平均情形相同,但系數(shù)大約增加一倍,所以運(yùn)行速度將降低一半,最壞情形對(duì)直接選擇排序、堆排序和歸并排序影響不大。

2.2空間復(fù)雜度

歸并排序的空間復(fù)雜度最大,為O(n),快速排序的空間復(fù)雜度為O(log2n),其它排序的空間復(fù)雜度為O(1)。

2.3穩(wěn)定性

直接插入排序、冒泡排序、歸并排序是穩(wěn)定的排序方法,而直接選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。

2.4算法簡(jiǎn)單性

直接插入排序、冒泡排序、直接選擇排序都是簡(jiǎn)單的排序方法,算法簡(jiǎn)單,易于理解,而希爾排序、快速排序、堆排序、歸并排序都是改進(jìn)型的排序方法,算法比簡(jiǎn)單排序要復(fù)雜得多,也難于理解。

3選擇規(guī)則

3.1根據(jù)時(shí)間/空間復(fù)雜度選擇

對(duì)元素個(gè)數(shù)較多的排序,可以選快速排序、堆排序、歸并排序,元素個(gè)數(shù)較少時(shí),可以選簡(jiǎn)單的排序方法。盡量選空間復(fù)雜度為O(1)的排序方法,其次選空間復(fù)雜度為O(log2n)的快速排序方法,最后才選空間復(fù)雜度為O(n)二路歸并排序的排序方法。

3.2一般性選擇規(guī)則

待排序元素的個(gè)數(shù)n較大,排序碼分布是隨機(jī),而對(duì)穩(wěn)定性不做要求時(shí),則采用快速排序?yàn)橐?。待排序元素的個(gè)數(shù)n大,內(nèi)存空間允許,且要求排序穩(wěn)定時(shí),則采用二路歸并排序?yàn)橐?。待排序元素的個(gè)數(shù)n大,排序碼分布可能會(huì)出現(xiàn)正序或逆序的情形,且對(duì)穩(wěn)定性不做要求時(shí),則采用堆排序或二路歸并排序?yàn)橐恕４判蛟氐膫€(gè)數(shù)n小,元素基本有序或分布較隨機(jī),且要求穩(wěn)定時(shí),則采用直接插入排序?yàn)橐?。待排序元素的個(gè)數(shù)n小,對(duì)穩(wěn)定性不做要求時(shí),則采用直接選擇排序?yàn)橐?若排序碼不接近逆序,也可以采用直接插入排序。冒泡排序一般很少采用?；鶖?shù)排序可在O(d × n)時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序,d是指單邏輯關(guān)鍵字的個(gè)數(shù),一般遠(yuǎn)少于n。但基數(shù)排序只適用于字符串和整數(shù)這類(lèi)有明顯結(jié)構(gòu)特征的關(guān)鍵字。若n很大,d較小時(shí),用基數(shù)排序較好。其它。前面討論的排序算法,除基數(shù)排序外,都是在向量存儲(chǔ)上實(shí)現(xiàn)的。當(dāng)記錄本身的信息量很大時(shí),為避免大量時(shí)間用在移動(dòng)數(shù)據(jù)上,可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。插入排序和歸并排序都易在鏈表上實(shí)現(xiàn),但有的排序方法,如快速排序和堆排序在鏈表上卻很難實(shí)現(xiàn)。

4結(jié)論

根據(jù)以上的論述及比較,我們看出,不同的運(yùn)行環(huán)境,不同應(yīng)用的需求,對(duì)算法的影響是很顯著的。有些算法理論上是優(yōu)化了,但實(shí)際運(yùn)行時(shí)就不一定最好的。我們無(wú)法確定一種算法是否是最優(yōu)的:有的適用于n較大的情況;有的適用于n較小的情況;有的適用于初始序列基本有序;而有的又在初始序列基本有序時(shí)效率最低。因此不能一概而論,應(yīng)該具體情況具體分析。

參考文獻(xiàn)

[1]嚴(yán)蔚敏,吳偉民數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).北京:清華大學(xué)出版社 2000;

[2]Ellis Horowitz(美) 等. 譯者:李建中等數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) .北京 機(jī)械工業(yè)出版社 2006

[3]徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程 .北京 清華大學(xué)出版社2006.