快速排序详解

快速排序

1.朴素版

无论是朴素版还是优化版，其实算法思想都是一样的
假设从小到大排序
按照分治三部曲：
划分问题：
将数组分成两部分，要求左半部分所有元素一定要小于等于右部分所有元素
递归求解：
递归排序这两个部分
合并问题：
无需合并，因为左边有序，左边小于等于右边，右边有序
可见最难的是划分问题
为了简化，可以选一个基准点，要求基准点左边小于等于基准点，基准点小于等于右边
理论上，基准点的选取是任意的，但是会影响时间复杂度
如果可以使用辅助空间，那么可以先找到所有比基准点小的元素放进去
然后放等于基准点的元素，最后放大于基准点的元素，然后重新赋值给原数组
然后找到等于基准点的第一个位置和最后一个位置，然后l_{第一个位置与最后一个位置+1}r分别递归
这样其实是三路快排，避开了大规模相等元素的情况
但是要用额外n的空间。
如果不借助辅助空间，仅使用栈空间，那么思路如下
：
这里选用左闭右开区间
当\(r-l>1\)时才需要排序，否则无需排序
首先选取基准点，记录基准点的位置，然后两个指针变量\(i\) \(j\)，最开始指在左 右端点(注意不一定是\(0\) \(n-1\),因为递归是缩小规模的）
然后进行循环
每一次循环内都有两个循环
第一个循环是\(j\)倒着找比基准点小的，找到就交换基准点和\(a[j]\)，并更新基准点位置，如果找不到，就当\(j\)和基准点位置相等时停止
因为比基准点小的应该在基准点左侧，当基准点右侧有小于他的元素时，应该交换去前面，如果基准点右侧所有值都比基准点大，那么\(j\)就应该在基准点处停止，否则左侧小的反而去了右边
第二个循环是\(i\)正着找比基准点大的，然后交换并更新基准点位置，停止循环，找不到就在基准点位置\(=i\)时停止
大循环的条件是\(i<j\)
然后进行递归操作，要边界处理
如果基准点的位置在\(l\)或者\(r-1\)，那么基准点要单独作为一部分递归，以缩减规模，否则死循环
递归时基准点放在左右两部分任意一部分都可以

2.优化版

快速排序的时间复杂度分析：
划分部分由于\(i\)和\(j\)从两边向中间碰头，所以\(O(n)\)
且固定不变
考虑交换操作，在序列递增时平均\(O(log^2 n)\)
序列递减时平均\(O(n)\)
当划分操作能够近似相等的把元素分成两部分，即元素个数近似相等，则\(O(nlogn)\)
但是当遇到递增序列时，若以最小值为基准点，则左边\(1\)个元素，右边\(n-1\)个元素，然后递归下去左边\(1\)个元素，右边\(n-2\)个元素
要递归n层，\(O(n^2)\)
所以快速排序最好\(O(nlogn)\),平均\(O(nlogn)\),最坏\(O(n^2)\)
空间考虑栈空间最好\(O(logn)\),最坏\(O（n）\)一般这个
若考虑原数组空间则\(O（n）\)
所以有超时危险，要优化
优化1 把基准点改为\((l+r)/2\)，实测效果不错
优化2 把基准点改为随机数 rand()%(r-l)+l，最小\(l\)，最大\(r-1\)，实测效果也不错
优化3 把基准点改成\(l\) \(r\) \((l+r)/2\) 中\(a\)元素最中间的那个，实测效果差
但是优化1 2 3都不能彻底解决超时，真正重要的是对于划分时对于与基准值相等元素的处理
优化4 把数组划分3部分，左边小于基准值，中间等于基准值，右边大于基准值，，递归时只递归左右，麻烦
优化5，划分时，当a[j]<基准值 a[i]>基准值时break并交换更新，而不是<= >=，因为最开始基准值在中间，当边上的=基准值的元素扫描到时，就会交换并更新，使得基准值靠边，使得左右不均，增大复杂度
实测效果非常好

使用时 1/2 5结合使用最佳
stl优化：记录当前递归层数，当当前递归层数\(>log_2⁡n\)
时，停止快排，改用堆排序，堆排序可以保证\(O(nlogn)\)
这样stl sort 最坏\(O(nlogn)\)
快速排序是不稳定的，即相等元素的相对位置会改变
因为交换，如果原来基准值右边有一个元素，再右边还有一个相等的元素，从右往左搜索，这个元素比基准值小，所以交换，交换 后这个在后面的元素就到了前面
因为快排连续访问内存，所以速度较快，\(O(nlogn)\)时比堆排序快，而\(O(n^2)\)时快排比堆排序慢，就要选用堆排序，而且快排已经排了一部分序，能加速

3.快速选择算法

利用快速排序，可以在平均\(O(n)\)的情况下找出数组一次性第\(k\)大/小值（非动态）
快排划分完成后，因为左边\(<=\)基准值\(<=\)右边，所以第\(k\)小值在左边还是右边可以确定下来
假设\(k\)从\(1\)开始
当只剩下一个元素时，返回这个元素大小
当\(k-1=\)基准值下标\(-l\)时，返回基准值大小
当\(k-1<\)基准值下标\(-l\)时，递归基准值左边
当\(k-1>\)基准值下标\(-l\)时，递归基准值右边，同时\(k-=\)基准值下标\(-l+1\)
最坏\(O（n^2)\)，因为如果问最大值，且数组递增，基准值选取最小值，就是\(O(n^2)\)