【快速排序】思想及代码实现-基于C++

一、思想

1、基本思想：基于 交换 的高效排序算法，采用了 分治法 的思想。

2、算法描述：

• 从数列中取出一个数作为基准数（pivot，一般取数组第一个元素）；
• 把数组进行左右划分(partition)，大于基准数的元素都移至枢轴右边，小于等于基准数的元素都移至枢轴左边；
• 再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素，排序完成。

3、复杂度：

4、稳定性:快速排序为 不稳定 的排序算法。

算法稳定性定义：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的。

二、C++实现

    
    
    void quickSort(vector &nums,int left,int right)//左闭右闭
    {
        if(left>=right) return;//递归边界

        int base=nums[left];//选择最左边的数字为 base
        int i=left,j=right;
        while(i=base) i++;//从左向右，找到小于 base 的数字
            if(i 
    
    
    void quickSort(vector &nums,int left,int right)//左闭右闭
    {
        if(left>=right) return;//递归边界

        int base=nums[left];//选择最左边的数字为 base
        int i=left,j=right;
        while(i=base) j--;//改动：从右向左，找到小于 base 的数字
            while(i 
有待补充：
 
1、时空复杂度分析
 
2、为什么：当基准数选择最左边的数字时，那么就应该先从右边开始搜索？