排序算法之--从冒泡排序到快速排序

  1. 云栖社区>
  2. 博客>
  3. 正文

排序算法之--从冒泡排序到快速排序

科技小能手 2017-11-12 14:22:00 浏览466
展开阅读全文

冒泡排序是很形象的一种排序方案,这里就不多谈了,但是它和快排的关系是什么呢?实际上快排可以看成是两个方向的冒泡排序,冒泡排序的过程是在一个方向伸展,最终到底的那个元素一定是个最值,它是以全局最值为基础的,最值最终冒泡到端点,而快排则不然,它是以数据为中心的,它不求最终能找个最值,而是最终能定位当前数据,快排的运气性更加强一些,如果你每次都能猜到待排数据的中值,那么整个排序很快就能完成。快排的本质就是在两个方向夹逼当前的基准元素,目的就是定位当前元素的最终位置,想想看如果你一开始就猜的值就在它最终的位置,那么就不用翻箱倒柜移动或者交换数据了,不像冒泡排序,它不是以数据位置为中心,而是最终一定将最值放到端点,那么它交换数据或移动数据就比较多,而快排一开始就注重数据的最终位置,因此按照概率来讲交换或者移动数据的几率就不大。

对于时间复杂度的计算以及排序算法的使用场合,考虑一下归并排序是基于递归的,时间复杂度可以通过主定理得到,对于归并排序而言这个事实更简单,用树就可以看出来是nlogn,而对于n^2复杂度的比如插入排序,数据量越大归并排序的优势越明显。



 本文转自 dog250 51CTO博客,原文链接:http://blog.51cto.com/dog250/1274007

网友评论

登录后评论
0/500
评论
科技小能手
+ 关注