※ 引述《cutekid (可愛小孩子)》之銘言：
: 給一字串全由字母 A-Z 組成
: 將其依字母順序由小到大排序
: 限定只能相鄰字母兩兩交換
: 問至少要交換幾次
: 能排序完成
: Ex.
: Input : DCBA
: Output: 6
: 請問這有好的算法嗎
: 謝謝 :)
相鄰交換 -> 逆序數 -> 修改merge sort來計算逆序數
-> 基於兩兩比較的排序法都可以算逆序數
這套流程，推文已經講得很清楚了
這裡講另外一個基於 counting sort 與 prefix sum 的方法
int n = 4;
char str[] = "DCBA";
int count[26] = {};
int ans = 0;
for (int i = 0; i < n; ++i)
{
int index = str[i] - 'A';
count[ index ] ++;
// ans += sum( count[index + 1] ... count[26 - 1] );
for (int j = index + 1 ; j < 26; ++j)
ans += count[j];
}
print ans;
時間複雜度 O(n * 26) = O(n)
或者也可以用 binary indexed tree，時間複雜度 O(n * lg(26)) = O(n)
或者也可以用其他的 prefix sum 演算法
由於輸入是有界整數，我猜應該可以做到 O(n * lglg(26))，不過還是 O(n)