快速排序

前几天有人问起快排,我心想这不难呀,把原理讲完了以后发现自己写不出来……回去默默看着导论用ruby写了一个……

快排使用分治思想。最重要的是分区:取一个基准值,比基准值小的放到数组左边,比基准值大的放到数组右边,基准值自己放到中间。然后对左边和右边的数进行再分区,如此递归直到全部排列好。

基准值是从数组中获取到的,你可以自己选择,或者随机选择一个。如果是随机取基准值的快排,因为无法确定命中最好情况还是最坏情况,所以大量的排序情况下会趋近于期望值。

快排保持着两个变量或者指针,一个是当前迭代到的key,一个是当前需要交换的key。如果达到交换条件(比如迭代到的key对应的值相对比对值小)就和需要交换的key进行交换。这两个变量或者指针可以按照自己的意愿进行调整,不管是从左到右,还是从右到左。

这里要注意的是当前需要交换的数是什么,我们假设比基准数小的数叫小数,比基数大的叫大数,排列在数组中最左边的大数叫最左大数,那么在程序中和基准数比对时:

  • 当前数是小数,交换当前数和最左大数(此时最左大数可能被移到了其他大数右边,往下一位找到下最新的最左大数)
  • 当前数是大数,进入下一轮
  • 和基准值相等,这种情况算大数小数都是可以的,因为后面迭代时会重新排到正确位置

所有数字比对和移动完毕后,把基准数和最左大数交换,这样基准数就在所有数字的中间了。

下面是增加了随机的ruby版本

快速排序》上有6条评论

  1. Pingback引用通告: 堆排序 | 星芒

发表评论

电子邮件地址不会被公开。 必填项已用*标注