01/04 - 逆序數對- 演算法的分析與證明

給定一個序列 \(A=(a_1, a_2, \ldots, a_n)\)。

我們說一個數對 \((i, j)\), \(1\le i < j\le n\) 是一個它的逆序數對 (Inversion)，若 \(a_i > a_j\)。

而滿足條件的數對總數，我們寫作 \(\mathrm{Inv}(A)\)。

有了這個定義以後，我們就可以討論當我們限制「每次只能交換相鄰兩數」的排序方法的效率了！泡沫排序法、雞尾酒排序法、與插入排序法當中，交換數對的次數皆相同，而且恰好是 \(\mathrm{Inv}