淺談快速排序算法的改進(jìn)

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007—9599 （2012） 14—0000—02

一、引言

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

二、基本原理

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

其中q是在劃分過(guò)程中計(jì)算的

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

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

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

然后，對(duì)整個(gè)數(shù)組進(jìn)行遞歸排序：

三、算法性能分析

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

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

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

四、方法改進(jìn)

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

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

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

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

此時(shí)可以考慮查找每次排序數(shù)組中的中值，但是這種做法可能會(huì)產(chǎn)生更大的開(kāi)銷（因?yàn)榧俣ㄊ孪葘?duì)數(shù)據(jù)的構(gòu)成一無(wú)所知，查找某個(gè)條件的值會(huì)遍歷數(shù)組，開(kāi)銷較大）。此時(shí)我們可以考慮隨機(jī)選取主元?？梢宰C明一般的不平衡劃分在運(yùn)用此法后對(duì)算法整體的平均影響將不會(huì)很大，可以得出期望的運(yùn)行時(shí)間仍為θ（nlgn）。

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

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

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

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

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

本文通過(guò)對(duì)快速排序進(jìn)行簡(jiǎn)單的介紹并提出了三點(diǎn)改進(jìn)快速排序的方法，同時(shí)做了簡(jiǎn)要的分析，可以達(dá)到增加快速排序算法性能的目的。遇到實(shí)際問(wèn)題時(shí)，可以結(jié)合具體情況，運(yùn)用此法進(jìn)行改進(jìn)，提高程序的性能。

參考文獻(xiàn)：

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

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

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