乐趣区

关于快速排序:快速排序及其优化超详细解答代码真正理解

jiezi

原文: https://zhuanlan.zhihu.com/p/…
欢送关注我知乎号: https://www.zhihu.com/people/…

疾速排序 QuickSort 采纳了分治法 Divide-and-ConquerMethod，通过将数组链表或其余元素集分为待排序汇合和已排序汇合，并在一次次迭代中将待排序汇合的元素转化到已排序汇合当中直到全副元素都为已排序则实现排序。

疾速排序利用这一策略，节约了解决已排序元素的老本。算法只关注残余待排序的元素，其中地位间断的未排序元素子串又分为：S1(左侧），pivot(替换枢纽元)，S2（右侧）

以疾速排序来实现升序排序为例：

先从数组当选取出一个数组作为枢轴元 pivot。（选取枢纽元的策略很要害）
将待排序汇合所有小于枢轴元 pivot 的元素移至 s1(左侧），所有大于枢轴元 pivot 的元素移至 s2（右侧）：（双指针中的相向指针法）
先将枢轴元 pivot(准有序局部)放到最左或者最右辨别出待排序局部。
将 i, j 别离指向待排序局部索引的最左和最右。
如果 i 索引指向的元素小于枢纽元，则 i ++；否则，i 进行。j 索引指向的元素大于枢纽元，j–；否则，j 进行。
如果 i <j，则替换两个元素，持续循环 3，4 步骤；否则跳出循环，将 i 对应的元素与枢纽元 pivot 替换（这时候实现了宰割）
这个时候定义枢轴元 pivot 为已排序局部，对残余未排序局部 S1(左侧）S2(右侧)持续循环步骤 1，2，3 直到所有元素都已排序。
最原始的疾速排序
最原始的疾速排序采纳最简略粗犷的枢纽元选取策略，即选取第一个或最初一个元素为 pivot。

该计划的均匀工夫复杂度为 O(nlogn)，当遇到数组刚好有序的状况下会呈现最坏工夫复杂度 O(n^2)，因为当输出序列自身有序时，会导致 S1 或 S2 汇合为空，除枢纽元外所有元素都在 S1 或 S2，此时遍历替换的工夫效率大幅降落，因为节约了另一个区间的作用。

Python 代码

nums = [23,2,4,6,2,5,1,6,13,54,8]

def quicksort(nums, left, right):   # left 为最左索引，righ 为最右索引
    if left >= right:
        return
    pivot = left // 取第一个元素为 pivot
    i, j = left, right
    while i < j:
        while nums[pivot] <= nums[j] and i < j:
            j -= 1
        while nums[pivot] >= nums[i] and i < j:
            i += 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    nums[pivot], nums[i] = nums[i], nums[pivot]
    quicksort(nums, left, i-1)
    quicksort(nums, i+1, right)

def quicksort2(nums, left, right):          # 用栈代替递归
    if left >= right:
        return
    stack = []
    while stack or left < right:
        if left < right:
            pivot = left
            i, j = left, right
            while i < j:
                while nums[pivot] <= nums[j] and i < j:
                    j -= 1
                while nums[pivot] >= nums[i] and i < j:
                    i += 1
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            nums[pivot], nums[i] = nums[i], nums[pivot]
            stack.append((left, i, right))
            right = i - 1
        else:
            left, mid, right = stack.pop()
            left = mid + 1

quicksort2(nums, 0, len(nums)-1)
print(nums)

因为堆栈存储(递归等价于栈代替），疾速排序空间复杂度 O(logn)

所以 S1 和 S2 约均衡，疾速排序的效率越高，即中值（中位数）是枢纽元最好的抉择（因为能够将序列均分为两个子序列，归并排序通知咱们，这时候是 O(NlogN）

但要计算一组数组的中位数就比拟耗时，会减慢快排的效率。

小问题：为什么当轴元 pivot 放入左侧时, 必须先平移右指针 j，而不能先平移左指针 i ?

答案：为了防止平移替换过程中, pivot 本人被替换掉。

疾速排序的优化
三数中值疾速排序（三数中值法选取枢轴元 pivot）
尽管计算一组数组的中位数就比拟耗时，会减慢快排的效率。但能够通过计算数组的第一个 left，两头地位(right-left)/2(向下或向上取整)，最初一个 right 元素的中值来代替。

Python 代码

def quicksort_opt1(nums, left, right): 
    if left >= right:
        return
    stack = []
    while stack or left < right:
        if left < right:
            l, m, r = left, (right-left)//2, right # 第一个, 两头地位, 最初一个
            pivot = findmedian(l, m, r) # 三数取中值法选取枢轴元 pivot
            i, j = left, right
            while i < j:
                while nums[pivot] <= nums[j] and i < j:
                    j -= 1
                while nums[pivot] >= nums[i] and i < j:
                    i += 1
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            nums[pivot], nums[i] = nums[i], nums[pivot]
            stack.append((left, i, right))
            right = i - 1
        else:
            left, mid, right = stack.pop()
            left = mid + 1

def findmedian(l, m, r):
    if nums[l] <= nums[m]:
        if nums[m] <= nums[r]:
            return m
        else:
            if nums[l] >= nums[r]:
                return l
            else:
                return r
    else:
        if nums[m] >= nums[r]:
            return m
        else:
            if nums[l] >= nums[r]:
                return r
            else:
                return l

用三数中值法来选取枢轴元 pivot 肯定水平上防止了最坏的状况产生。

然而即便这样，咱们的疾速排序算法依然有可能呈现最坏的状况：工夫复杂度 O(n^2)

因为反复的元素越多会给算法带来越多的无用功，会波及以下一个问题：

简略说是遇到与枢纽元相等的元素时，左右索引指针的平移须要进行吗？

如果只有一个进行：这将导致所有等于枢纽元 pivot 的元素都挪动到同一侧 (S1 或 S2)，在极其状况下所有元素都是反复，会产生最坏状况 O(n^2)
如果都不进行：在极其状况下所有元素都是反复，整个过程枢纽元 pivot 相当于对整个数组进行了一次遍历，工夫复杂度是 (n + n-1 +…+2+1)=(1/2)(1+n)*n，即工夫复杂度 O(n^2)，其实推演一下会发现基于疾速排序的执行规定这种状况跟状况 1 是等价的，都不进行相当于始终只有一个指针在平移，而且是始终平移到开端才进行。
如果都进行：在极其状况下所有元素都是反复，尽管看似会进行很屡次“无意义”的替换，但因为每次双指针相遇的地点都是数组的中点，这个时候恰好将序列分为两个均等调配的子序列，还是归并排序的原理，达到分治法效率最大化，以此类推会让枢纽元 pivot 以 logn 的速度走残缺个数组。所以这种办法最坏状况的工夫复杂度为 O(nlogn)
反复元素解决思路：三向切分疾速排序

三向切分疾速排序举荐简书上这个博客

疾速排序(Quick Sort)
​www.jianshu.com/p/779bc4b61254

双路疾速排序
图解疾速排序及双路三路疾速排序 – SegmentFault 思否
​segmentfault.com/a/1190000021726667

双路疾速排序把待排序区域用指针 i , j 分为三个子区域:

(<nums[pivot])，未知，(>nums[pivot])

将 &amp;amp;lt;v 和 &amp;amp;gt;v 两局部放在数组的两端，用 i 指向 &amp;amp;lt;v 局部的下一个元素，用 j 指向 &amp;amp;gt;v 局部的前一个元素。

从 i 开始向后遍历，如果遍历的元素 &amp;amp;lt;v，则持续向后遍历，直到遍历的元素 &amp;amp;gt;v，则进行遍历。同样从 j 开始向前遍历，如果遍历的元素 &amp;amp;gt;v，则持续向前遍历，直到遍历的元素 &amp;amp;lt;v，则进行遍历。

替换 i 指向的元素和 j 指向的元素。而后 i ++，j– 持续比拟下一个。
Python 代码

def quicksort_opt2(nums, left, right): 
    if left >= right:
        return
    stack = []
    while stack or left < right:
        if left < right:
            l, m, r = left, (right-left)//2, right # 第一个, 两头地位, 最初一个
            pivot = findmedian(l, m, r) # 三数取中值法选取枢轴元 pivot
            nums[pivot], nums[left] = nums[left], nums[pivot]
            pivot = left
            i, j = left+1, right
            while i <= j:   # 为什么不能是 i < j?
                # 此处先平移 j 和先平移 i 对后果没有影响, 因为 i=left+ 1 避开了 pivot
                while nums[i] < nums[pivot] and i <= j:
                    #不能改为 nums[i] <= nums[pivot], 因为这种形式将间断呈现的这些值归为其中一方, 使得两棵树不均衡
                    i += 1
                while nums[j] > nums[pivot] and i <= j: 
                    j -= 1
                if i <= j:
                    nums[i], nums[j] = nums[j], nums[i]
                    j -= 1
                    i += 1
            nums[pivot], nums[j] = nums[j], nums[pivot] 
            #因为 pivot 搁置在右边, 所以不可与左侧指针 i 替换 ----> 会造成有限循环
            stack.append((left, j, right))  
            right = j - 1
        else:
            left, mid, right = stack.pop()
            left = mid + 1

nums = [23,2,4,6,2,5,1,6,13,54,8]
quicksort_opt2(nums, 0, len(nums)-1)
print(nums)

问题 1：为什么此处不能用 i < j 代替 i <= j 当作循环条件？

问题 2：为什么平移完结后, pivot 要跟 j 替换 而不是 i？为什么跟 i 替换会造成有限循环？

那么在此基础上，咱们是否再次优化，将前文提到的反复元素 ’ 无意义 ’ 的替换也省了？当然能够，上面的三路疾速排序就是围绕这点进行优化。

三路疾速排序 3 way quick sort
在双路快排把未排序区域分为三个子区域的根底上，三路快排多分了一个子区域用来寄存反复且等于 pivot 的元素，来辨认并跳过他们。

在双路疾速排序的根底上，咱们把等于 v 的元素独自作为一个局部。lt 指向小于 v 局部的最初一个元素，gt 指向大于 v 局部的第一个元素。

从 i 开始向后遍历，如果遍历的元素 e =v，则 e 间接合并到 = v 局部，而后 i ++ 持续遍历。如果遍历的元素 e &amp;amp;lt;v，则将 e 和 = v 局部的第一个元素（lt+ 1 指向的元素）替换，而后 lt++，i++ 持续遍历。如果遍历的元素 e &amp;amp;gt;v，则将 e 和 &amp;amp;gt;v 局部前一个元素（gt- 1 指向的元素）替换，而后 gt–，不过此

Python 代码

def quicksort_opt3(nums, left, right): 
    if left >= right:
        return
    stack = []
    while stack or left < right:
        if left < right:
            l, m, r = left, (right-left)//2, right
            pivot = findmedian(l, m, r)
            nums[pivot], nums[left] = nums[left], nums[pivot]
            pivot = left
            lt, gt = left, right + 1
            i = left + 1
            while i < gt:
                if nums[i] < nums[pivot]:
                    nums[i], nums[lt+1] = nums[lt+1], nums[i]
                    i += 1
                    lt += 1
                elif nums[i] > nums[pivot]:
                    nums[i], nums[gt-1] = nums[gt-1], nums[i] 
                    gt -= 1
                else:# nums[i] == nums[pivot]
                    i += 1
            nums[pivot], nums[lt] = nums[lt], nums[pivot] 
            stack.append((left, lt, right))  
            right = lt - 1
        else:
            left, mid, right = stack.pop()
            left = mid + 1

nums = [23,2,4,6,2,5,1,6,13,54,8]
quicksort_opt3(nums, 0, len(nums)-1)
print(nums)

疾速排序复杂度剖析
疾速排序的均匀工夫复杂度为 O(nlogn)

疾速排序均匀复杂度数学证实可参考此答复：
https://www.zhihu.com/questio…

疾速排序的短板：
即便是三路疾速排序也做不到堆排序那样保障最坏工夫复杂度为 O(nlogn)

疾速排序是不稳固排序 (所谓稳固就是当待排数组中存在反复元素的时候，排序后反复元素的绝对程序不会扭转)

当待排序序列元素数量很小 (N<=20) 的时候，疾速排序不如插入排序快，并且插入排序是稳固排序。

github 代码出处: https://github.com/stevezkw19…

欢送关注我的 github：stevezkw1998 – Overview

退出移动版