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

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

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

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