快速排序又稱分劃交換排序，其設計方法與合并排序不同。其分解方法是：在待排序的序列中選擇一個元素作為分劃元素，稱之為主元。在經過一趟特殊分劃規則處理后，分劃元素左側元素都不大于主元，右側元素都不小于主元，此過程被稱為一次分劃操作。一次劃分后，原序列被劃分為兩個待排序的子序列，在將兩個子序列排序后合并成一個序列，則其為排序完成的序列。

    快速排序算法中，使用分劃操作將一個問題分解為兩個獨立的子問題。當子序列為空或有一個元素時，被認為自問題足夠小。因為空序列或者只有一個元素的子序列不需要進行任何處理自然是有序的，所以能夠被認為足夠小。而快速排序算法在子問題足夠小時，根據算法本身的主元的性質，在左側的自然是小的，在右側的自然是大的，所以快速排序在合并時很容易。 只需要將原有的子序列按分治的順序合并即可。

    合并排序和分治排序都運用了分治策略，合并排序分解方法十分簡單，只需將原數列一分為二即可，但合并時需要調用merge函數合并，而快速排序分解方法相對困難，但合并十分簡單。這是合并排序和快速排序的不同。

    下面介紹快速排序的關鍵——分劃操作。一次分劃操作可以劃分四步：第一步先定義兩個下標變量，i自左向右移動，j自右向左移動，i初始指向數列的最左元素，j指向數列的最右元素，移動i下標直至遇到一個元素不小于主元，i下標停止移動并指向該元素；第二步移動j 下標直至遇到一個不大于主元的函數；第三步交換i和j所指的元素；第四步，重復以上操作直至i>=j，將主元和j下標指向的元素對調即可。以上為一次分劃操作的執行過程。注意i和j的大小判斷在對應元素交換之前，最后一次的i>=j時，所指元素是不需要對調的，若主元最大，則最后一位元素與主元對調。以下以一段數組演示過程。

以72 26 27 88 42 80 72 48 60 +∞為例：

第一步 ：i移至88處   j移至60處 此時i<j 交換對應元素 此時數組為 72 26 27 60 42 80 72 48 88  +∞

第二步： i移至80處   j移至48處 此時i<j 交換對應元素 此時數組為 72 26 27 60 42 48 7280 88  +∞

第三步： i移至72處   j移至72處 此時i>=j 將主元和j指向元素對調   此時元素為  72 26 57 60 42 48 72  80 88 +∞

此為一次分劃操作。

    以下為一次分劃函數的代碼：

template <class T>int SortableList<T>::Partition(int left, int right){	int i = left, j = right + 1;//i指向左側，j指向右側以正無窮防止越界 	do	{		do i ++; while(a[i] < a[left]); //找到不小于主元的數 		do j --;	while(a[j] > a[left]);//找到不大于主元的數 		if(i < j)			Swap(a[i], a[j]);//i下標小于j下標時 交換兩個元素 	}while(i < j);	Swap(a[left], a[j]);  //交換主元和j下標指向的元素 	return j;} 快速排序主體函數：
template <class T>void SortableList<T>::QuickSort(int left, int right){	if(left < right) //當遞歸至最底層子序列只剩最后一個元素時退出 此時數組已排列完成 	{		int j = RPartition(left, right);//j指向的元素 		QuickSort(left, j - 1);//左側排序 		QuickSort(j + 1, right);//右側排序 	}}    快速排序算法還可以進行改進，因為當以第一個元素為主元時，此時若數列為遞增或者遞減數列，此時會出現時間效率最低的情況。此時采用隨機選取元素作為主元或者選取中間元素作為主元的方法。筆者選擇的隨機選擇元素作為主元的方法。
 快速排序在數組元素個數下降到一定程度時，效率反而不如普通的直接插入法。所以可以選擇在子數列元素小于10（舉例）時采用直接插入法提高效率。
 以下為整體代碼：
#include <iostream>#include <cstdlib>#include <ctime>using namespace std;void Swap(int &a, int &b){	int t = a;	a = b;	b = t;}template <class T>class SortableList{	public:		SortableList(int m)		{			n = m;		}		void QuickSort();		void Input();		void Init();		void Output();	PRivate:		int RPartition(int left, int right);		int Partition(int left, int right);		void QuickSort(int left, int right);		T l[1000];//輸入的數組值		T a[1000];//實際排序對象		int n;};template<class T>void SortableList<T>::Input(){	for(int i = 0; i < n; i++)		cin >> l[i];}//Init()函數的作用是在兩路合并排序結束后將序列恢復到初始序列//再進行快速排序template<class T>void SortableList<T>::Init(){	for(int i =0; i < n; i++)		a[i] = l[i];}template<class T>void SortableList<T>::Output(){	for(int i = 0; i < n; i++)		cout << a[i] << " ";	cout << endl << endl;}//快速排序template <class T>int SortableList<T>::RPartition(int left, int right){	srand((unsigned)time(NULL));	int i = rand() % (right - left) + left;//以上下界中間的一個隨機元素作為主元 	Swap(a[i], a[left]);	return Partition(left, right);}template <class T>int SortableList<T>::Partition(int left, int right){	int i = left, j = right + 1;//i指向左側，j指向右側以正無窮防止越界 	do	{		do i ++; while(a[i] < a[left]); //找到不小于主元的數 		do j --;	while(a[j] > a[left]);//找到不大于主元的數 		if(i < j)			Swap(a[i], a[j]);//i下標小于j下標時 交換兩個元素 	}while(i < j);	Swap(a[left], a[j]);  //交換主元和j下標指向的元素 	return j;}template <class T>void SortableList<T>::QuickSort(int left, int right){	if(left < right) //當遞歸至最底層子序列只剩最后一個元素時退出 此時數組已排列完成 	{		int j = RPartition(left, right);//j指向的元素 		QuickSort(left, j - 1);//左側排序 		QuickSort(j + 1, right);//右側排序 	}}template<class T>void SortableList<T>::QuickSort(){	QuickSort(0, n - 1);}int main(){	int m;	cout << "數組長度n: ";	cin >> m;	SortableList<int> List(m);	cout << "輸入" << m << "個數字:" << endl;	List.Input();	List.Init();//恢復初始狀態	cout << "快速排序后：" << endl;	List.QuickSort();	List.Output();	return 0;}