曹小陽　王琨

摘 要：排序是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素或記錄的任意序列，重新排列成一個按中軸點有序的序列。本文簡要論述幾種常見的排序算法，重點討論快速排序及其優(yōu)化。

關(guān)鍵詞：中軸點；快速排序；分治；優(yōu)化

一、前言

某系統(tǒng)軟件在整個運行過程中采集和分析終端數(shù)據(jù)，并以列表形式終端信息。為方便查看，需要根據(jù)信息類型進行排序。因此，學習和研究各種排序算法是系統(tǒng)軟件開發(fā)人員的重要課題之一。

二、排序算法簡介

由于待排序的記錄數(shù)量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為內(nèi)部排序和外部排序兩大類。內(nèi)部排序指的是待排序記錄存放在計算機隨機存儲器中進行的排序過程；外部排序指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。本文只討論內(nèi)部排序。內(nèi)部排序的方法很多，但就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境下使用。按排序過程中依據(jù)的不同原則對內(nèi)部排序方法進行分類，大致可分為插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。

插入排序?qū)⒁粋€數(shù)據(jù)插入到已經(jīng)排好序的有序序列中，從而得到一個新的、個數(shù)加一的有序序列；交換排序根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置，將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動；選擇排序每一趟在記錄中選取中軸點最小的記錄作為有序序列中第i個記錄；歸并排序?qū)蓚€已經(jīng)排序的序列合并成一個序列；基數(shù)排序借助多中軸點排序的思想對單邏輯中軸點進行排序。

各內(nèi)部排序方法的平均時間、最壞情況和所需輔助存儲如下：

從平均時間性能而言，快速排序最佳，其所需時間最省。

三、快速排序算法及優(yōu)化

軟件采用快速排序算法?？焖倥判蚴怯擅芭菖判蚋倪M而得的，它的基本思想是：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄放在最終的位置后，數(shù)據(jù)序列被此記錄分割成兩部分。所有中軸點比該記錄中軸點小的放置在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一趟快速排序。之后對所有的兩部分分別重復上述過程，直至每部分內(nèi)只有一個記錄為止。

一趟快速排序采用從兩頭向中間掃描的方法，同時交換與基準記錄逆序的記錄。

假設T（n）為n個記錄r[1，n]進行排序所需時間，則由算法可得：

T（n）=Tpass（n）+T（k-1）+T（n-k）

其中Tpass（n）為對n個記錄進行一趟快速排序所需時間，由算法可知，它和記錄數(shù)n成正比，可以cn表示；T（k-1）和T（n-k）分別為對r[1，k-1]和r[k+1，n]中記錄進行快速排序所需時間。如果待排序列中的記錄是隨機排列的，則在一趟排序之后，k取1至n之間任何一值的概率相同，快速排序所需時間的平均值則為knlnn。

在所有同數(shù)量級的排序方法中，快速排序的常數(shù)因子k最小。因此，就平均時間而言，快速排序是目前被認為是最好的一種內(nèi)部排序方法。但是，若初始記錄序列按中軸點有序或基本有序時，快速排序?qū)ⅠR上退化到起泡排序，其時間復雜度為O（n2），這是由于選定的中軸點每次都會跟剩余的所有元素做比較，每一次的排序只能使待排序列減一。顯然，該情況下，排序算法的效率很低。究其原因，是算法每次都選擇左端點作為中軸點。

由上面可知影響快速排序速度的一個重要因素是中軸點的選取，可以將中軸點的選擇隨機化，不再是固定選擇左端點，而是利用隨機數(shù)生成一個有效的位置作為中軸點。在有序序列的排序上面，改進后的算法有很大進步，但是當待排序列中所有元素相等時，仍然會出現(xiàn)最壞情況，時間復雜度為O（n2）。

理想情況下，選擇中軸點時，最佳選擇是將待排序列劃分為兩個相等長度的子序列，但是要達到這種狀態(tài)需要經(jīng)過大量計算，會帶來時間消耗，一種近似的估計取法是隨機選擇三個排序元素并且用三個元素的中值作為中軸點。

針對包含大量重復元素的序列，理想情況下是在一次排序完成后，下一次排序不需要再對重復元素進行比較，即相同元素不參與后續(xù)的遞歸，改進方法是在一次排序后，將與中軸點相同的元素放在一起，減少迭代次數(shù)，將待排序列劃分為三個區(qū)域：小于中軸點，等于中軸點，大于中軸點。

算法步驟如下：

1、將與中軸點相同的元素放到序列兩端；

2、一次排序結(jié)束后將兩端相同元素放到中軸點周圍。

軟件采用該算法對終端信息進行排序，效率得到明顯提升。

四、結(jié)束語

系統(tǒng)的正常運行，表明該排序算法可滿足現(xiàn)有需求。但是，算法還存在缺陷，當待排序列足夠小時，插入排序的效率很高，可以將算法改進為在排序前判斷待排序列大小，當待排序列元素個數(shù)小于某一個值時使用插入排序。（作者單位：南京模擬技術(shù)研究所）

參考文獻：

[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).清華大學出版社，2007-04.

[2] 李春葆.數(shù)據(jù)結(jié)構(gòu).清華大學出版社，2004-01.

[3] Stanley B.Lippman、Josee Lajoie.C++Primer第三版，潘愛民、張麗譯.中國電力出版社，2002-05.

[4] Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析，馮舜璽譯.機械工業(yè)出版社，2004-01.

[5] 程杰.大話數(shù)據(jù)結(jié)構(gòu).清華大學出版社，2011-06.

[6] Thomas H.Cormen、Charles E.leiserson、Ronald L.Rivest et al.算法導論，殷建平、徐云、王剛譯.機械工業(yè)出版社，2013-01.

[7] Anany Levitin.算法設計與分析基礎，潘彥譯.清華大學出版社，2014-1.

[8] Sedgewick.算法，謝路云譯.人民郵電出版社，2012-10.