快速排序的三种方法(python实现)

2022年 11月 5日

快速排序的三种方法(python实现)

前言

为什么要写这篇博客呢？快速排序方法网上一搜一大堆，已经是比较全面的了。好久没摸排序算法了，下午想找个博客快速重温一下快排。然后看到150多的评论，基本都是说那个博主的排序算法是错的，和他们知道的排序算法不一样，一堆评论说赶紧删了别误导别人。我仔细看了算法，实行起来的确和我之前所了解的排序算法不一样，但是排序结果是没问题的，这个算法并没有脱离快排切分的思想，然后才知道这是《啊哈，算法》一书里面的方法。

（个人多bb两句：看看那篇文章下面评论真就是当代互联网评论的缩影。还是自己写一篇博客，综合一下快速排序算法。）

后言

边写这篇文章的时候，边看别人的文章，还是感觉自己写的太烂了。回头想想写这篇博客我也挺傻的。总之继续努力吧，博客写的不是很好。

1.快速排序(挖坑法)

你在网上看到的大多都是双指针快速排序法，也就是我要介绍的第一种快速排序的方法。简单起见，给定一组数{4，1，2，7，6，3，5}.用快速排序的方法对这种组数进行排序。

第一步，在这组数里面随机选择一个数作为基准数。(我们每轮排序就是要把，比基准数大的数放在其右边，比其小的放在左边。)
我们给定两个”哨兵”(指针),分别指向这组数的第一个数和最后一个数。
右边的哨兵先动,依次向左，找到一个比基准数，小的数然后和基准数交换，此时右哨的指向基准数。左哨再动，依次向右，找到一个比基准数大的数，然后交换，此时左哨指向基准数。
直到两个”哨兵”相遇结束这一轮排序。过程如下。
接着以基准数切分两边的数得到{3,1,2}和{6,7,5}循环上述过程。

在这里插入图片描述

代码实现(python)

import numpy as np
import sys
# 设置随机种子
np.random.seed(0)
# 得到一组随机数
nums=np.random.randint(10,size=(8))
# nums=np.array([1,3,2,2])
print(nums)

# 我这里就选择每组数的第一个作为基准数，不随机选择数字了
def QuickSort(nums,left,right):   
    if left>=right:
        return 0
    baseNumber=nums[left]
    i=left
    j=right
    while i!=j:
        while j>i and nums[j]>=baseNumber:
            j-=1
        if j>i:
        #实现两个元素的互换，python就是简单啊
            nums[i],nums[j]=nums[j],nums[i]

        while i<j and nums[i]<=baseNumber:
            i+=1
        if i<j:
            nums[i],nums[j]=nums[j],nums[i]
    QuickSort(nums,left,i-1)
    QuickSort(nums,i+1,right)
    
QuickSort(nums,0,nums.size-1)
print(nums)

2.快速排序(交换法)

具体你们可以参考这篇文章，就是我前言说的那篇文章，说的应该是很详细了。点这里！

我就简单的说一下，这种排序和之前一样右哨先开始移动找到比基准数小的数，但是它不急着交换，然后左哨开始移动，找到一个比基准数大的数字。然后交换两个”哨兵”的值，然后继续上述操作指导两个”哨兵”相遇，然后并没有结束，哨兵相遇时所指的那个数与基准数再交换，这时一轮才结束。(注意哨兵没有相遇的时候基准数的位置是没有改变的)
代码如下其实只改了一小部分，代码如下:

import numpy as np
import sys
# 设置随机种子
np.random.seed(0)
# 得到一组随机数
nums=np.random.randint(10,size=(8))
print(nums)
def QuickSort(nums,left,right):   
    if left>=right:
        return 0
    baseNumber=nums[left]
    i=left
    j=right
    while i!=j:
        while j>i and nums[j]>=baseNumber:
            j-=1
# 这个地方的交换没有了-----------
        while i<j and nums[i]<=baseNumber:
            i+=1
        if i<j:
            nums[i],nums[j]=nums[j],nums[i]
# 这个地方多了一个交换------------
    nums[j],nums[left]=nums[left],nums[j]
    QuickSort(nums,left,i-1)
    QuickSort(nums,i+1,right)
    
QuickSort(nums,0,nums.size-1)
print(nums)

3.快速排序(前后指针法)

这个方法跟前面的方法有些区别，但是本质都是一样的。下面图解吧！

我们定义了前向索引prev，和当前索引cur，left和right分别指向第一个数和最后一个数。
prev最开始指向-1，cur指向prev的后一个位置即0。并且我们定义right指向的数为key也就是最后一个数。

执行规则：cur开始找比key小的数，只有找到比key小的数，才执行+ +prev并且如果prev ！= cur时执行swap(a[prev],a[cur]),然后执行cur++ ，知道key前一个值中止循环

动态的过程如下。

在这里插入图片描述

代码实现：

import numpy as np
import sys
# 设置随机种子
np.random.seed(0)
# 得到一组随机数
nums=np.random.randint(10,size=(8))
# nums=np.array([4,3,2,1])
print(nums)

def QuickSort(nums,left,right):  
    if left>=right or right>nums.size-1:
        return 0
    prev=left-1
    cur=prev+1
    key=right 
    baseNumber=nums[key]
    while cur!=key:
        if nums[cur]<baseNumber:
            prev+=1
            if(prev!=cur):
            #实现两个元素的互换，python就是简单啊
                nums[prev],nums[cur]=nums[cur],nums[prev]
        cur+=1
    prev+=1
    nums[prev],nums[key]=nums[key],nums[prev]
    QuickSort(nums,left,prev-1)
    QuickSort(nums,prev+1,right)
    
QuickSort(nums,0,nums.size-1)
print(nums)