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

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