選択ソートの実装で、スワップ回数の計算に時間がかかる

Question

static int count = 0; 
for (int i = 0; i < arr.length; i++) { 
    for (int j = i + 1; j < arr.length; j++) { 
     if (arr[i] > arr[j]) { 
      swap(arr, i, j); 
      count++; 
     } 
    } 
} 

これは選択ソートの正しい実装ですか？私はこの実装とのスワップのためにO（n-1）の複雑さを得ていません。

Answer 1

これは選択ソートの正しい実装ですか？

論理的には、実行していることが正しいかどうかです。 「配列の最大値/最小値を見つける」を使ってソートされます。しかし、選択ソートでは、通常、1回の繰り返しで複数のスワップは必要ありませんでした。スワップ

ためのあなただけのあなたは、i番目の要素

私はOを取得していないですし、それを交換終わり、その後、配列内の最大/最小値を保存する（n-1）の複雑さあなたはスワップのn倍を意味しましたか？はい、それは毎回スワップするので、最大の価値だけでなく、より大きな価値を見つけることができます。あなたはこのようなあなたのコードを書き換えることを試みることができます。

static int count=0; 
static int maximum=0; 
for(int i=0;i<arr.length-1;i++){ 
    maximum = i; 
    for(int j=i+1;j<arr.length;j++){ 
     if(arr[j] > arr[maximum]){ 
      maximum = j; 
     } 
    } 
    swap(arr[maximum],arr[i]); 
    count++; 
} 

また、あなたは、n-1回の交換を強要したい場合は、あなたの反復を、私はあまりにも変化しなければならないため。