快速排序一步一步优化

int Median(int *a,int left,int right){
    int midIndex = (left + right)>>1;
    if (a[left] > a[midIndex])
    {
        swap(a[left],a[midIndex]);
    }
    if (a[left] > a[right])
    {
        swap(a[left],a[right]);
    }
    if (a[midIndex] > a[right])
    {
        swap(a[midIndex],a[right]);
    }
    swap(a[midIndex],a[right-1]);
    return a[right-1]; //返回中轴
}

void qSort(int *a,int left,int right){
        //如果需要排序的数据大于3个则使用快速排序
        if (right - left >=3)
        {
            int midIndex = Median(a,left,right);
            int begin = left;
            int end = right - 1;
            while (true){
                while(a[++begin] < midIndex);
                while(a[--end]<midIndex);
                if (begin < end)
                {
                    swap(a[begin],a[end]);
                }
                else{
                    swap(a[begin],a[right -1]);//将枢轴移动到何时位置
                    break;
                }
            }
            qSort(a,left,begin -1);
            qSort(a,begin + 1,right);
        }
        else{
            BubbleSort(a,left,right);//当数据小于3个,直接用冒泡排序
        }//当要排序的数据很少时（小于3个），则不能进行三数取中值，此时直接使用简单的排序（例如冒泡）即可，而且从效率的角度来考虑这也是合理的，因为可以避免函数调用的开销。
    }

if (high - low + 1 < 10)  
{  
    InsertSort(arr,low,high);  
    return;  
}//else时，正常执行快排  

void QSort(int arr[],int low,int high)  //三数中值+聚集相等元素
{
    int first = low;
    int last = high;

    int left = low;
    int right = high;

    int leftLen = 0;
    int rightLen = 0;

    if (high - low + 1 < 10)
    {
        InsertSort(arr,low,high);
        return;
    }
    
    //一次分割
    int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴
        
    while(low < high)
    {
        while(high > low && arr[high] >= key)
        {
            if (arr[high] == key)//处理相等元素
            {
                swap(arr[right],arr[high]);
                right--;
                rightLen++;
            }
            high--;
        }
        arr[low] = arr[high];
        while(high > low && arr[low] <= key)
        {
            if (arr[low] == key)
            {
                swap(arr[left],arr[low]);
                left++;
                leftLen++;
            }
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = key;

    //一次快排结束
    //把与枢轴key相同的元素移到枢轴最终位置周围
    int i = low - 1;
    int j = first;
    while(j < left && arr[i] != key)
    {
        swap(arr[i],arr[j]);
        i--;
        j++;
    }
    i = low + 1;
    j = last;
    while(j > right && arr[i] != key)
    {
        swap(arr[i],arr[j]);
        i++;
        j--;
    }
    QSort(arr,first,low - 1 - leftLen);
    QSort(arr,low + 1 + rightLen,last);
}

void QSort(int arr[],int low,int high)  
{   
    int pivotPos = -1;  
    if (high - low + 1 < 10)  
    {  
        InsertSort(arr,low,high);  
        return;  
    }  
    while(low < high)  
    {  
        pivotPos = Partition(arr,low,high);  
        QSort(arr,low,pivot-1);  
        low = pivot + 1;  
    }  
}