在學數據結構中排序這一章節的時候，有一道有關快速排序的作業題描述如下：

按下述要求編寫快速排序的非遞歸算法：
定義一個棧（或隊列），把整個序列的上、下界入棧（或隊列）。當棧（或隊列）非空時進行如下操作：
（1）取棧頂（或隊頭）元素作為序列的上、下界，在區間的頭部、中間、尾部取關鍵字居中的元素作為中樞元素，進行一趟快速排序；
（2）在一趟排序過程中，如果子表已有序(沒有發生元素交換)，則該子序列排序結束，否則先對劃分出的長度較短的子表進行排序，且將另一子表的上、下界入棧（或隊列）保存；
（3）若待排序區間中數據元素數小于等于3，則不再進行分割，而是直接進行比較完成排序。
完成算法實現后，用大數據量進行測試，同原有快速排序算法在時間上進行對比分析。

這道題本質上是在優化快速排序。

1.用棧代替遞歸

函數的遞歸本身就利用了堆棧，用棧改寫遞歸算法為非遞歸是常用思路。我們可以將序列的上下界入棧，排序時再取棧頂元素并出棧，本題中要求先對劃分出的長度較短的子表進行排序，那么我們就先入棧較長的子表，將較短的子表后入棧以便下次循環中優先出棧。(部分)代碼如下：

SeqStack<int> s;
while( !s.isEmpty())  //棧非空且未排好序{//得到某分區的左右邊界int r;s.getTop(r);s.pop();int l;s.getTop(l);s.pop();boundary = Part(a, l, r, Flag);  //boundary為樞軸元素所在位置if( boundary - l < r - boundary)    ///如果左分區比右分區短{if( boundary + 1 < r ) //判斷右分區是否存在{s.push(boundary + 1);s.push(r);}if( boundary - 1 > l ) //判斷左分區是否存在{//將左分區端點后入棧以便優先排序s.push(l);s.push(boundary - 1);}}else                                       //如果右分區比左分區短{if( boundary - 1 > l ) //判斷左分區是否存在{s.push(l);s.push(boundary - 1);}if( boundary + 1 < r ) //判斷右分區是否存在{///將右分區端點后入棧以便優先排序s.push(boundary + 1);s.push(r);}}}

2.中樞元素的取法

一般書本上的快速排序是取第一個待排序的元素作為中樞元素，而為了優化快速排序算法，如果能夠盡量將中樞元素取在整個待排序數組的中位數附近，那么兩個子表的長度就會接近，這樣一來就減少了時間復雜度，優化了快速排序算法，本題中采取的方法是：在區間的頭部、中間、尾部取關鍵字居中的元素作為中樞元素。其實我們也可以平均取五個點、七個點來找居中的元素。（頭中尾取中值）代碼如下：

int Mid(int first, int mid, int last)
//求頭，中，尾中關鍵字居中的元素
{if ((first>=mid&&first<=last)||(first<=mid&&first>=last))return first;else if ((mid>=first&&mid<=last)||(mid<=first&&mid>=last))return mid;elsereturn last;
}

注意，要在Partition函數中交換首元素和中樞元素的位置:

int pivot = Mid(low, (low+high)/2, high);//選擇區間的頭部、中間、尾部取關鍵字居中的元素作為中樞元素Swap(elem[pivot], elem[low]);  //保持代碼的統一性

3.在一趟排序中，如果子表已有序，則該子序列排序結束

這一點便于理解，代碼實現上可以定義一個bool類型的標記，來判斷Partition中是否發生過元素交換，如果沒有交換bool賦true。

4.待排區間中元素數<=3，則不再進行分割，則直接比較排序

快速排序是適用于大數據量的排序方式，在數據量比較小的時候，使用插入排序或者選擇排序較好，所以很多實用的排序算法使用快排+插排的方式排序。本題中要求：若待排序區間中數據元素數小于等于3，則不再進行分割，而是直接進行比較完成排序，代碼如下：

void JustSort(int a[], int left, int right)
//數組元素小于等于3時的直接比較排序
{if(right-left==1)         //序列只有兩個元素時{if(a[left] > a[right]){Swap(a[left], a[right]);}}else                      //三個元素時{if(a[left] > a[left+1])Swap(a[left], a[left+1]);if(a[left+1] > a[right])Swap(a[left+1], a[right]);if(a[left] > a[left+1])Swap(a[left], a[left+1]);}
}

應用以上優化方法后，用50000個隨機元素的數組進行排序，與書本上的遞歸快排進行時間比較，如下：



可見有一定的優化效果。

全部代碼如下：

#ifndef __ExQUICKSORT_H__
#define __ExQUICKSORT_H__
#include "SeqStack.h"int Mid(int first, int mid, int last)
///求頭，中，尾中關鍵字居中的元素
{if ((first>=mid&&first<=last)||(first<=mid&&first>=last))return first;else if ((mid>=first&&mid<=last)||(mid<=first&&mid>=last))return mid;elsereturn last;
}int Part(int elem[], int low, int high, int &flag)  ///參數flag用以判斷是否已經有序，以便結束排序
//原快速排序算法中的劃分部分，寫成函數方便循環調用
{int pivot = Mid(low, (low+high)/2, high);//選擇區間的頭部、中間、尾部取關鍵字居中的元素作為中樞元素Swap(elem[pivot], elem[low]);   /// 交換樞軸元素和首元素的位置，保持代碼的統一性int e = elem[low];				// 取樞軸元素int i = low, j = high;while (i < j){while (i < j && elem[j] >= e)	// 使j右邊的元素不小于樞軸元素j--;if (i < j){elem[i++] = elem[j];flag = 1;}while (i < j && elem[i] <= e)	// 使i左邊的元素不大于樞軸元素i++;if (i < j){elem[j--] = elem[i];flag = 1;}}elem[i] = e;return i;                           //返回樞軸元素位置
}void JustSort(int a[], int left, int right)
///數組元素小于等于3時的直接比較排序
{if(right-left==1)         //序列只有兩個元素時{if(a[left] > a[right]){Swap(a[left], a[right]);}}else                      //三個元素時{if(a[left] > a[left+1])Swap(a[left], a[left+1]);if(a[left+1] > a[right])Swap(a[left+1], a[right]);if(a[left] > a[left+1])Swap(a[left], a[left+1]);}
}template <class ElemType>
void ExQuickSort(ElemType a[], int left, int right)
// 操作結果:對數組elem[low .. high]中的元素進行快速排序
{int Flag = 0;             ///標記，用來判斷是否已經排好序(未發生過交換)SeqStack<int> s;if( left<right ){if(right-left < 3)   //如果序列小于等于3個元素{JustSort(a, left, right);return ;}int boundary = Part(a, left, right, Flag);   //劃分后的中樞所在位置if(Flag == 0)return ;if( boundary - left < right - boundary)    ///如果左分區比右分區短{if( boundary + 1 < right ) //判斷右分區是否存在{s.push(boundary + 1);s.push(right);}if( boundary - 1 > left ) //判斷左分區是否存在{///將左分區端點后入棧以便優先排序s.push(left);s.push(boundary - 1);}}else                                       ///如果右分區比左分區短{if( boundary - 1 > left ) //判斷左分區是否存在{s.push(left);s.push(boundary - 1);}if( boundary + 1 < right ) //判斷右分區是否存在{///將右分區端點后入棧以便優先排序s.push(boundary + 1);s.push(right);}}while( !s.isEmpty())  //棧非空且未排好序{//得到某分區的左右邊界int r;s.getTop(r);s.pop();int l;s.getTop(l);s.pop();boundary = Part(a, l, r, Flag);  //boundary為樞軸元素所在位置if(Flag == 0)        ///如果已經有序，結束排序。return ;if(right-left < 3)   //如果序列小于等于3個元素{JustSort(a, left, right);return ;}if( boundary - l < r - boundary)    ///如果左分區比右分區短{if( boundary + 1 < r ) //判斷右分區是否存在{s.push(boundary + 1);s.push(r);}if( boundary - 1 > l ) //判斷左分區是否存在{///將左分區端點后入棧以便優先排序s.push(l);s.push(boundary - 1);}}else                                       ///如果右分區比左分區短{if( boundary - 1 > l ) //判斷左分區是否存在{s.push(l);s.push(boundary - 1);}if( boundary + 1 < r ) //判斷右分區是否存在{///將右分區端點后入棧以便優先排序s.push(boundary + 1);s.push(r);}}}}
}#endif // __ExQUICKSORT_H__