排序算法

快速排序

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

严蔚敏版数据结构解法

void quick_sort_Book(vector<int>& nums,int left,int right)
{
    if(left<=right)
    {
        int pivot=quick_sort_pivot(nums,left,right);
        quick_sort_Book(nums,left,pivot-1);
        quick_sort_Book(nums,pivot+1,right);
    }
}
int quick_sort_pivot(vector<int>& nums,int left,int right)
{
    int mid=nums[right];
    int begin=left,end=right-1;
    while(begin<end)
    {
        while(nums[begin]<mid&&begin<end) begin++;
        while(nums[end]>=mid&& begin<end) end--;
        swap(nums[begin],nums[end]);
    }
    if(nums[begin]>=nums[right])
    {
        swap(nums[begin],nums[right]);
    }
    else begin++;
    
    return begin;
}

递归

void quick_sort_recursive(vector<int>& nums,int start,int end)
    {
        if(start>=end)
        return ;
        
        int left=start,right=end-1;
        int mid=nums[end];

        while(left<right)
        {
            //从左边找一个比mid大的数
            while(nums[left]<mid&& left<right)
            left++;
            while(nums[right]>=mid&&left<right)
            right--;

            std::swap(nums[left],nums[right]);
        }

        if(nums[left]>=nums[end])
        swap(nums[left],nums[end]);
        else
        left++;
        quick_sort_recursive(nums,start,left-1);
        quick_sort_recursive(nums,left+1,end);
    }

参考

1. 快速排序