摘要：快速排序是冒泡排序經(jīng)改進之后的一種新的排序方法。擁有速度快，原地排序等特點，本文主要探討了對原始的快速排序的一些改進的想法，提高其效率。

關(guān)鍵詞：算法；快速排序；改進

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007—9599 （2012） 14—0000—02

一、引言

排序作為一類重要的計算機算法，經(jīng)常在程序中被使用。通過對排序的實現(xiàn)與改進可以幫助程序完成許多出色的功能。不同的排序算法有著各自的特點，其中：空間方面當(dāng)前最好的算法僅需占用一個記錄的存儲空間，而在時間方面，快速排序在同數(shù)量級排序算法中性能優(yōu)異，應(yīng)用廣泛。

二、基本原理

快速排序是基于分治模式的。對任意數(shù)組A[p..r]分治過程分為如下三步[1]：

其中q是在劃分過程中計算的

解決：對我們分解得到的兩個子數(shù)組再次通過快速排序的方法進行排序，遞歸執(zhí)行代碼。

合并：由于整個過程是就地排序（在原來的地址空間進行排序），所以遞歸進行快速排序后整個數(shù)組已達到排好序的狀態(tài)，無需多余操作。

下示偽代碼為快速排序的關(guān)鍵算法：

然后，對整個數(shù)組進行遞歸排序：

三、算法性能分析

快速排序算法運行的快慢與否與被排序的數(shù)組元素分布狀態(tài)有關(guān)，同時與我們選取哪一元素作為主元有關(guān)。

最壞情況劃分發(fā)生在劃分過程產(chǎn)生的兩個區(qū)域分別包含n—1個元素和1個元素的時候。假設(shè)劃分時間代價為θ（n），那么T（0）=θ（1），則

最佳情況為平分所要排序的數(shù)量，此時

四、方法改進

1.當(dāng)排序數(shù)量較小時

如果在r—p的數(shù)量較小情況下，仍舊進行快速排序的劃分，出現(xiàn)上述分析中的最壞情況的可能性會明顯增大，同時劃分也需要花費一些代價。此時快速排序相對于一般的排序算法，根本無法體現(xiàn)其優(yōu)勢，甚至成為程序的負累。所以我們可以考慮r—p在小于一定范圍內(nèi)時直接對所需要排序的數(shù)據(jù)使用一些其他簡單的排序算法如冒泡排序，插入排序等。這些簡單的排序算法在進行數(shù)量規(guī)模較小的數(shù)據(jù)排序時，由于其過程簡單、開銷較小，將比快速排序效率更高，更加實用。

方法：在partition（A，p，r）中插入一條語句判定

2.優(yōu)化對主元的選擇

此時可以考慮查找每次排序數(shù)組中的中值，但是這種做法可能會產(chǎn)生更大的開銷（因為假定事先對數(shù)據(jù)的構(gòu)成一無所知，查找某個條件的值會遍歷數(shù)組，開銷較大）。此時我們可以考慮隨機選取主元。可以證明一般的不平衡劃分在運用此法后對算法整體的平均影響將不會很大，可以得出期望的運行時間仍為θ（nlgn）。

3.一次增大對區(qū)間的劃分

對于輸入的數(shù)組，確定兩個支點元素A[low]和A[high]，滿足A[low]

方法：對low和high的確定可以使用雙向搜索法結(jié)合原來確定q的方法實現(xiàn)?，F(xiàn)列出偽代碼：

此種方法將只增加了一個輔助空間卻將數(shù)組分成了三個同數(shù)量級的子數(shù)組，且仍保持原地性，最后排序結(jié)束后則原數(shù)組也排序完成。圖2列出了簡單示例。

五、結(jié)束語

本文通過對快速排序進行簡單的介紹并提出了三點改進快速排序的方法，同時做了簡要的分析，可以達到增加快速排序算法性能的目的。遇到實際問題時，可以結(jié)合具體情況，運用此法進行改進，提高程序的性能。

參考文獻：

[1]（美）科曼等著，潘金貴等譯.算法導(dǎo)論（原書第2版）[M].北京：機械工業(yè)出版社，2006：85—92

[2]汪維清，羅先文，汪維華等.分組排序算法[J].計算機工程與應(yīng)用，2008，44（33）：53—56.DOI：10.3778/j.issn.1002—8331.2008.33.017.

[3]張廣路.對冒泡排序和快速排序算法的改進[J].瓊州大學(xué)學(xué)報，2005，12（5）：18—21