Javascriptは発泡体の並べ替えと迅速な並べ替えを実現し、迅速な並べ替えの性能最適化を実現します.

3983 ワード

javascript データ構造とアルゴリズム

泡の並べ替え
紹介する
並べ替えされる要素列を巡回して、2つの隣接する要素を順次比較します.前の要素が後の要素より大きい場合、位置を交換します.昇順で並べ替えられた例では、最大の要素は、最初の遍歴後に配列の端まで泡を作ります.配列長がnの場合、n-1回の巡回後に並べ替えが完了します.
実現する

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function bubbleSort(arr) {
  let time = arr.length - 1
  while (time) {
    let i = 0
    while (iif (arr[i] > arr[i+1]) [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      i ++
    }    
    time --
  }
}

bubbleSort(arr)

クイックソート
紹介する
順序付けによって順序付けされるデータは独立した2つの部分に分割され、そのうちの一部のすべてのデータは他の部分のすべてのデータよりも小さい.その後、この方法によってこれらの2つの部分のデータをそれぞれ高速に並べ替え、順序付けプロセス全体を再帰的に行うことができ、それによってデータ全体が秩序化される.
実現する

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort(arr) {
  if (arr.length <= 1) return arr
  let pivotVal = arr[0],
  smallers = [], 
  biggers = [], 
  idx = 1
  while (idx < arr.length) {
    if (pivotVal > arr[idx]) {
      smallers.push(arr[idx])
    } else {
      biggers.push(arr[idx])
    }
    idx ++
  }
  return quickSort(smallers).concat(pivotVal, quickSort(biggers))
}

quickSort(arr)

この方法はよく理解できます.基準要素を探して、行列の第1位になります.そして、配列を巡回して、基準要素の大きい要素を一時的な配列に入れて、小さなものを別の一時的な配列に投げ込んで、最後にこの二つの配列と基準要素を順番につづり合わせます.もちろん、一時的配列は、最後に生成された一時的配列長が0または1であるまで、内部を分割し続けるために、再帰的に方法を呼び出す必要がある.
次にこの方法を最適化します.結局このようなセットが再帰的に作られ、多くの臨時配列が作られました.性能に一定の影響があります.
最適化

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort2(arr, start, end) {
  while(start >= end) return
  let pivot = start,
  pivotVal = arr[pivot],
  idx = pivot + 1
  while (idx <= end) {
    if (arr[idx] < pivotVal) {
      pivot ++
      if (arr[pivot] != arr[idx]) {
        [arr[pivot], arr[idx]] = [arr[idx], arr[pivot]]
      }
    }
    idx ++
  }
  [arr[pivot], arr[start]] = [arr[start], arr[pivot]]
  quickSort2(arr, pivot + 1, end)
  quickSort2(arr, 0, pivot - 1)
}

quickSort2(arr, 0, arr.length-1)

配列の最初の要素を基準要素とし、2番目の要素から基準要素を比較し、基準要素が小さい場合は基準点を1桁前進させ、同時に現在の基準点の値を比較要素の値と交換するという原理です.一度通過した後、基準要素の位置は基準要素より小さい最後の要素の位置で、右は基準要素より大きいか等しい要素で、左は基準要素より小さい要素である(第一位を除いて、第一位は基準要素である).最後のステップは、現基準点の要素と第一位の要素(基準要素)を動作させることである.基準点と基準要素の対応を確保する.その後再帰的に呼び出したら完了します.
迅速な並べ替えは、単純で効率的ですが、シーケンス長が5から25の間にある場合、直接的に並べ替えの速度を挿入するのは、最低10%の速さで並べ替えられ、改善された急速な並べ替えは、データサイズが25未満の場合、直接挿入順序を採用します.
並べ替えの挿入
紹介する
i番目の要素(i≧1)を挿入すると、arr[0]からarr[i-1]までが整然としていると仮定すると、arr[i]と前の秩序ある数値だけを比較して、自分の挿入すべき位置を見つけることができ、元の位置の要素は一度後にずらされる.
実現する

let arr = [0, 99, 2, 6, 1, 10, 2, 3, 1, 9, 0]

function insertSort(arr) {
  let idx = 1
  while(idx < arr.length) {
    while(idx > 0) {
      if (arr[idx] >= arr[idx-1]) break
      [arr[idx], arr[idx-1]] = [arr[idx-1], arr[idx]]    
      idx --
    }
    idx ++
  }
}

insertSort(arr)

転載先:https://juejin.im/post/5c5698436fb9a049ba420570

Nodeモジュール化