不同的快排算法
之前写过一篇快排
但是现在来看写的很简单, 很无聊
快排的思想其实大家都懂
这次详细写写不同快排之间的区别和一些优化点
1. 首先是pivot元素的选择
a. 当我们数组本身就是随机的时候, 选择 第一个/最后一个/中间一个 都是可以的, 但如果数组是有某种规律的, 有可能会退化成O(n^2)的算法, 有一个比较有趣的技巧是, 把这三个数中的中值作为基准, 这样就可以减少不平衡划分的概率
b. 再一个就是我们熟悉的随机选择了, 随机选择一个数作为pivot
2. 然后是分组的算法不同
a. 我们熟悉的算法, 使用两个索引i和j从两端向中间扫描, 交换元素
b. 还有一种写法, 用单个索引i, 小于等于pivot的元素移动到左侧, 可参考:
https://www.geeksforgeeks.org/quick-sort-algorithm/
3. 递归与非递归实现
这种不多介绍了, 常见快排都是递归写, 来得简单直接
需要注意的是有个很精妙的技巧, 先递归小的数组, 再递归大的数组, 可以利用尾递归降低递归深度
4. 混合使用其他排序
比如元素小于10个的时候, 就可以使用插入排序了, 性能更好(c++的sort也是这么做的)
如果你问为什么性能更好
hmmmmm
插入排序是个线性排序, 常数开销低, 规避了递归, 而且对于接近有序的数组效率很高(quick sort排序可以形成一种接近有序的数组?玄学.jpg)
具体说说实现时候的一些细节
主要是什么时候跳出循环的问题, 很简单, i和j交错的时候, 谁和pivot交换呢? 主要取决于写法, 如果pivot是第一个元素且是升序排序, 那肯定是拿小的那个和pivot交换
还有选择第一个元素的时候i移动用小于等于为了规避pivot被移动的问题
hmmmm 懒得写了 以后有机会补充吧