冒泡排序、選擇排序、插入排序 | JavaScript 中的資料結構與演算法-js教程-PHP中文網

首頁

web前端

js教程

冒泡排序、選擇排序、插入排序 | JavaScript 中的資料結構與演算法

Sep 03, 2024 am 11:43 AM

Bubble Sort, Selection Sort, Insertion Sort | Data Structures & Algorithms in JavaScript

排序演算法是許多計算任務的支柱，在組織資料以實現高效存取和處理方面發揮著至關重要的作用。無論您是剛開始探索演算法世界的初學者，還是希望刷新知識的經驗豐富的開發人員，了解這些基本排序技術都是至關重要的。在這篇文章中，我們將探討一些更基本的排序演算法 - 冒泡排序、選擇排序和插入排序。

冒泡排序

冒泡排序是一種簡單的、基於比較的排序演算法。它重複遍歷列表，比較相鄰元素，如果順序錯誤則交換它們。這個過程一直持續到不再需要交換為止，表示清單已排序。雖然冒泡排序易於理解和實現，但對於大型資料集效率較低，因此它主要適用於教育目的和小型資料集。

冒泡排序的時間複雜度為O(n²).

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function bubbleSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i &lt; n; i++) {
    // loop through all n-1 pairs
    for (let j = 0; j &lt; n-1; j++) {
      // if a &gt; b, swap; else do nothing
      if (sortedArray[j] &gt; sortedArray[j+1]) {
        const temp = sortedArray[j]
        sortedArray[j] = sortedArray[j+1]
        sortedArray[j+1] = temp
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", bubbleSort(inputArray))

登入後複製

選擇排序

選擇排序是一種簡單的、基於比較的排序演算法。它的工作原理是將清單分為已排序區域和未排序區域。它反覆從未排序區域中選擇最小（或最大）元素，並將其與第一個未排序元素交換，逐漸增加排序區域。選擇排序對於大型資料集來說並不是最有效的，但很容易理解，並且具有最小化交換次數的優點。

選擇排序的時間複雜度為 O(n²).

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function selectionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i &lt; n; i++) {
    // start from i'th position
    let lowestNumberIndex = i
    for (let j = i; j &lt; n-1; j++) {
      // identify lowest number
      if (sortedArray[j] &lt; sortedArray[lowestNumberIndex]) {
        lowestNumberIndex = j
      }
    }

    // swap the lowest number with that in i'th position
    const temp = sortedArray[i]
    sortedArray[i] = sortedArray[lowestNumberIndex]
    sortedArray[lowestNumberIndex] = temp
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", selectionSort(inputArray))

登入後複製

插入排序

插入排序是一種直覺的、基於比較的排序演算法，一次建構一個元素的最終排序清單。它的工作原理是從清單的未排序部分中獲取元素並將它們插入到已排序部分中的正確位置。插入排序對於小型資料集或接近排序的資料非常有效，並且在實際應用中經常用作更複雜演算法的更簡單替代方案。

插入排序的時間複雜度為O(n²).

function insertionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times, starting at index 1
  for (let i = 1; i &lt; n; i++) {
    // start at index 1
    const comparedNumber = sortedArray[i]
    let tempIndex = i

    // compare with previous numbers (right to left)
    for (let j = i-1; j &gt;= 0; j--) {
      // if number in current index is larger than compared number, swap
      if (sortedArray[j] &gt; comparedNumber) {
        sortedArray[tempIndex] = sortedArray[j]
        sortedArray[j] = comparedNumber
        tempIndex = j
      } else {
        // OPTIONAL: else exit
        break
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", insertionSort(inputArray))

登入後複製