冒泡排序、选择排序、插入排序 | JavaScript 中的数据结构和算法-js教程-PHP中文网

冒泡排序、选择排序、插入排序 | JavaScript 中的数据结构和算法

WBOY

发布： 2024-09-03 11:43:19

原创

944 人浏览过

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 < n; i++) {
    // loop through all n-1 pairs
    for (let j = 0; j < n-1; j++) {
      // if a > b, swap; else do nothing
      if (sortedArray[j] > 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 < n; i++) {
    // start from i'th position
    let lowestNumberIndex = i
    for (let j = i; j < n-1; j++) {
      // identify lowest number
      if (sortedArray[j] < 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 < 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 >= 0; j--) {
      // if number in current index is larger than compared number, swap
      if (sortedArray[j] > 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))

登录后复制