中值排序

中值排序，最坏情况下性能为二次方，即o(n^2)，但其最好和平均性能是线性，即o(n log n)
sort(A)
    medianSort(A, 0, n-1)
end

medianSort(A, left, right)
    if(left < right) then
        find median value A[me] in A[left, right]
        mid = (right+left)/2
        swap A[mid] and A[me]
        for i=left to mid-1 do
            if(A[i] > A[mid]) then
                find A[k] <= A[mid] where k>mid  //mid位置之后,寻找元素，使A[k] <= A[mid]
                swap A[i] and A[k]
        medianSort(A, left, mid-1)
        medianSort(A, mid+1, right)
end

C实现：
数组arr：15, 9, 8, 1, 4, 11, 07, 12, 13, 06, 05, 03, 16, 02, 10, 14
int partition(void **arr,
    int(*funcCMP)(const void *, const void *),
    int nLeft, int nRight, int nPivotIndex)
{
    int nIndex = nLeft;
    int nStore = nLeft;

    void *pivot = arr[nPivotIndex];

    void *tmp = arr[nRight];
    arr[nRight] = arr[nPivotIndex];
    arr[nPivotIndex] = tmp;

    //扫描数组，小于中枢值（pivot）的，放到数组的前面
    for(nIndex=nLeft; nIndex    {
        if(0 >= funcCMP(arr[nIndex], pivot))
        {
            tmp = arr[nIndex];
            arr[nIndex] = arr[nStore];
            arr[nStore] = tmp;
            nStore++;
        }
    }

    //最后把中枢值填到nStore位置
    arr[nRight] = arr[nStore];
    arr[nStore] = pivot;
    return nStore;
}

paritition(0, 15, 9)执行返回p=5，A[left，p）中的所有元素都小于或等于中枢值（pivot）；
而A[p+1, right]中的元素都大于中枢值。选择中值元素的过程：p是在中值元素的最终位置的左侧，则p的左边没有元素会是中值（有序数组的中值）；要想获得有中值，只需反复调用partition，则返回的p等于中值的位置。（中值与中枢值是不同的概念,中值是位于有序数组中间位置，而中枢值是把数组一分为二的界值。）
partition返回中枢值的位置p，p能够用来递归在A[left， right]中检查第K个元素，对于任何1<=k<=right-left+1，有如下结论：

• 如果k=p+1，选择的中值元素是第k个值（这里的k是以1为基数的）；
• 如果k
• 如果k>p+1，A的第k个元素是A[p+1， right]的第k-p个元素。

//选项中枢值
int selectPrivoIndex(void **arr, int nLeft, int nRight);

/**
    在数组中寻找第k大元素的位置的算法，其在平均情况下为线性时间。
    A随着计算的进行不断被修改更新。注意1<= k <=right-left+1
**/
int selectKth(void **arr,
    int(*funcCmp)(const void *, const void *),
    int nLeft, int nRight, int k)
{
    int nIndex = selectPrivoIndex(arr, nLeft, nRight);
    int nPivotIndex = partition(arr, funcCmp, nLeft, nRight, nIndex);

    if(nPivotIndex > nLeft-k+1)
    {
        return selectKth(arr, funcCmp, nLeft, nPivotIndex-1, k);
    }
    else
    {
        return selectKth(arr, funcCmp, nPivotIndex+1, nRight, k-(nPivotIndex-nLeft+1));
    }
}

参考：《算法技术手册》