整列選択(Selection Sort)

3558 ワード
algorithm テキストリンク

サマリ


まず要素の配置位置を決定し、配置する要素を選択するアルゴリズムです.

プロセス



時間の複雑さ

  • Best Case, Worst Case: O(n^2)
  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

    • くうかんふくざつさ

  • は、与えられた配列において交換順序付けされるので、O(1)

    • 長所

  • アルゴリズムは簡単です.
  • アレイでスワップするため、他のメモリ領域のその場ソートは必要ありません.
  • 安定したソート.

    • 短所

  • は非効率です.
  • 不安定なソート.

    • コード実装

    const selectionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) min = j;
    }
    if (i !== min) [arr[i], arr[min]] = [arr[min], arr[i]];
  }
  return arr;
};
    スレッド例【4】
    タイプスクリプトベースのルータの適用方法[node.js]