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