※ 引述《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)

推(Y)

已晕 推一下 慢慢看 @_@

推