快速排序算法（C++）介绍和简易实现

快速排序算法，即一种递归地讲数组按一定大小标准分成两组，小的一组在前，大的一组排在后的算法。

有关快速排序算法的文章和图解，网络上已经很多了，但阅读理解起来可能稍有困难，接下来我们将看到更容易理解的快速排序算法。

示例：以数组的首位作为基准（pivot），将小于ta的数置于ta的左边，大于ta的数在右边，左边只有1个元素，排序完成，而右边有4个数，那么把这4个数作为新的要排序的（抽象的）数组，重复上面的过程，最终基准所在的（抽象的）数组只有基准一个元素（如下图第二排的“2”），排序完成。

快速排序的复杂度

快排过程中需要移动元素的位置，很大程度上决定了时间复杂度。如果一个数组由大到小排列，而选取首位（最大数）为基准，则每一个元素都需要移动，而每一次移动的过程：对n个元素，考虑一般情况，分割一次数组（即小的排左边的过程）比较和交换元素的次数和n有关（虽然有的时候不用交换，但一定会比较）；而快排有一颗递归树，在数字比较随机，树比较均匀的情况下，树的高度近似logn，而树的每一层都有n个元素参与partition（数组分割成抽象数组后，多个抽象数组partition，因为partition的复杂度与n的一次方相关，在估测复杂度时，可以认为每一层都有n个元素参与一次partition），随机情况的复杂度即为n*logn。

最坏情况这棵树只沿着一颗子树延伸，树的高度为n，每一层仍有n个元素参与partition，复杂度为n*n。看一下数字从大到小排列的情况，例如100到1，首次partition会进行99次比较，最后一次partition进行1次比较，并且递归也会进行99次，从等差数列的公式也可以看出来它与n的平方相关。

复杂度的数学证明：

快速排序的代码（便于理解过程的版本，partition时移动数据，复杂度高）

#include <iostream>
using namespace std;

void QuickSort(int arr[],int start,int end){//递归的时候，start和end都相对于整个arr
    if(start>=end){return;}
    int temp=start;//保留start初始值
    int pivot=arr[start];//以数组或分割后的抽象数组的第一个元素作为基准(pivot)
    for(int i=start+1;i<=end;i++){//遍历arr[start]右边的元素
        if(arr[i]<pivot){//当arr[i]比基准小
            arr[start]=arr[i];//小的元素放到基准所在的位置
            for(int j=i;j>start;j--){//遍历arr[start]到arr[i]，全体右移（arr[start]已经放了新的元素）
                arr[j]=arr[j-1];//右移
            }
            arr[++start]=pivot;//由于start和i项交换，start+1项的值需要修正,完成交换后基准右移，所以start也要++
        }
    }//完成了一次左右分组（排序）
    
    QuickSort(arr, temp, start-1);//对0号到start-1号元素排序，共有start个元素
    QuickSort(arr, start+1, end);//对右边的元素排序
}

int main(int argc, const char * argv[]) {
    int arr[]={3,4,2,7,5,8,6,1};//8个元素组成的的乱序数组
    QuickSort(arr,0,7);//8个元素即0号到7号
    for(int i=0;i<8;i++){
        cout<<arr[i]<<endl;
    }
    
    return 0;
}

快速排序的代码（普通版本）

#include <iostream>
using namespace std;

int Partition(int arr[],int &start,int &end){
    int pos=start;//(pos-start)用来记录小于等于arr[start]（基准）的数的个数，arr[start+1]到arr[pos]都小于基准
    for(int i=start+1;i<=end;i++){//遍历基准以后的元素
        if(arr[i]<arr[start]){//当某一项小于基准
            if(arr[i]!=arr[++pos]){//如果任何一个大于基准的数后面所有元素中都没有小于x基准的数（即基准后的元素，前一部分全部小于基准，后一部分全部大于基准），则arr[i]==arr[pos]，不需要交换；否则需要交换
                swap(arr[i], arr[pos]);
            }
        }
    }
    swap(arr[start], arr[pos]);//基准的位置开始没有移动，现在把基准的位置交换到小于基准的抽象数组的最右端，实现对数组的分割
    return pos;
}

void QuickSort(int arr[],int start,int end){//递归的时候，start和end都相对于整个arr
    if(start>=end){return;}//对应多种情况，pos可能等于start，pos-1为负，这种情况没有数小于基准，也不需要排序，对应start==end+1；pos等于start+1时，只有一个数比基准小，并且已经z位于基准左边，也不需要排序，对应start==end
    int pos=Partition(arr, start, end);//对数组或抽象数组按基准排列，基准左边的数小于基准，右边大于基准
    QuickSort(arr, start, pos-1);//对0号到start-1号元素排序，共有start个元素
    QuickSort(arr, pos+1, end);//对右边的元素排序
}

int main(int argc, const char * argv[]) {
    int arr[]={3,4,2,7,5,8,6,1};//8个元素组成的的乱序数组
    QuickSort(arr,0,7);//8个元素即0号到7号
    for(int i=0;i<8;i++){
        cout<<arr[i]<<endl;
    }
    return 0;
}

两个指针的快速排序&&Partition的优化

待补充

参考资料：

1.《算法导论》第7章：快速排序

2.快速排序的时间复杂度nlogn是如何推导的？？

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1q1xzkj9mydbq