排序算法在某系統(tǒng)中的應(yīng)用

曹小陽(yáng)　王琨

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

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

一、前言

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

二、排序算法簡(jiǎn)介

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

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

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

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

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

軟件采用快速排序算法。快速排序是由冒泡排序改進(jìn)而得的，它的基本思想是：在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），把該記錄放在最終的位置后，數(shù)據(jù)序列被此記錄分割成兩部分。所有中軸點(diǎn)比該記錄中軸點(diǎn)小的放置在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個(gè)過(guò)程稱(chēng)作一趟快速排序。之后對(duì)所有的兩部分分別重復(fù)上述過(guò)程，直至每部分內(nèi)只有一個(gè)記錄為止。

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

假設(shè)T（n）為n個(gè)記錄r[1，n]進(jìn)行排序所需時(shí)間，則由算法可得：

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

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

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

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

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

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

算法步驟如下：

1、將與中軸點(diǎn)相同的元素放到序列兩端；

2、一次排序結(jié)束后將兩端相同元素放到中軸點(diǎn)周?chē)?/p>

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

四、結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7] Anany Levitin.算法設(shè)計(jì)與分析基礎(chǔ)，潘彥譯.清華大學(xué)出版社，2014-1.

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