首页 > 代码库 > 算法整理(四):浅析快速排序的优化问题
算法整理(四):浅析快速排序的优化问题
前文介绍了快速排序的单边扫描和双边扫描,但么有做对比,今天来简单分析下。
一、单边扫描的缺点
单边扫描最大的缺点是每次都要交换,如果一个数组是 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章
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。