クイックソート
実用上では最も高速な処理ができる
以下、手順
配列要素が1以下であれば整列済みであるとみなす
ピボット(軸)と呼ばれる要素をその配列から選択する
先頭の要素を選択
その配列全体をピボットより値が大きい配列、ピボットより値が小さい配列の2つに分割する
以上の手順を分割された2つの配列に対して適用する
ピボットより値が小さい配列、ピボット、ピボットより大きい配列と結合して整列
計算量について
ピボットの選び方に依存する
ピボット＝中央値のとき分割回数はlogn回、ピボットとの比較がn回行われるので全体としての計算量はO(nlogn) 関連記事