最后一个数是5
大于5的区域的第一个数是6
6和5交换
5就不用动了 在数组中固定下来
这一个过程就是partition分层过程
再在小于等于5的区域上拿最后一个数重复此过程
大于5区域上拿最后一个数重复此过程
左侧递归下去
右侧递归下去
总能让左右2个区域都有序
在一个范围上总拿这个范围的最后一个数做划分
然后把最后一个数放到小于等于区域的最后一个位置
然后让小于等于区域做递归
让大于区域也做递归
因为每次都能排好一个数
所以总有整体都有序的时候
每个区域的最后一个值可能都不一样 上面是以5为例做的说明
快排2.0基于荷兰国旗
拿最后一个数做划分 比如是5
让前面的分三个区域 小于5 等于5 大于5区域
把5和大于5区域的第一个数做交换
等于5的区域就靠在一起了
整个数组就变成 等于5的区域在中间
大于5的区域在右边
等于5的区域就不用动了
在小于5的区域上做递归
在大于5的区域上做递归
每一次递归搞定的是一批等于划分值的数
所以总有有序的时候
快排2.0版本比1.0版本快一些
因为它一次搞定一批数
举例说明
原数组
小于5区域
等于5区域
大于5区域
最后一个元素5和大于区域的第一个元素6做交换
等于5的区域在整个数组中的位置固定了
接下来在左侧区域 4301上以最后一个元素1做划分重复该行为
0继续做递归是0
4 3区域 以3做划分
总有都变成有序的时候
在右侧区域 786上 以6做划分重复该行为
左侧和右侧做递归总有都排好的时候
快排1.0和2.0时间复杂度都是O(N^2)
拿最差的例子说明
1,2,3,4,5,6,7,8,9
以9做划分 没有右侧区域
只有左侧区域
划分的过程就是partition
partition过了9个数
在左侧区域拿8做划分 没有右侧区域
只有左侧区域
partion过了8个数
每次只搞定一个
所以等差数列
所以是O(N^2)的算法
最差情况原因只有一个 划分值打的很偏
先看什么时候是好情况
好情况是划分值打在几乎中间的位置
左侧递归的规模和右侧递归的规模都是差不多的
此时的master公式是
T(N)=2 T(N/2) + O(N)
除了调用递归之外（就是partition过程）的时间复杂度是O(N)
整体的时间复杂度是 O(N*LogN)
这种是最好的情况
划分值打偏就会逐渐退化成N^2的算法
左侧很小 右侧规模很大 最差情况就是没有左侧部分 只有右侧部分
或者 右侧很小 左侧规模很大 最差情况就是没有右侧部分 只有左侧部分
不管哪一种都是O(N^2)的算法
因为总是拿数组的最后一个位置做划分
所以差情况没法避免
可以人为构建差的例子
快排3.0
在数组L~R范围上
拿谁做划分
随机选择一个数
随机选了一个数之后 拿它和最后位置上的数做交换
然后拿这个新的最后位置的数做划分
既然是随机选的
好情况和差情况就是概率事件
随机选的可能是最坏的情况 事件复杂度是O(N^2)
也可能是1/5处
master公式是
T(N)=T(4/5)+T((1/5) * N)+O(N)
每一位置都是等概率事件
每一种情况都是1/N的权重
把所有的master公式做概率累加
再求数学期望 得到的结果是O(N logN)的算法
代码
第一步等概率随机选择一个位置
把它跟最右侧位置做交换
在L~R这个范围上 拿最后位置的数即选出来的这个随机数
做partition
返回一个数组 长度一定为2
指的是划分值等于区域的左右边界
原数组最后一个数是5
按照5进行partition划分
等于5的区域是下标12和13的位置
返回的这个数组就是[12,13]
表示划分值等于区域的左右边界
p[0]就是等于区域的左边界
p[0]-1 为小于区域的右边界
然后在小于区域上递归
p[1]是等于区域的右边界
p[1]+1是大于区域的第一个数的位置
在右侧范围上递归
