【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
快速排序是編程中經常使用到的一種排序方法。可是很多朋友對快速排序有畏難情緒，認為快速排序使用到了遞歸，是一種非常復雜的程序，其實未必如此。只要我們使用好了方法，就可以自己實現快速排序。
首先，我們復習一下，快速排序的基本步驟是什麼：
1、 判斷輸入參數的合法性
2、把數組的第一個數據作為比較的原點，比該數據小的數據排列在左邊，比該數據大的數據排列在右邊
3、按照（2）的方法分別對左邊的數組和右邊的數據進行和（2）一樣的數據排列
那麼實際編寫代碼中，應該怎麼做呢？
a）首先，判斷數據的合法性？
void quick_sort(int array[], int length)
{
int median = 0;
if(NULL == array || 0 == length)
return;
_quick_sort(array, 0, length -1);
}
void quick_sort(int array[], int length)
{
int median = 0;
if(NULL == array || 0 == length)
return;
_quick_sort(array, 0, length -1);
}
b）尋找中間數，分別對左邊和右邊的數據進行排序
void _quick_sort(int array[], int start, int end)
{
int middle;
if(start >= end)
return;
middle = get_middle(array, start, end);
_quick_sort(array, start, middle -1);
_quick_sort(array, middle + 1, end);
}
void quick_sort(int array[], int length)
{
int median = 0;
if(NULL == array || 0 == length)
return;
_quick_sort(array, 0, length-1);
}
void _quick_sort(int array[], int start, int end)
{
int middle;
if(start >= end)
return;
middle = get_middle(array, start, end);
_quick_sort(array, start, middle -1);
_quick_sort(array, middle + 1, end);
}
void quick_sort(int array[], int length)
{
int median = 0;
if(NULL == array || 0 == length)
return;
_quick_sort(array, 0, length-1);
} c）那麼這裡的中間數應該怎麼安排呢？
int get_middle(int array[], int start, int end)
{
int front = 0;
int tail = end - start;
int value = array[start];
int length = end - start + 1;
int loop = start + 1;
while(loop <= end){
if(array[loop] < value){
gQuickSort[front] = array[loop];
front ++;
}else{
gQuickSort[tail] = array[loop];
tail --;
}
loop ++;
}
gQuickSort[front] = value;
memmove(&array[start], gQuickSort, sizeof(int) * (length));
return start + front ;
}
int get_middle(int array[], int start, int end)
{
int front = 0;
int tail = end - start;
int value = array[start];
int length = end - start + 1;
int loop = start + 1;
while(loop <= end){
if(array[loop] < value){
gQuickSort[front] = array[loop];
front ++;
}else{
gQuickSort[tail] = array[loop];
tail --;
}
loop ++;
}
gQuickSort[front] = value;
memmove(&array[start], gQuickSort, sizeof(int) * (length));
return start + front ;
}
注意：這裡gQuickSort是一個全局數組，主要是為了作為排序的臨時數組使用，實際環境中大家可以靈活運用各種方法。
d）基本的快速排序就完成了，那我們怎麼測試呢？我們可以編寫幾個簡單的測試用例？
static void test1()
{
int array[] = {1};
quick_sort(array, sizeof(array)/sizeof(int));
}
static void test2()
{
int array[] = {2, 1};
quick_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
}
static void test3()
{
int array[] = {4, 3, 2,1};
quick_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
assert(4 == array[3]);
}
static void test4()
{
int array[] = {3, 2, 1};
quick_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
