排序算法之--從插入排序到希爾排序

插入排序是排序中最基本的了，它的效率不高，但是卻比桶排序之類的算法更精妙，本質上此算法開始挖掘程式的時間複雜性，本質上時間複雜性比空間複雜性更重要，如果給我足夠的空間我可以一眼看穿任何事，然而時間卻會越發沖淡一切，時間拖得越久越對解決問題不利，計算機的重要性就在于其機關時間處理問題的能力而不是它能如何好的利用空間，是以比較排序算法是比非比較算法更精密的，循環本質上就是計算機特有的概念，而遞歸則不是，數學上早就有了遞歸的概念，但是數學的發明者--人類卻不會用循環來解決任何問題，是以數學上根本就沒有循環的任何概念，循環意味着一個一個嘗試而不是智能定位，循環意味着需要将大量時間花在循環本身上，是以對于計算機而言，時間是更值得壓縮的而不是空間，空間僅僅與機器的寄存器，cache，記憶體，磁盤，帶寬有關系，而和計算機本身的處理能力關系并不大。

一般的教科書總是将冒泡排序排到最基本的位置，認為那是最傻的算法，其實插入排序更加基本，插入算法實作的很單純，就是将一個元素取出，然後插入到已經排序的序列中，試想如果序列初始本身就是幾乎已經排過序的，那麼速度就會很快，反之如果序列起初是逆序，那麼速度将會極其慢，它慢就慢在每一個元素隻能一個一個和前面的已排序序列比較，而不能一下子跳躍好幾個元素，于是希爾排序解決了這一個問題，希爾排序的精髓在于先将待排序列排序成一個大緻有序的序列，注意這個大緻排序的過程其實也是一系列的插入排序，隻不過不是一個一個移動元素的，而是按照一個步長移動的，效率肯定比一個一個移動要高，比如初始步長為d，按照一個函數遞減d，當d為1的時候，就是普通的插入排序過程，但是此時由于前面比較大的d已經将資料排列的大緻有序了，那麼現在的插入排序就簡單了，而前面的大緻排序的過程比精确排序的開銷要小的多，随着步長d減小，開銷本應增大，但是由于大步長的補償，是以開銷很穩定，這就是希爾排序的精髓，希爾排序的時間複雜度和插入排序一樣，都是O(n^2)，單單從時間複雜度不能看出算法的優劣，各種算法都有自己的适用範圍。

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