浙江大學-數據結構-簡單排序-9.1.4

03-06

前面講了冒泡排序和插入排序，它們都是屬於簡單排序，它們都是有公共的時間複雜度下界的，那麼要理解這個問題呢，我們先介紹一個新的概念，叫做逆序對。

就是說如果有下標i是小於j的，但是A[i]是大於A[j],在我們默認從小到大排序的前提下，我們認為A[i]，A[j]這兩個元素是待錯位置了，如果有這種情況，那我們就把這對元素叫做逆序對，或者把它們的下標稱作是一對逆序對，那我們回過頭來看，前一節看的例子，給定了6個數，

數一下，這6個數字中有多少逆序對呢？

一共有9個逆序對，有沒有覺得9這個數字有點熟悉呢？前面我們說了，不管是冒泡排序，還是插入排序，它們做交換的次數，也正好都是9次，為什麼大家都正好是9次呢？這肯定不是一個特別碰巧的事，說明什麼問題呢？說明我們每一次交換元素的時候，都是正好消掉了一個逆序對的，因為前面兩種演算法它們的共同特點是什麼？不管是冒泡還是插入，每次它們都交換2個相鄰的元素，兩個相鄰的元素進行交換正好消去一個逆序對，所有的這一切都不是巧合，因為這裡面有9個逆序對，所以這兩種演算法都必須用9次元素交換才能消掉，於是呢，重新來看一下插入排序的時間複雜度，它的時間複雜度不僅跟元素的個數N相關，而且跟I,I是原始的序列裡面逆序對個數有關，無論如何，它都要把整個的元素從頭到尾掃描一遍，所以它至少是一個O(N)複雜度的，另外，它的操作的次數，是跟它逆序對的個數，成正比的，所以這實際上是一個O(N+I)的複雜度，於是，我們也就看到，如果這個序列裡面的I非常少，換言之，如果這個序列是基本有序的話，那麼插入排序呢，一個是程序非常好寫，而且它還非常快，什麼叫非常快呢，如果逆序對的個數跟這個N是同一個數量級的，甚至比N還要小的話，那麼整個演算法的時間複雜度是線性的，是O(N)數量級的

那麼是一種非常快的排序演算法，那麼對於更一般的情況，我們有下面這樣的定理，也就是說任意N個不同元素組成的序列，平均具有N(N-1)/4個逆序對。也就是逆序對的平均個數是O(N^2)這個數量級的。也就意味著說，不管是冒泡排序，還是插入排序，它們的平均時間複雜度是跟逆序對的個數有關係的。也就得到了我們下面的定理。

就是任何僅以交換相鄰兩元素的來進行排序的演算法，它平均時間複雜度，是 $Omega(N^2)$ ,什麼是 $Omega$ , $Omega$ 指的是下界，也就是說你最好最好也就是N^2這個數量級的複雜度了，這個聽上去是一個壞消息，但是我們要注意到限制是什麼，是以僅以交換相鄰兩元素來排序的演算法，那換句話說，如果我們想要提高演算法效率，我們應該怎麼努力呢？你要注意到前面兩個簡單演算法之所以慢，是因為每一次交換，只能去掉一個逆序對，而它平均有這麼多個逆序對，所以它無論如何都快不了，所以我們想要快的一個很重要的努力目標是每次交換的時候，希望能夠不止消去一個逆序對，那怎麼才能做到這一點呢？如果每次交換都是相鄰兩個元素的話，是做不到這一點的，於是我要想做到這一點，我必須說每次交換的兩個元素應該相隔比較遠，我跳著交換，那麼就有希望在一次交換中，我同時就消掉了好幾個逆序對。這樣演算法就會快起來。