整列
データを並べ替えるアルゴリズムについてです。
整列アルゴリズム
下記のようなものがあります。
交換法 O(n2)
隣同士を比較して
順序が逆であれば入れ替えます。
選択法 O(n2)
最大値、最小値を順じ取り出す。
挿入法 O(n2)
整列済み要素の適切な位置に
未整列要素を挿入する処理を繰り返します。
クイックソート O(nlog n)
基準値よりも大きなグループと
小さいグループに分ける。
その後同様の処理を繰り返します。
二分法に近い形です。
マージソート O(nlog n)
整列済みの二つの配列を併合することを
繰り返します。
配列データの2分の1を格納する作業領域が必要です。
シェルソート O(n 1.25)
挿入法の改良版
一定間隔ごとに整列し、感覚を徐々に狭めながら再度整列を繰り返します。
ヒープソート O(nlog n)
ヒープの根を取り出して、ヒープを再構築することを繰り返します。