快排里面找基准值的算法
思路:先把数据里面第一个数据定义为基准值。我们要找到基准值左边比基准值小的数据(left)和基准值右边比基准值要大的数据(right)。
怎么把left和right的数据放到相应的位置里呢。
我们让left从前往后遍历,right从后往前遍历。left找比基准值大的数据,right找比基准值小的数据。找到之后left right里面的数据交换位置。这样就可以把大的数据往后放,小的数据往前放。
当right走到超过left的时候,right里存着比基准值要小的数据,让right和基准值里面的数据交换位置,这个时候基准值左边都是小的数据,右边都是大的数据。
这个时候right里面存的数据就是我们的基准值。
注意:交换的时候要判断一下当前的right有没有走的超过right,因为有可能刚进循环的时候right没越界,但是循环完一次之后就越界了。
那 left 和基准值相等还要不要交换位置呢??
相等就没必要交换位置,但是如果一直往后遍历,就容易出界,所以要多加一个限制条件:left<=right 保证不出界。
如果数据全是一样的,按照前面相等就不交换位置的话,每一次分组就要从头开始遍历,享受不到二分法带来的便利了,所以我们就是相等也交换,这样能提高运行效率。
那当left和right相等的时候要不要交换呢???
比如上面这个情况left原来在7的位置,right在3的位置,走完之后都在9的位置,要是9和基准值换了之后就不符合排序的要求了。所以相等的时候继续进去,再走一轮right的位置就是基准值的位置了。