ちょくせつせんたくソートアルゴリズム

直接選択ソートアルゴリズムの考え方
無秩序配列a[0...n-1]は、初めてa[0]~a[n-1]から最小値を選択する、a[0]と交換し、2回目はa[1]~a[n-1]から最小値を選択し、a[1]と交換する、...、第i回目はa[i-1]~a[n-1]から最小値を選択し、a[i-1]と交換する、n−1回目はa[n−2]~a[n−1]から最小値を選択し、a[n−2]と交換し、合計n−1回により、キーワードが小さいから大きいまで配列された秩序配列・
直接選択ソートアルゴリズムの手順は次のとおりです.
n=7が与えられ、配列a中の7つの要素は[8,3,2,1,7,4,6]である.

初期状態[8 3 2 1 7 4 6]

第1回目、配列a[0..6]の最小数はa[3]=1、交換a[3]a[0]、交換結果[1 3 2 8 7 4 6]

第2回,配列a[1..6]の最小数はa[2]=2,交換a[2]a[1]、交換結果[1 2 3 8 7 4 6]

第3回,配列a[2..6]の最小数はa[2]=3,交換a[2]a[2]、交換結果[1 2 3 8 7 4 6]

が4回目、配列a[3..6]の中で最小の数はa[5]=4、交換a[5]a[3]、交換結果[1 2 3 4 6 8 7]

第5回、配列a[4..6]の最小数はa[4]=6、交換a[4]a[4]、交換結果[1 2 3 4 6 8 7]

第6回、配列a[5.6]のうち最小の数はa[6]=7、交換a[6]a[5]、交換結果[1 2 3 4 6]

並べ替えが完了しました.
直接選択ソートでは,n−1回の選択と交換が必要であり,選択ごとにn−i回の比較(1<=i<=n−1)が必要であり,交換ごとに最大3回の移動が必要であるため,総比較回数C=(n*n−n)/2,時間複雑度O(n^2)である.直接選択ソートはその場ソート,空間複雑度O(1)である.直接選択ソートは安定したソートアルゴリズムではありません.
アルゴリズム実装
直接選択ソートアルゴリズム擬似コード

//    
SELECTION_SORT(A)
{
  for i=1 to n-1
      min=i
      for j=i+1 to n
          if A[min] > A[j]
             min = j
      swap A[min]  A[i]
}

Test
配列arr[10]={8,5,10,12,7,6,15,9,11,3}を直接選択ソートアルゴリズムで小から大にソートした.

    @Test
    public void sort3() {
        Integer arr[] = { 8, 5, 10, 12, 7, 6, 15, 9, 11, 3 };
        for (int i = 0; i < arr.length; i++) {
            int temp = arr[i];
            int min = arr[i];
            int key = i;
            for (int j = i; j < arr.length; j++) {
                key = arr[j] < min ? j : key;
                min = arr[j] < min ? arr[j] : min;
            }
            if (key != i) {
                arr[i] = arr[key];
                arr[key] = temp;
            }
        }
        //       
        for (Integer it : arr) {
            System.out.print(it + "   ");
        }
    }

しゅつりょく

3   5   6   7   8   9   10   11   12   15