快速排序的三种方法(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)