工程中遇到的排序算法-基础篇

总结下经典的排序算法和工程中遇到的排序。

1. 基于比较的排序算法

时间复杂度$O(n^2)$ 的 排序算法

冒泡排序: 时间复杂度$O(n^2)$,空间复杂度:原地排序,稳定的排序算法。

快速排序: 时间复杂度$O(n^2)$,空间复杂度:原地排序,稳定的排序算法。

选择排序: 时间复杂度$O(n^2)$,空间复杂度:原地排序,不稳定的排序算法。

上述三种排序算法因为时间复杂度比较高,$O(n^2)$。因此只适合小规模数据的排序。

时间复杂度$O(nlogn)$的排序算法

对于大规模数据进行排序,应该选择时间复杂度$O(nlogn)$的排序算法。

归并排序: 时间复杂度$O(nlogn)$,空间复杂度On, 稳定的排序算法。算法思想用到了分治思想。

缺点:实战中使用归并并不多,这是因为归并不是原地排序算法。粗略举例来说,100MB数据,除了数据本身占用的内存之外,排序算法那还需要额外占用100MB的内存,空间耗费翻倍。

快速排序: 时间复杂度 $O(nlogn)$,原地排序,不稳定的排序算法。

谈谈快排的优化,快排可能导致性能差的几点:

快排性能脆弱点1:分区哨兵点选择,哨兵点选择不对可能时间复杂度退化为$O(n^2)$。 快速排序性能关键点在于 pivot分区哨兵点选择。如果数据原来就是有序,每次pivot分区哨兵点都选择最后一个数据,那么快排时间复杂度退化为$O(n^2)$。 最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。常用的分区点选择算法:

  1. 三数取中法。从区间的首、尾、中间分别取一个数,然后对比大小,取这三个数的中间值作为分区点。
  2. 随机法。随机选择一个元素作为分区点,从概率的角度来看这种要好一些。

快排性能脆弱点2:快排依赖了递归,警惕堆栈溢出。解决办法:

  • 限制递归深度,一旦超过设定的阈值,就停止递归;
  • 在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程,这样就没有了系统栈大小的现在。

堆排序

2. 非基于比较排序

时间复杂度$O(n)$
桶排序
计数排序
基数排序

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×