簡單實用的c++快速排序模闆類

 （一）目标

在實際問題的解決過程中，我們發現，很多問題都可以歸結為對資料的排序和查詢。而查詢的效率則在很大程度上依賴于排序的效率；尤其是在資料量達到海量級的時候。是以，設計一個有效的排序算法是至關重要的。本文設計了一個通用的c++ quicksort 模闆類。通過簡單的提供一個Data類，可以實作任意資料的快速排序算法，提高了開發效率。

（二）快速排序算法的思想

最基本的快速排序的思想是基于分治政策的：

對于輸入的子序列L[p..r]，如果規模足夠小則直接進行排序，否則分三步處理：

1 分解(Divide)：将輸入的序列L[p..r]劃分成兩個非空子序列L[p..q]和L[q+1..r]， 使L[p..q]中任一進制素的值不大于L[q+1..r]中任一進制素的值。

2 遞歸求解(Conquer)：通過遞歸調用快速排序算法分别對L[p..q]和L[q+1..r]進行排序。

3 合并(Merge)：由于對分解出的兩個子序列的排序是就地進行的， 是以在L[p..q]和L[q+1..r]都排好序後不需要執行任何計算L[p..r]就已排好序。

（三）準備工作和源代碼

1 使用vc6建立console工程

2 加入下面的模闆類：

　　 

　　 // 切分資料為左右兩個部分，傳回中間元素x的編号

　　 // 主要的過程就是：選擇一個元素x作為分界點，将比x大的元素放到x右邊，其餘放到x左邊。

　　

　　以上就實作了快速排序的模闆類。

　　3 資料類接口的實作

　　從上面模闆類的實作我們可以看出，為了使用這個模闆類對某種類型的資料數組DataType * data進行排序，我們必須實作DataType的接口CompareTo（比較兩個DataType 元素a,b的大小，a>b傳回1，a==b傳回0，否則傳回-1）。

　　舉個例子來說：現在要排序二維點坐标，定義大小關系是：先比較x軸坐标值大小，x相同的話，由y值大小決定大小關系。即：(1,1) == (1,1) , (2,1) > (1, 10) , (3, 5) < (4, 1)。

　　此外：還必須實作DataType類型的無參數的預設構造函數（因為模闆類中要使用）。

　　定義資料類型MyPoint如下：

　　（四）測試

　　下面是用于測試的主函數：

　　結果輸出如下:

　　before quicksort:

　　0 <-------> (1,1)

　　1 <-------> (2,5)

　　2 <-------> (7,11)

　　3 <-------> (100,2)

　　4 <-------> (1,7)

　　5 <-------> (9,32)

　　6 <-------> (7,1)

　　7 <-------> (2,2)

　　8 <-------> (1,1)

　　9 <-------> (9,5)

　　after quicksort:

　　1 <-------> (1,1)

　　2 <-------> (1,7)

　　3 <-------> (2,2)

　　4 <-------> (2,5)

　　5 <-------> (7,1)

　　6 <-------> (7,11)

　　7 <-------> (9,5)

　　8 <-------> (9,32)

　　9 <-------> (100,2)

　　請按任意鍵繼續 . . .

　　（五）說明

　　本文根據快速排序算法，實作了一個c++快速排序模闆類。使用這個模闆類，并遵守欲排序資料類型必須實作的接口定義，就能實作對任意資料類型的快速排序。當然，本文的例子隻是一個基本的引導。

本文轉自yonghu86 51CTO部落格，原文連結：http://blog.51cto.com/yonghu/1321405，如需轉載請自行聯系原作者