改进版快速排序（quicksort）算法技巧

int pval = arr[left];

int pval = arr[rand()%(right-left)+left];

void selectmedianofthree(int *arr, size_t left, size_t right) 
{
    size_t mid = left + (right - left)/2;  //中部数据的下标
    if(arr[mid]>arr[right])
    {
            swap(arr[mid],arr[right]);
    }
    if(arr[left]>arr[right])
    {
            swap(arr[left],arr[right]);
    }
    if(arr[mid]>arr[left])
    {
            swap(arr[mid],arr[left]);  //把中间大小的数值放到首位，取为基准
    }
}

 if(left >= right)
 {
        return;
 }
 else if(right-left > 0 && right-left < 20)  
//数组长度较小时，调用希尔排序，减少调用快排
 {
        size_t len = right - left + 1;
        shellsort(len, &arr[left]); //数组首地址为&arr[left]
 }
 else
 {
          qsort(****);
 }

void partion(int *arr, size_t left, size_t right, size_t &lessPnum, size_t &largePnum)//数据分段
{
    selectmedianofthree(arr,left,right);  //找出中间大小的哨兵，让分段尽量均匀，提高效率
    int pval = arr[left];  //中间大小的数赋值给哨兵
    int *temp = new int [right-left+1];  //开辟堆空间存放临时数组
    int tempLindex=0, tempRindex = right-left;  //临时数组的首末位下标
    for(int i = left+1; i <= right; ++i)
    {
        if(pval > arr[i]) //比哨兵小的放在左边，从左边首位往中间写入，记录下比哨兵小的有多少个
        {
            temp[tempLindex++] = arr[i];
            ++lessPnum;
        }
        if(pval < arr[i])  比哨兵大的放在右边，从右边末位中间写入，记录下比哨兵大的有多少个
        {
            temp[tempRindex--] = arr[i];
            largePnum++;
        }
    }
    for( ; tempLindex <= tempRindex; ++tempLindex)
    //中间还未被写入的位置，写入哨兵（哨兵可能是多个相同的值）
    {
        temp[tempLindex] = pval;
    }
    for(int i = left, j=0; i <= right; ++i)
    {
        arr[i] = temp[j++]; //把分好段的数组写回原数组{ [小于哨兵的], [等于哨兵的], [大于哨兵的] }
    }
    delete [] temp; //释放临时数组
    temp = NULL;  //指针置空
}