首页 > 代码库 > 算法整理(四):浅析快速排序的优化问题

算法整理(四):浅析快速排序的优化问题

前文介绍了快速排序的单边扫描和双边扫描,但么有做对比,今天来简单分析下。

一、单边扫描的缺点

单边扫描最大的缺点是每次都要交换,如果一个数组是 5 4 3 2 1,用单边扫描的话,则从4开始,4要和4交换一次,3要和3交换一次,依次类推,这种无意义的操作。正因此用双边扫描会更好,第一趟只需交换一次,就能得到1 4 3 2 5这样的数组。但双边扫描也是可以进一步优化的。

二、双边扫描的优化

优化一:对key值得选取应该使用随机选取的原则,而非第一个数字。意义大家都懂得。

优化二:前文的方法是挖坑法,从右边找到第一个小于key的数,然后将他放到左边的坑里,这时右边新增了一个坑。将左边的坑的索引加1,接着从左往右找第一个大于key的数,再将它放到右边的坑里。依次类推。为了加快速度,再从右边找到第一个小于key的数后,记索引为j,将它和左边的第一个坑交换(注意是交换,而非单纯的放。)。然后从左边的坑加1扫描,找到第一个大于key的数,然后和j进行交换。然后从j-1开始扫描找第二个小于key的数,依次类推。

优化三:前文介绍了插入排序,他的特点是对一个基本有序的数组进行排序会非常的快,因此在进行快速排序时,可以首先判断right-left的值,如果这个值很小,则返回。最后进行一次插入排序就ok!这也是一种优化思路。

具体的 代码杂家就不附了,网上都能找到。

参考文献:《编程珠玑》11章