ソートの選択

ソートの選択

ソートを選択することは、合計をクエリーし、最も前の数を最小値で交換し、前から入力するソート方法です.

まず、最初の位置(すなわち9が位置する位置)をiとし、jはiから配列の最小インデックス(minIndex)を抽出する.j 8から配列の探索を開始し,最小のインデックスを見つけ,1が存在する位置が最小であることを発見する.だからminIndexは2(1が存在する配列要素の位置!).最初の位置は1です

そして,2番目の位置(8がある位置)はi,jが最小の要素でインデックスを求め,minIndexが2の位置,すなわち4となる.minIndexとiの置換

次は9の位置です.iが2になる.最小インデックスは、3が存在する場所であるため、iによって置き換えられます.

次のiは、9を指す1つ追加されます.8がもっと小さいので交換します

今ではすべての比較と交換が終わりました.昇順ソートが表示されます.

時間の複雑さ

繰り返し文→O(N 2)O(N^2)O(N 2)

インプリメンテーション

class Solution {
    public int[] selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = 2147483647, idx = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    idx = j;
                }
            }
            // 앞의 최소값이 있어야할 자리에 이미 최소값이 있지 않은 경우
            if (i != idx) {
                nums[idx] = nums[i];
                nums[i] = min;
            }
        }
        return nums;
    }
}