集合{1,2、...、n}の順列が与えられます。私はこの並べ替えをソートする必要があります。連続する位置にある要素x、yを交換するコストはmin（x、y）です。例えば並べ替えコスト
総最小のコストは3 ある3,1,2,4 Iの手順（（x、y）は、YとXを交換手段）を行うので、私は順列がある場合：
総費用は、私はSWにより、ブルートフォースを試み3
ありますソートされていないペアがなくなるまで、最小コストのソートされていないペアをアペンドしますが、この方法は明らかに十分速くありません。
私の質問には、自分の条件が満たされている場合の最小の並べ替えコストをどのように見つけるのですか？
このアルゴリズムはinsertion sortのように聞こえます。置換の逆転を排除することに基づく挿入ソート。そして、あなたは、挿入ソートのように逆転を排除することができます。すでにソート済み配列として知られているので、逆転はありません。
挿入ソートアルゴリズムの時間複雑度はO（n + d）です（nは要素数、d - は反転数です）。
順列における反転の最大数はn *（N-1）/ 2であり、最小値はO（N * LG、アレイ内の反転の数を見つけるために、merge sortをmodificatedを使用でき0
ありますn）。
挿入の並べ替えを使用すると、一度に1つ以上のインデックスの要素を移動できます。これは単なるバブルソートです。 http://ja.wikipedia.org/wiki/Bubble_sort –
@Jonathan M、それは実現にかかっています。通常は、スワッピングを使用して移動します。そして、スワップの数は、この要素iの逆数d（i）の数に依存する。リンクされたリストを使用する場合でも、挿入場所を見つけるのにd（i）時間が必要です。 – Alexander
シーケンスをソートする連続番号スワップの数は、逆順のペア数に等しい。
例えば逆の順序で
6 1 3 2 4 5
対を以下に列挙する：配列をソートする
(6,1) (6,3) (6,2) (6,4) (6,5) (3,2)
よう
操作は次のとおり
swap(6,1) 1 6 3 2 4 5
swap(6,3) 1 3 6 2 4 5
swap(6,2) 1 3 2 6 4 5
swap(6,4) 1 3 2 4 6 5
swap(6,5) 1 3 2 4 5 6
swap(3,2) 1 2 3 4 5 6
だから操作は決まっています（無駄な操作をしない限り）。
逆の順序ですべてのペア（x、y）を数え、min（x、y）を合計する必要があります。
はい、このペアは逆転と呼ばれます。そして、ちょうど挿入の並べ替えを示しています。 – Alexander
はい、あなたが正しいと思います。ありがとうございました！ – altair1000
そしてすべてのペアをチェックすることは無差別な二乗解です – Alexander
ここに質問はありません。あなたは何をやっているのか教えてくれました。あなたは何をしたいのですか？ところで、あなたの英語で+1 ...それはとても良いです。 :) –
@JonathanM、質問は明らかです：最適な解決策は何ですか？ – Shahbaz
@ user1385303、bubble-sortが最適でない結果をもたらす例を挙げることができますか？もしあなたが貪欲に交換すれば最小コストを得ることができますが（私はそれを証明する必要があります） – Shahbaz