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

　　摘要：本文基于Java平臺針對經典快速排序提出改進方案，使用歸并的思想對快速排序作了多線程優化，并對單、多線程下的快速排序進行了對比測試和分析。結果表明，通過多線程優化，快速排序在雙核主機上對5千萬個隨機整型數據進行排序的速度是單線程的1.6倍，說明了該優化方法的有效性。該方法思路直觀、容易理解，宜作為多核技術教學案例。
　　關鍵詞：快速排序；歸并；多線程
　　文章編號：1672-5913(2010)08-0149-04
　　中圖分類號：G642
　　文獻標識碼：A
　　
　　1　快速排序
　　
　　排序是計算機科學的重要內容，是計算機及相關專業的學生必須掌握的一類基礎算法。快速排序以其優異的性能成為各種排序算法中的佼佼者。在日常講授、學習以及實現快速排序算法時，大都是以單線程的模式進行。隨著多核技術的發展與普及，對快速排序作多線程優化以進一步提高排序性能，可以使學生更好地掌握多線程思想。Java是當今的主流編程語言之一，具有優秀的跨平臺性。在Java平臺上對快速排序進行多線程優化，可適用于多種軟硬件環境，應用前景廣闊。筆者首先基于Java平臺對快速排序在小數據量情況下的優化做了測試，得到了一個可行的優化方案，然后在Java中實現了歸并方式的多線程快速排序，并在不同的軟硬件環境下做了測試。測試結果表明，多線程排序能大幅提高排序的速度。
　　
　　
　　1，1算法概要
　　快速排序(Quicksort)由Hoare提出，是現今最快的內部排序算法之一，其過程主要分為三個階段：
　　(1)在待排序的序列中找出一個樞軸；……