Python之快速排序(单路快排、双路快排、三路快排)

快速排序

• 1、单路快排
• 2、双路快排
• 3、三路快排

1、单路快排

\quad \quad 单路快排即快速排序。
\quad \quad 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

1.1 普通单路快排

基本思想:

• 1): 从序列中挑出一个元素作为"基准"元素，一般是该序列的第一个元素或者是最后一个元素。

• 2): 把序列分成2个部分，其数值大于"基准"元素的元素放在"基准"元素的左边，否在放在"基准"元素的右边，此时"基准"元素所在的位置就是正确的排序位置，这个过程被称为 partition（分区）。

• 3): 递归将"基准"元素左边的序列和"基准"元素右边的序列进行partition操作。

算法的演示：

Partition主要思想:

这个就是待排序的数组序列，可将第一个元素作为"基准"元素。

给"基准"元素找到合适的位置，将比"基准"元素小的元素放在其左边，否则放在其右边

具体分区过程：

• 首先将"基准"元素用v表示（选择第一个元素），使用i作为遍历序列的索引值，j的位置表示>v部分和<v部分的分界位置（也就是最后一个小于v的元素所在位置）。

• 如果此时i指向的元素大于v，这个好处理，直接将i++即可，也就表示大于v的元素多了一个

• 如果此时i指向的元素小于v，那么需要将i指向的元素与大于v序列的第一个元素交换位置，即swap(arr[i], arr[j+1])，然后再将i++，再将j++即可，表示小于v的元素多了一个。如下图所示
  
  进行swap(arr[i], arr[j+1])
  
  j++
  
  i++

• 遍历完成以后，将元素v与j指向的元素交换位置即可。
  

此时就出现了小于"基准"元素的元素在其左边，大于"基准"元素的元素在其右边的分布情况。

【python代码实现】

code-1:以数组第一个元素为基准元素

'''
分区函数
输入：待排序数组，l，r:待分区的数组的起始位置，数组长度减一
作用：将数组第一个元素视为基准元素v，并将所有小于v的元素放到左边，大数放到右边
输出：返回正确分割索引j即小于与大于的分界
'''
def partition_first_base(nums,l,r):
  
    v=nums[l]#以第一个元素为基准元素
    j=l+1#
    for i in range(l+1,r+1):#遍历数组除基准元素之外剩余的元素
        if nums[i]<v:
            nums[i],nums[j]=nums[j],nums[i]
            j+=1
    nums[l],nums[j-1]=nums[j-1],nums[l]#将基准元素与最后小于基准元素的位置交换以下
    return j-1

'''
快排函数
输入：待排序数组，l:数组起始位置，r：数组长度-1
作用：将数组进行排序
输出：返回已排好的数组
'''
def quick_sort(nums,l,r):
    if l>=r:
        return nums
    else:
        m=partition_first_base(nums,l,r)
        quick_sort(nums,l,m-1)
        quick_sort(nums,m+1,r)
    return nums
A=[3,2,9,5,6,4,1]
quick_sort(A,0,len(A)-1)
    

code-2:以数组最后一个元素为基准元素

'''
分区函数
输入：待排序数组，l，r:待分区的数组的起始位置，数组长度减一
作用：将数组最后一个元素视为基准元素v，并将所有小于v的元素放到左边，大数放到右边
输出：返回正确分割索引j即小于与大于的分界
'''
def partition_last_base(nums,l,r):
  
    v=nums[r]#以数组中最后一个元素为基准元素
    j=l#分解位置索引
    for i in range(l,r):#遍历数组除基准元素之外剩余的元素
        if nums[i]<v:
            nums[i],nums[j]=nums[j],nums[i]
            j+=1
    nums[r],nums[j]=nums[j],nums[r]#将基准元素与最后小于基准元素的位置交换以下
    return j

'''
快排函数
输入：待排序数组，l:数组起始位置，r：数组长度-1
作用：将数组进行排序
输出：返回已排好的数组
'''
def quick_sort_2(nums,l,r):
    if l>=r:
        return nums
    else:
        m=partition_last_base(nums,l,r)
        quick_sort_2(nums,l,m-1)
        quick_sort_2(nums,m+1,r)
    return nums
A=[3,2,9,5,6,4,1]
quick_sort_2(A,0,len(A)-1)
    

单路快排特点：

• 快速排序最差时间复杂度为 O ( n 2 ) O(n^2) O(n2)

• 期望时间复杂度为 O ( n l g n ) O(nlgn) O(nlgn)

• 在o(nlgn)中蕴含的常量比较小

• 就地排序，不需要辅助数组空间

什么时候普通快速排序算法的最差时间复杂度会下降为 O ( n 2 ) O(n^2) O(n2)呢？

我们可以想象一种情况，当待排序的数组近乎有序时，因为我们选择第一个元素作为基准，这时导致比基准元素小的元素基本为0，导致元素全部在基准一边。这样就导致我们递归算法的深度由期望的log(n),变为n。因此算法时间复杂度退化为 O ( n 2 ) O(n^2) O(n2)级别。

那么这种情况的解决办法就是: 尽可能的别让第一个元素成为"基准"元素，而最好使用中间位置的元素成为"基准"元素，那如何做到这点呢？解决办法就是"基准"元素随机产生，而不指定。

1.2 随机单路快排

\quad \quad 随机单路快排与普通单路快排的唯一区别是分区时基准元素随机选取。

【python代码实现】

'''
随机快排分区基函数
输入：nums:待排序数组，l，r:待分区的数组的起始位置，数组长度减一
作用：在数组中随机选取一个元素视为基准元素v，并将所有小于v的元素放到左边，大数放到右边
输出：返回正确分割索引j即小于与大于的分界
'''
import random
def partition_random(nums,l,r):
    m=random.randint(l,r)#randint产生一个随机数
    nums[l],nums[m]=nums[m],nums[l]#将上一程序的第一元素为基准数改为随机数，这样下面的内容就跟partition_first_base一样
    v=nums[l]#以第一个元素为基准元素
    j=l+1#
    for i in range(l+1,r+1):#遍历数组除基准元素之外剩余的元素
        if nums[i]<v:
            nums[i],nums[j]=nums[j],nums[i]
            j+=1
    nums[l],nums[j-1]=nums[j-1],nums[l]#将基准元素与最后小于基准元素的位置交换
    return j-1
'''
随机快排函数
输入：待排序数组，l:数组起始位置，r：数组长度-1
作用：将数组进行排序
输出：返回已排好的数组
'''
def quick_sort(nums,l,r):
    if l>=r:
        return nums
    else:
        m=partition_first_base(nums,l,r)
        quick_sort(nums,l,m-1)
        quick_sort(nums,m+1,r)
    return nums
A=[3,2,9,5,6,4,1]
quick_sort(A,0,len(A)-1)

2、双路快排

\quad \quad 之前讲的，当我们排序的是一个近乎有序的序列时，快速排序会退化到一个O(n^2)级别的排序算法，而对此的改进就是引入了随机化快速排序算法；但是当我们排序的是一个数值重复率非常高的序列时，
此时随机化快速排序算法就不再起作用了，而将会再次退化为一个O(n^2)级别的排序算法，那为什么会出现这种情况呢？且听下面的分析:

如上图所示就是之前分析的快速排序算法的partition的操作原理，我们通过判断此时i索引指向的数组元素e>v还是<v，将他放在橙色或者是紫色两个不同的位置，然后将整个数组分成两个部分递归下去；但是这里其实我们是没有考虑=v的情况，其实隐含的意思就是下面的两种情况:


其实从这里就可以看出来了，不管是>=v还是<=v，当我们的序列中存在大量重复的元素时，排序完成之后就会将整个数组序列分成两个极度不平衡的部分，所以又退化到了O(n^2)级别的时间复杂度。产生下图所示的情况，左右子树不均衡

针对数值重复率非常高的序列，就产生了双路快排算法.

Partition主要思想:

\quad \quad 之前说的快速排序算法是将>v和<v两个部分元素都放在索引值i所指向的位置的左边部分，而双路快排算法则不同，他使用两个索引值（i、j）用来遍历我们的序列，将<v的元素放在索引i所指向位置的左边，而将>v的元素放在索引j所指向位置的右边，并延用随机选基准元素的思路，等于v时使用交换的方式处理。

图示：

具体分区过程：

• 首先从左边的i索引往右边遍历，如果i指向的元素<v，那直接将i++移动到下一个位置，直道i指向的元素>=v则停止
  
• 然后使用j索引从右边开始往左边遍历，如果j指向的元素>v，那直接将j–移动到下一个位置，直到j指向的元素<=v则停止

• 此时，i之前的元素都已经归并为<v的部分了，而j之后的元素也都已经归并为>v的部分了，此时只需要将arr[i]和arr[j]交换位置即可

这样就可以避免出现=v的元素全部集中在某一个部分，这正是双路排序算法的一个核心

• 将i++，j–开始遍历后后面的元素

【python 代码实现】

import random
'''
双路快排分区基函数
输入：nums:待排序数组，l，r:待分区的数组的起始位置，数组长度减一
作用：在数组中随机选取一个元素视为基准元素v，并将所有小于v的元素放到左边，大数放到右边
输出：返回正确分割索引j即小于与大于的分界
'''
def partition_double(nums,l,r):
    # 随机产生基准元素
    m=random.randint(l,r)
    #将随机产生的基准元素与数组第一元素交换，并令基准元素v为nums[l],就相当于基准元素还是数组第一元素
    nums[l],nums[m]=nums[m],nums[l]
    v=nums[l]
    i,j=l+1,r
    while True:
        while i<=r and nums[i]<v:
            i+=1
        while j>=1 and nums[j]>v:
            j-=1
        if i>j:
            break
        else:
            nums[i],nums[j]=nums[j],nums[i]
            i+=1
            j-=1
    nums[j],nums[l]=nums[l],nums[j]
    return j
'''
双路快排函数
输入：待排序数组，l:数组起始位置，r：数组长度-1
作用：将数组进行排序
输出：返回已排好的数组
'''
def quick_sort_double(nums,l,r):
    if l<r:
        m=partition_double(nums,l,r)
        quick_sort_double(nums,l,m-1)
        quick_sort_double(nums,m+1,l)
    return nums
A=[3,2,9,5,6,4,1]
quick_sort_double(A,0,len(A)-1)

当然除了快排和双路快排，还有一个更加经典的优化，我们叫它三路快排。

3、三路快排

\quad \quad 针对数值重复率非常高的序列，前面提到了了双路快排算法,其实还有一个更高效的快排算法即三路快排。

Partition主要思想:

\quad \quad 双路快排将整个数组分成了小于v，大于v的两部分，而三路快排则是将数组分成了小于v，等于v，大于v的三个部分，当递归处理的时候，将小于v的部分放到指针lt左边，将大于v的部分放到指针gt右边。考虑到v有重复值的情况，遇到等于v的情况，将i指针右移。同样基准元素v的选择可随机随机选择。

图示：

具体分区过程：

• 当元素e等于v的时候直接纳入绿色区域之内，然后i++处理下一个元素。如图：

• 当元素e小于v的时候，只需要将元素e与等于v的第一个元素交换就行了，如图：

• 当元素e大于v的时候，只需要将元素e与等于v的最后一个元素交换就行了。

【python代码实现】

import random
'''
三路快排分区基函数
输入：nums:待排序数组，l，r:待分区的数组的起始位置，数组长度减一
作用：在数组中随机选取一个元素视为基准元素v，划分为三区间
输出：返回正确分割索引lt,gt即小于与大于的分界
'''

def partition_three_ways(nums,l,r):
    # 随机产生基准元素
    m=random.randint(l,r)
    #将随机产生的基准元素与数组第一元素交换，并令基准元素v为nums[l],就相当于基准元素还是数组第一元素
    nums[l],nums[m]=nums[m],nums[l]
    v=nums[l]
    lt=l # nums[l+1...lt]<v
    gt=r+1# nums[gt...gt]>v
    i=l+1 # nums[lt+1...i]==v
    while i<gt:
        # i==gt时表示已经比较结束
        if nums[i]<v:
            nums[i],nums[lt+1]=nums[lt+1],nums[i]
            lt+=1
            i+=1
        elif nums[i]>v:
            nums[i],nums[gt-1]=nums[gt-1],nums[i]
            gt-=1
        else:# nums[i]==v
            i+=1
    nums[l],nums[lt]=nums[lt],nums[l]
    return lt,gt
'''
三路快排函数
输入：待排序数组，l:数组起始位置，r：数组长度-1
作用：将数组进行排序
输出：返回已排好的数组
'''
def quick_sort_three_ways(nums,l,r):
    if l<r:
        lt,gt= partition_three_ways(nums,l,r)
        quick_sort_three_ways(nums,l,lt-1)
        quick_sort_three_ways(nums,gt,r)
    return nums
A=[3,2,9,5,6,4,1]
quick_sort_three_ways(A,0,len(A)-1)

参考资料：

1、部分图片来自于慕课网liuyubobobo老师的课程。