シロ学のアルゴリズム2.2——並べ替えを選択します.

シロ学のアルゴリズム2.2——並べ替えを選択します.
白さんはアルゴリズムを勉強します.
白学アルゴリズム2.xは全部並べ替えアルゴリズムです.この節のすべての並べ替えアルゴリズムは小さい時から大きい順に並べ替えられます.
1.並べ替えアルゴリズムを選択する
優先順位を選択します.時間の複雑度はO(n 2)です.n個の数を選択して並べ替えます.n-1回の並べ替えが必要です.一番小さい数と一番左の数を並べ替えます.
2.並べ替えの選択実現

void bubbleSort(int* A, int n) 
{
    for (int i=0; i<n; i++)// n-1 
    {
        int min = i;
        for (int j=i+1; j<n; j++)//        
            if (A[j] < A[min])
                min = j;

        swap(A, min, i);//  A[min] A[i]    
    }
}

3.まとめ

は、長さnの数列に対して、順序を選択するには、約n 2/2の比較とnの交換

が必要である.

順序付けの運転時間と入力に関係なく選択します.

並べ替え移動要素を選択する回数は、最も少ない

である.

選択順序は、不安定な順序

である.

優先順位は一次順序に属し、時間の複雑度はO(n 2)である.データ量が大きい場合、上位順序

を採用することを提案する.

ランダムデータ量が大きい場合、選択順序は発泡体より速いです.私は発泡体の並べ替え回数が多すぎて、運転時間が長い

を推測します.