快速排序

    快速排序与中值排序的思想大致相同，但比中值排序简单；快速排序首先数组根据中枢值分成两个数组，左子数组的元素都小于或者等于中枢值，右子数组的元素都大于或等于中枢值，然后每个子数组被递归地排序。
    因为快速排序是递归的，可以用公式t(n) = 2*t(n/2)+O(n)，O(n)表示切分数组需要花费的线性时间，公式表现的性能为O(n log n)。
    快速排序最好情况：O(n log n)，平均情况：O(n log n)， 最坏情况：O(n^2)；在每一个递归步骤中，大小为n的数组都被切分成两个集合，如果其中一个集合为空，另外一个集合的大小为n-1，快速排序将会退化成最坏的二次方行为。
    快速排序要比中值排序快，快速排序的总开销也比较少，因为它不需要在构建子问题时寻找中值元素，并且，在快速排序每次递归的时候只需要进行一次切分操作(而中值排序需要递归地调用切分操作来寻找中值元素)

sort(A)
    quickSock(A, 0, n-1)
end

quickSort(A, left, right)
    if(left <  right) then
        pi = partition(A, left, right)
        quickSort(A, left, pi-1)
        quickSort(A, pi+1, right)
end

parition(A, left, right)
    p = select pivot in A[left, right]
    swap A[p] and A[right]
    store = left

    for i = left to right-1 do
        if(A[i] <= A[right]) then
            swap A[i] and A[store]
            store++
    
    swap A[store] and A[right]
    return store
end

C实现：

//插入排序的规模
int nMinSize = 10;
              
//插入排序函数
void SortPointers(
     void **arr,
     int(* funcCmp)(const void *, const void *),
     int nLeft, int nRight);

//当待排序的数组大小低于某个预先设定的值时，使用插入排序
void do_qsort(
     void **arr,
     int(* funcCMP)(const void *, const void *),
     int nLeft, int nRight)
{
    int nPivotIndex = 0;
    nPivotIndex = selectPrivoIndex(arr, nLeft, nRight);
    nPivotIndex = partition(arr, funcCMP, nLeft, nRight, nPivotIndex);

    if(nPivotIndex-nLeft-1 <= nMinSize)
    {
        SortPointers(arr, funcCMP, nLeft, nPivotIndex-1);
    }
    else
    {
        do_qsort(arr, funcCMP, nLeft, nPivotIndex-1);
    }

    if(nRight-nPivotIndex-1 <= nMinSize)
    {
        SortPointers(arr, funcCMP, nPivotIndex+1, nRight);
    }
    else
    {
        do_qsort(arr, funcCMP, nPivotIndex+1, nRight);
    }
}

void SortPointersQuick(
     void **arr, int nTotalElems,
     int(* funcCMP)(const void *, const void *))
{
    do_qsort(arr, funcCMP, 0, nTotalElems-1);
}

参考：《算法技术手册》