摘要：本文基于Java平臺針對經(jīng)典快速排序提出改進方案，使用歸并的思想對快速排序作了多線程優(yōu)化，并對單、多線程下的快速排序進行了對比測試和分析。結(jié)果表明，通過多線程優(yōu)化，快速排序在雙核主機上對5千萬個隨機整型數(shù)據(jù)進行排序的速度是單線程的1.6倍，說明了該優(yōu)化方法的有效性。該方法思路直觀、容易理解，宜作為多核技術(shù)教學案例。
　　關(guān)鍵詞：快速排序；歸并；多線程
　　文章編號：1672-5913(2010)08-0149-04
　　中圖分類號：G642
　　文獻標識碼：A
　　
　　1　快速排序
　　
　　排序是計算機科學的重要內(nèi)容，是計算機及相關(guān)專業(yè)的學生必須掌握的一類基礎(chǔ)算法?？焖倥判蛞云鋬?yōu)異的性能成為各種排序算法中的佼佼者。在日常講授、學習以及實現(xiàn)快速排序算法時，大都是以單線程的模式進行。隨著多核技術(shù)的發(fā)展與普及，對快速排序作多線程優(yōu)化以進一步提高排序性能，可以使學生更好地掌握多線程思想。Java是當今的主流編程語言之一，具有優(yōu)秀的跨平臺性。在Java平臺上對快速排序進行多線程優(yōu)化，可適用于多種軟硬件環(huán)境，應(yīng)用前景廣闊。筆者首先基于Java平臺對快速排序在小數(shù)據(jù)量情況下的優(yōu)化做了測試，得到了一個可行的優(yōu)化方案，然后在Java中實現(xiàn)了歸并方式的多線程快速排序，并在不同的軟硬件環(huán)境下做了測試。測試結(jié)果表明，多線程排序能大幅提高排序的速度。
　　
　　
　　1，1算法概要
　　快速排序(Quicksort)由Hoare提出，是現(xiàn)今最快的內(nèi)部排序算法之一，其過程主要分為三個階段：
　　(1)在待排序的序列中找出一個樞軸；
　　(2)根據(jù)樞軸將待排序的序列劃分成兩個不相交的子序列，其中一個子序列里的關(guān)鍵字全部不小于樞軸，另一個子序列里的關(guān)鍵字全部不大于樞軸；
　　(3)分別對兩個子序列遞歸進行快速排序，直到劃分出的子序列的長度為1。
　　
　　1，2改進
　　快速排序的平均性能非常優(yōu)秀，但是在最壞情況下，即序列已基本有序或是基本逆序時，快速排序的性能會變得非常低。而且由于采用遞歸來進行排序，當序列的長度較小時，頻繁的遞歸操作也會影響排序的性能。許多文獻對快速排序的改進提出了建議。Singleton在文獻中使用“三點取中”方法，用序列中的頭、尾和中點這三個關(guān)鍵字的中間值作為樞軸，有效地避免了快速排序在最壞情況下的性能惡化。在內(nèi)存使用上，快速排序需要使用額外的?？臻g來進行遞歸操作。為減小棧的深度，在通過劃分之后得到的子序列中，應(yīng)優(yōu)先對較小的子序列遞歸進行排序。另外，快速排序的遞歸操作在序列長度較小時會影響排序的效率，應(yīng)該使用其他非遞歸算法來處理小序列。
　　
　　對小序列進行處理時，使用直接插入排序是有效的改進方法。此處通過測試來尋找從快速排序切換到插入排序的時機，為此設(shè)置一個閾值M，當快速排序過程中劃分出的子序列的長度小于或等于M時，不再遞歸調(diào)用快速排序而使用直接插入排序，以避免對小序列排序時的頻繁遞歸。這里M值的選取非常重要，會對排序的速度產(chǎn)生較大的影響。因為當M值偏小時，相當于沒有做改進；如果M值偏大，則無法體現(xiàn)快速排序的優(yōu)勢。M值的選取與計算機軟硬件因素相關(guān)，這里對M選取了一組值f4，8，16，32，64，128，256}在Java平臺下做測試，令M分別取這些值來對一個長度為