9.6.1?變不可能為可能

??????? 給大家出一道智力題。請問“VII”是什么？
??????? 嗯，很好，它是羅馬數字的7。現在我們要給它加上一筆，讓它變成8（VIII），應該是非常簡單，只需要在右側加一豎線即可。
??????? 現在我請大家試著對羅馬數字9，也就是“IX”增加一筆，把它變成6，應該怎么做？
??????? （幾分鐘后）
??????? 我已經聽不少聲音說，“這怎么可能！” 可為什么一定要用常規方法呢？
??????? 我這里有三種另類的方法可以實現它。
??????? 方法一：觀察發現“X”其實可以看作是一個正放一個倒置兩個“V”。因此我們，給“IX”中間加一條水平線，上下顛倒，然后遮住下面部分，也就是說，我們所謂的加上一筆就是遮住一部分，于是就得到“VI”。

?

??????? 方法二：在“IX”前面加一個“S”，此時構成一個英文單詞“SIX”，這就等于得到一個6了。哈哈，我聽到下面一片嘩然，我剛有沒有說一定要是“VI”呀，我只說把它變成6而已，至于是羅馬數字還是英文單詞，我可沒有限制。顯然，你們的思維受到了我前面舉例的“VII”轉變為“VIII”的影響。

?

??????? 方法三：在“IX”后面加一個“6”，得到“1X6”，其結果當然是數字6了。大家笑了，因為這個想法實在是過分，把字母“I”當成了數字1，字母“X”看成了乘號。可誰又規定說這是不可以的呢？只要沒違反規則，得到6即可。

?

??????? 智力題的答案介紹完了 。大家會發現，看似解決不了的問題，還真不一定就沒有辦法，也許只是暫時沒想到罷了。
??????? 我們都能理解，優秀排序算法的首要條件就是速度(還有其他要求，速度是第一位的)。于是人們想了許許多多的辦法，目的就是為了提高排序的速度。而在很長的時間里，眾人發現盡管各種排序算法花樣繁多（比如前面我們提到的三種不同的排序算法），但時間復雜度都是O(n²)，似乎沒法超越了（這里排序指內排序）。此時，計算機學術界充斥著“排序算法不可能突破O(n²)”的聲音。就像剛才大家做智力題的感覺一樣，“不可能”成了主流。
??????? 終于有一天，當一位科學家發布超越了O(n²)新排序算法后，緊接著就出現了好幾種可以超越O(n²)的排序算法，并把內排序算法的時間復雜度提升到了O(nlog₂n)。“不可能超越O(n²)”徹底成為了歷史。
??????? 從這里也告訴我們。做任何事，你解決不了時，想一想“Nothing is impossible!”，雖然有點唯心，但這樣思維方式會讓你更加深入的思考解決方案，而不是匆忙的放棄。

9.6.2?希爾排序原理
??????? 現在，我要講解的算法叫希爾排序（Shell Sort）。希爾排序是D.L.Shell于1959年提出來的一種排序算法，在這之前排序算法的時間復雜度基本都是O(n²)的，希爾排序算法是突破這個時間復雜度的第一批算法之一。
??????? 我們前一節講的直接插入排序，應該說，它的效率在某些時候是很高的，比如，我們的記錄本身就是基本有序的，我們只需要少量的插入操作，就可以完成整個記錄集的排序工作，此時直接插入很高效。還有就是記錄數比較少時，直接插入的優勢也比較明顯。可問題在于，兩個條件本身就過于苛刻，現實中記錄少或者基本有序都屬于特殊情況。
??????? 不過別急，有條件當然是好，條件不存在，我們創造條件，也是可以去做的。于是科學家希爾研究出了一種排序，對直接插入排序改進后可以增加效率的方法。
??????? 如何讓待排序的記錄個數較少呢？很容易想到的就是將原本有大量記錄數的記錄進行分組。分割成若干個子序列，此時每個子序列待排序的記錄個數就比較少了。然后在這些子序列內分別進行直接插入排序，當整個序列都基本有序時，注意只是基本有序時，再對全體記錄進行一次直接插入排序。
??????? 此時一定有同學開始疑惑了。這不對呀，比如我們現在有序列是{9,1,5,8,3,7,4,6,2}，現在將它分成三組，{9,1,5}，{8,3,7}，{4,6,2}，哪怕將它們各自排序排好了，變成{1,5,9}，{3,7,8}，{2,4,6}，再合并它們成{1,5,9,3,7,8,2,4,6}，此時，這個序列還是雜亂無序，談不上基本有序，要排序還是重來一遍直接插入有序，這樣做有用嗎？需要強調一下，所謂的基本有序，就是小的關鍵字基本在前面，大的基本在后面，不大不小的基本在中間，像{2,1,3,6,4,7,5,8,9}這樣可以稱為基本有序了。但像{1,5,9,3,7,8,2,4,6}這樣的9在第三位，2在倒數第三位就談不上基本有序。
??????? 問題其實也就在這里，我們分割待排序記錄的目的是減少待排序記錄的個數，并使整個序列向基本有序發展。而如上面這樣分完組后，就各自排序的方法達不到我們的要求。因此，我們需要采取跳躍分割的策略：將相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列內分別進行直接插入排序后得到的結果是基本有序而不是局部有序。

出處：http://www.cnblogs.com/cj723/archive/2011/04/19/2021613.html

總結

以上是生活随笔為你收集整理的《大话数据结构》第9章 排序 9.6 希尔排序（上）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。