快速排序，快速排序算法

快速排序，快速排序算法

　　快速排序基本思想是，一趟排序，選擇一個元素作為樞軸，然後將所有比樞軸小的元素放到樞軸的左邊，將比樞軸大的元素放到樞軸的右邊，這樣的一趟排序也稱為一次劃分。然後對該樞軸劃分的左右子序列分別再進行劃分，如此遞歸。就平均時間而言，快速排序是目前被認為是最好的一種內部排序方法，其平均時間是O(nlogn)，最壞情況是O(n2)（是n方），最壞的情況就是如下倒序完後再正序排的情況。

　　C++代碼如下：

#include "stdafx.h"

#define MAXSIZE 20

typedef struct{
    int r[MAXSIZE+1];
    int len;
}SqList;

int Partition(SqList &L, int low, int high)
{
    L.r[0] = L.r[low]; // 以第一個元素作為樞軸
    int pivotkey = L.r[low];// 記錄樞軸關鍵字
    while (low < high)
    {
        while(low<high && L.r[high]>=pivotkey) 
　　　　　　--high;// 找到從high位置開始向前第一個比樞軸小的元素
        L.r[low] = L.r[high];// 將找到的比樞軸小的元素放到前邊的空閒位置
        while(low<high && L.r[low]<=pivotkey) 
　　　　　　++low;// 找到從low位置開始向後第一個比樞軸大的元素
        L.r[high] = L.r[low];// 將找到的比樞軸大的元素放到後邊的空閒位置
    }
    L.r[low] = L.r[0];// 將樞軸放回中間的空閒位置

    return low;
}

void QSort(SqList &L, int low, int high)
{
    if (low < high)
    {
        int pivotloc = Partition(L, low, high);
        QSort(L, low, pivotloc-1);
        QSort(L, pivotloc+1, high);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    SqList sqList;
    for (int i=1; i<MAXSIZE+1; i++)
    {
        sqList.r[i] = MAXSIZE - i;
    }
    sqList.len = MAXSIZE;

    QSort(sqList, 1, sqList.len);

    return 0;
}

// 附一次劃分過程，第一行為index，第二行為待排序序列
// 0   1   2   3   4   5   6   7  
// __  49  38  65  97  76  13  27  // 開始時，0號位空閒(low:1, high:7)
// 49  __  38  65  97  76  13  27  // 將第1號元素作為樞軸，放到0號位，1號位冗余(low:1, high:7)
// 49  27  38  65  97  76  13  __  // 發現27比49小，將7號位值放到1號位，7號位冗余(low:1, high:7)
// 49  27  38  __  97  76  13  65  // 發現65比49大，將3號位值放到7號位，3號位冗余(low:3, high:7)
// 49  27  38  13  97  76  __  65  // 發現13比49小，將6號位值放到3號位，6號位冗余(low:3, high:6)
// 49  27  38  13  __  76  97  65  // 發現97比49大，將4號位值放到6號位，4號位冗余(low:4, high:5)
// __  27  38  13  49  76  97  65  // low == high，將樞軸放到4號位，此時49左邊的都比49小，右邊的都比49大