快速排序是編程中經(jīng)常使用到的一種排序方法?？墒呛芏嗯笥褜?duì)快速排序有畏難情緒，認(rèn)為快速排序使用到了遞歸，是一種非常復(fù)雜的程序，其實(shí)未必如此。只要我們使用好了方法，就可以自己實(shí)現(xiàn)快速排序。

首先，我們復(fù)習(xí)一下，快速排序的基本步驟是什么：

1、 判斷輸入?yún)?shù)的合法性

2、把數(shù)組的第一個(gè)數(shù)據(jù)作為比較的原點(diǎn)，比該數(shù)據(jù)小的數(shù)據(jù)排列在左邊，比該數(shù)據(jù)大的數(shù)據(jù)排列在右邊

3、按照（2）的方法分別對(duì)左邊的數(shù)組和右邊的數(shù)據(jù)進(jìn)行和（2）一樣的數(shù)據(jù)排列

那么實(shí)際編寫代碼中，應(yīng)該怎么做呢？

a）首先，判斷數(shù)據(jù)的合法性？

void quick_sort(int array[], int length)
{
    int median = 0;
    if(NULL == array || 0 == length)
        return;

    _quick_sort(array, 0, length -1);
}

**b）尋找中間數(shù)，分別對(duì)左邊和右邊的數(shù)據(jù)進(jìn)行排序**

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）那么這里的中間數(shù)應(yīng)該怎么安排呢？

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是一個(gè)全局?jǐn)?shù)組，主要是為了作為排序的臨時(shí)數(shù)組使用，實(shí)際環(huán)境中大家可以靈活運(yùn)用各種方法。

d）基本的快速排序就完成了，那我們?cè)趺礈y試呢？我們可以編寫幾個(gè)簡單的測試用例？

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]);
}