歸并方式的多線程快速排序算法

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