基于JAVA的快速排序

邢素萍

0 引言

信息是計算機(jī)學(xué)科的基礎(chǔ)，信息必須以數(shù)據(jù)的方式，按一定的規(guī)則存儲在計算機(jī)的存儲器中。對數(shù)據(jù)的操作方法如增加、插入、刪除、查詢等既要考慮數(shù)據(jù)的存儲，又要考慮數(shù)據(jù)操作中數(shù)據(jù)的處理速度等各方面的因素。因此，怎樣更科學(xué)的設(shè)計算法，采用哪種程序設(shè)計語言能更好地實現(xiàn)算法是非常重要的。

著名的瑞士科學(xué)家 N.Wirth曾指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。其中數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法是對數(shù)據(jù)運(yùn)算的描述。由此可見，程序?qū)嵸|(zhì)是對具體問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，再設(shè)計一個好的算法，而好的算法通常取決于實際問題的數(shù)據(jù)結(jié)構(gòu)。Java語言作為面向?qū)ο蟮某绦蛟O(shè)計語言，它提供了許多特性來持封裝，每個數(shù)據(jù)項均封裝在某個對象中。每條可執(zhí)行的語句均由某個對象來完成。每個對象均是某個類的實例或是一個數(shù)組。每個類均在一個單繼承的層次結(jié)構(gòu)中定義。Java的單繼承層次結(jié)構(gòu)是一種樹型結(jié)構(gòu)，它的根是object類。Java的面向?qū)ο蟮奶攸c使得它特別適合于數(shù)據(jù)結(jié)構(gòu)的設(shè)計和實現(xiàn)，為程序員提供了一個很好的開發(fā)平臺。因而，采用當(dāng)今流行的跨平臺程序設(shè)計語言java實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的設(shè)計，可以很好地解決對數(shù)據(jù)存儲方式、處理方式的具體化問題。另外，利用 java語言程序設(shè)計的靈活性及交互性，實現(xiàn)數(shù)據(jù)的動態(tài)輸入，自動、分步、循環(huán)執(zhí)行存儲處理過程，并可在Internet上發(fā)布。

排序（Sorting）又稱分類，廣泛地應(yīng)用在事務(wù)處理及各種數(shù)據(jù)加工的過程中，如果數(shù)據(jù)能夠根據(jù)某種規(guī)則排序，就能大大提高數(shù)據(jù)處理的算法效率。如，在英文字典中按英文字母順序單詞排列單詞，使我們可以很快速地從一本厚厚的字典中找到所要查找的單詞。在計算機(jī)處理數(shù)據(jù)之前也要對其先進(jìn)行排序，它是計算機(jī)程序設(shè)計中的一種重要操作。

1 排序的概念

所謂排序就是整理文件中的記錄，使之按關(guān)鍵字遞增（或遞減）的次序排列起來。

假設(shè)含n個記錄的序列為｛R1,R2,…,Rn｝，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…,K}，需確定 1,2,…,n的一種排列Ri1,Ri2,…Rin，使其相應(yīng)的關(guān)鍵字滿足 Ki1≤Ki2≤…≤Kin(或Kn≥Ki2≥…≥Kin)的關(guān)系。排序的對象是文件，它由一組記錄組成。每條記錄則由一個或若干個數(shù)據(jù)項（或域）組成。排序運(yùn)算的依據(jù)是可用來標(biāo)識一個記錄的一個或多個組合數(shù)據(jù)項，我們稱其為關(guān)鍵字（Key）。當(dāng)待排序記錄的關(guān)鍵字均不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則這種排序方法是不穩(wěn)定的。快速排序被認(rèn)為是目前基于比較記錄關(guān)鍵字的內(nèi)部排序中最好的排序方法。

2 快速排序的基本思想

快速排序是C.R.A.Hoare提出的一種劃分交換排序。此排序方法采用了一種分治的策略，通常稱其為分治法（Divide-and-ConquerMethod）。分治法的基本思想是：將原問題分解為若干個規(guī)模更小結(jié)構(gòu)與原問題相似的子問題，遞歸地解這些子問題。然后將這些子問題的解組合為原問題的解。這樣在用遞歸描述的分治算法的每一層遞歸上，都有以下3個步驟：

分解：將原問題分解為若干個子問題；

求解：遞歸地解各子問題，若子問題的規(guī)模足夠小，則直接求解；

組合：將各子問題的解組合成原問題。

若把當(dāng)前待排序的無序區(qū)設(shè)為 R[low……h(huán)igh] ,利用上面方法可將快速排序的基本思想描述為：

1．分解。在 R[low……h(huán)igh] 任選一個記錄作基準(zhǔn)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個較小的子區(qū)間R[low……pivotpos-1] 和R[pivotpos＋1……h(huán)igh] ,并使左邊子區(qū)間中所記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄（設(shè)基準(zhǔn)記錄為pivot）的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置（pivotpos）上，不用參加后續(xù)的排序。因此，劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos，劃分的結(jié)果可以簡單地表示為：

R[low……pivotpos-1] .keys≤R[pivotpos] .key≤R[pivotpos＋1……h(huán)igh] .key

這 里 low≤pivotpos≤high 。 應(yīng) 當(dāng) 注 意 ：pivot=R[[pivotpos] 。

2．求解。通過遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間R[low……pivotpos-1] 和 R[pivotpos＋1……h(huán)igh] 排序。

3．組合。因為當(dāng)“求解”求解步驟中的兩個遞歸調(diào)用結(jié)束時，其左、右兩個子區(qū)間已有序，所以由上面的不等式立即知道整個數(shù)組R已有序。

3 用java實現(xiàn)具體算法

4 算法分析

快速排序的時間主要耗費(fèi)在劃分操作上，對長度為 k的區(qū)間進(jìn)行劃分，共需k-1次關(guān)鍵字的比較。

1.最壞的時間復(fù)雜度

最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空（或右邊的子區(qū)間為空），而劃分所得的另一個非空的子區(qū)間中記錄數(shù)目僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。

因此，快速排序必須做n-1次劃分，第i次劃分開始時區(qū)間長度為 n-i+1,所需的比較次數(shù)為 n-i(1≤i≤n-1),故總的比較次數(shù)達(dá)到最大值：

如果按上面給出的劃分算法，每次取當(dāng)前無序區(qū)的第1個記錄為基準(zhǔn)，那么文件的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準(zhǔn)就是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，則快速排序所需的比較次數(shù)反而最多。

2.最好的時間復(fù)雜度：最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個無序子區(qū)間的長度大致相等。總的關(guān)鍵字比較次數(shù)為：O（nlgn）因為快速排序的記錄移動次數(shù)不大于比較的次數(shù)，所以快速排序的最壞時間復(fù)雜度應(yīng)為O(n2)，最好的時間復(fù)雜度為O(nlgn)。

3.平均時間復(fù)雜度：盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者，它的平均時間復(fù)雜度為O(nlgn)。

4.空間復(fù)雜度：快速排序在系統(tǒng)內(nèi)部需要一個棧來實現(xiàn)遞歸。若每次劃分較為均勻，則其遞歸樹的高度為O(lgn)，故遞歸后需?？臻g為O(lgn)。最壞情況下，遞歸樹的高度為O（n），所需的棧空間為O(n)。

5.穩(wěn)定性：快速排序是非穩(wěn)定的。

目前，隨著社會經(jīng)濟(jì)的飛速發(fā)展，要求計算機(jī)處理的信息量越來越大，在各種數(shù)據(jù)加工的過程中，如果數(shù)據(jù)能夠根據(jù)某種規(guī)則排序，就能大大提高數(shù)據(jù)處理的算法效率。

5 結(jié)束語

本文分析了快速排序的算法。在實際應(yīng)用中，若待排序的記錄數(shù)量大，記錄本身除關(guān)鍵字外的其它信息量也較大，而且對排序穩(wěn)定性要求不很高時快速排序法是較好的選擇。掌握排序的方法，可以在實際的應(yīng)用過程中提高查找的效率。

[1] “一種適合 Java環(huán)境的中文快速排序和模糊檢索方法”[J] .《電腦知識與技術(shù)》2009(7).

[2] “中文數(shù)據(jù)排序與快速檢索方法研究” [J] .《微計算機(jī)信息》2007(3).

[3] “用Java語言改進(jìn)插入排序算法” [J] .《宜賓學(xué)院學(xué)報》2006(12).

[4] “自然歸并算法的Java語言實現(xiàn)” [J] .《濮陽職業(yè)技術(shù)學(xué)院學(xué)報》2006(4).