アルゴリズム03ソートデフォルト|選択ソート、バブルソート、挿入ソート|JS

15933 ワード

ソートアルゴリズムのタイプ


simple, slowfastO(N)Selection sort, Bubble sort, Insertion sortQuicksort, Merge sort,Heap sortradix sort

ソート選択|Sortの選択

  • の最大値を見つけて、最後の位置を置き換えます.
  • 時間複雑度:O(n^2)
  • // 오름차순, 최소값을 맨 앞자리와 바꾸는 방식
    function selectionSort(arr) {
      const len = arr.length
      let minIndex = 0
      let temp = 0
      let i = 0
      let j = 0
      for (i = 0; i < len; i++) {
        minIndex = i
        for (j = i + 1; j < len; j++) {
          if (arr[i] > arr[j]) {
            minIndex = j
          }
        }
        temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
      }
      return arr
    }
    
    const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
    console.log(selectionSort(arr))

    バブル整列|Bubble Sort



    画像ソース
    2つの隣接する要素をチェックしてソートする方法
  • 元素の移動が泡状に水面に浮かぶことから
  • と名付けられた.
  • 時間複雑度:O(n^2)
  • // 오름차순
    function bubbleSort(arr) {
      const len = arr.length
      let temp = 0
      let i = 0
      let j = 0
      for (i = 0; i < len; i++) {
        for (j = i + 1; j < len; j++) {
          if (arr[i] > arr[j]) {
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
          }
        }
      }
      return arr
    }
    
    
    const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
    console.log(bubbleSort(arr))

    挿入位置合わせ|挿入Sort



  • リソースアレイ内のすべての要素を、前の順序で配列するアレイ部分と比較し、それらの位置を検索して挿入することによって
  • に並べ替える.
  • 時間複雑度:O(n^2)
  • [挿入位置合わせ](Insert Align)(ドアの冗長性)

    function insertionSort(arr) {
      const len = arr.length
      let temp = 0
      for (i = 1; i < len; i++) {
        for (let j = i - 1; j >= 0; j--) {
          if (arr[i] < arr[j]) {
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
            i--
          }
        }
      }
      return arr
    }
    
    const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
    console.log(insertionSort(arr))

    挿入位置合わせ(文+while文用)


    リファレンス
    function insertionSort(arr) {
      for (let i = 0; i < arr.length; i++) {
        index = i;
        while (arr[index] !== undefined && arr[index - 1] > arr[index]) {
          let temp = arr[index - 1];
          arr[index - 1] = arr[index];
          arr[index] = temp;
          index--;
        }
      }
    }

    📚 リファレンス


    YOUTUBE|2015春学期アルゴリズム|権五鑫
    Photo by Michael Dziedzic on Unsplash