快速排序

• 分而治之
• 主元的选择：low、中间
• 子集的划分：
  不藏/记录主元：交换
  藏主元：左右分别前进，后交换/替换
• 问题：递归（尾递归改进）、小规模数据（设置比较数据个数的阈值）、不稳定
• 复杂度

  //快速排序（从小到大）
  void quickSort(vector<int>& arr,int left, int right)
  {
        if(left >= right) return;
        if(left < 0 || right >= arr.size())
    {
        cout << "error args! array bound." << endl;
        return;
    }//非法输入判断,防止数组越界
        if(Cutoff<=right-left)
        {
        int i, j, base, temp;
        i = left, j = right;
            /**优化base的取值：left,right,mid中间的数
            int mid=left+(right-left)/2;
            if(arr[mid]>arr[left]) swap((arr[mid],arr[left]);
            if(arr[left]>arr[right]) swap((arr[left],arr[right]);
            if(arr[mid]>arr[right]) swap((arr[mid],arr[right]);//left为中间值
            **/
        base = arr[left];  //取最左边的数为基准数
        while (i < j)
        {
        while (arr[j] >= base && i < j) j--;
        while (arr[i] <= base && i < j) i++;
        if(i < j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
                else break;
        }
        //基准数归位
        arr[left] = arr[i];
        arr[i] = base;
        quickSort(arr,left, i - 1);//递归左边
        quickSort(arr,i + 1, right);//递归右边
            //这一句可以优化为尾递归：left=i+1;
        }
        else //进行直接插入排序
  }
  
  

int partition(vector<int> &nums,int l,int h)
{
int pivot=nums[l];
while(l<h)
{
while(l<h && nums[h]>=pivot) --h;
nums[l]=nums[h];
while(l<h && nums[l]<=pivot) ++l;
nums[h]=nums[l];
}
}</int>

void quicksort(vector<int> &nums,int l,int r)
{
if(l<r)
{
int pos=partition(nums,l,r);
quicksort(nums,l,pos);
quicksort(nums,pos+1,r);
}
else return;
}</int>