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

冒泡排序是很形象的一種排序方案，這裡就不多談了，但是它和快排的關系是什麼呢？實際上快排可以看成是兩個方向的冒泡排序，冒泡排序的過程是在一個方向伸展，最終到底的那個元素一定是個最值，它是以全局最值為基礎的，最值最終冒泡到端點，而快排則不然，它是以資料為中心的，它不求最終能找個最值，而是最終能定位目前資料，快排的運氣性更加強一些，如果你每次都能猜到待排資料的中值，那麼整個排序很快就能完成。快排的本質就是在兩個方向夾逼目前的基準元素，目的就是定位目前元素的最終位置，想想看如果你一開始就猜的值就在它最終的位置，那麼就不用翻箱倒櫃移動或者交換資料了，不像冒泡排序，它不是以資料位置為中心，而是最終一定将最值放到端點，那麼它交換資料或移動資料就比較多，而快排一開始就注重資料的最終位置，是以按照機率來講交換或者移動資料的幾率就不大。

對于時間複雜度的計算以及排序算法的使用場合，考慮一下歸并排序是基于遞歸的，時間複雜度可以通過主定理得到，對于歸并排序而言這個事實更簡單，用樹就可以看出來是nlogn，而對于n^2複雜度的比如插入排序，資料量越大歸并排序的優勢越明顯。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274007