quick sort(重复数版)

针对数组中有大量重复数优化

example

// 1,3,4,7,7,7,17,11,1,7

void QuickSort(int* arr, int from, int to);
void QSort(int* arr, int size);

void QuickSort(int* arr, int from, int to)
{
    if(from >= to)    return;
    int pivot = arr[to];
    // save the numbers of who's value equals pivot
    int numsOfPivot = 0;
    int border = from;
//                b     i
//    1,3,4,7,7,7,17,11,1,7
    for(int i = from; i <= to; i++)
    {
        if(arr[i] < pivot)
        {
            int temp = arr[i];
            arr[i] = arr[border];
            arr[border - numsOfPivot] = temp;
            ++border;
        }
        else if(arr[i] == pivot)
        {
            ++numsOfPivot;
            arr[i] = arr[border];
            ++border;
        }
    }
    // refill the duplicate of pivot at the behind of border
    while(numsOfPivot != 0)
    {
        arr[border-numsOfPivot] = pivot;
        --numsOfPivot;
    }
    QuickSort(arr,from,border-2-numsOfPivot);
    QuickSort(arr,border,to);
}

void QSort(int* arr, int size)
{
    QuickSort(arr, 0, size-1);
}