JavaScript数据结构与算法(排序算法)

冒泡排序

在所有排序算法中最简单，然而，从运行时间的角度看，冒泡排序是最差的一个。

function swap(array, a, b) {
  const temp = array[a]
  array[a] = array[b]
  array[b] = temp
}

function bubbleSort(array) {
  const { length } = array
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        swap(array, j, j + 1)
      }
    }
  }

  console.log(array)
}

bubbleSort([1, 3, 5, 2, 0])

选择排序

一种原址比较排序算法。选择排序大致思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

function selectionSort(arr) {
  const { length } = arr
  let indexMin
  for (let i = 0; i < length - 1; i++) {
    indexMin = i
    for (let j = i; j < length; j++) {
      if (arr[indexMin] > arr[j]) {
        indexMin = j
      }
    }
    if (i !== indexMin) {
      swap(arr, i, indexMin)
    }
  }

  console.log(arr)
}

selectionSort([1, 3, 5, 2, 0])

插入排序

function insertionSort(array) {
  const { length } = array
  let temp
  for (let i = 1; i < length; i++) {
    let j = i
    temp = array[i]
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1]
      j--
    }
    array[j] = temp
  }

  console.log(array)
}

insertionSort([1, 3, 5, 2, 0])

归并排序

第一个可以实际使用的排序算法。前三个排序算法性能不好，但归并排序性能不错，其复杂度为O(nlog(n))。

归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

function mergeSort(array) {
  if (array.length > 1) {
    const { length } = array
    const middle = Math.floor(length / 2)
    const left = mergeSort(array.slice(0, middle))
    const right = mergeSort(array.slice(middle, length))
    array = merge(left, right)
  }

  return array
}

function merge(left, right) {
  let i = 0
  let j = 0
  const result = []
  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++])
  }
  return result.concat(i < left.length ? left.slice(i) : right.slice(j))
}

console.log(mergeSort([1, 3, 5, 2, 0]))

快速排序

也许是最常用的排序算法了。它的复杂度为O(nlog(n))，且性能通常比其他复杂度为O(nlog(n))的排序算法要好。和归并排序一样，快速排序也使用分而治之的方法，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开）。

function quickSort(arr) {
  const { length } = arr
  if (length < 2) {
    return arr
  }

  let base = arr[0]
  let minArr = arr.slice(1).filter((item) => item <= base)
  let maxArr = arr.slice(1).filter((item) => item > base)

  return quickSort(minArr).concat(base).concat(quickSort(maxArr))
}

console.log(quickSort([1, 3, 5, 2, 0]))

计数排序

是分布式排序。

function countSort(arr) {
  if (arr.length < 2) {
    return arr
  }

  const maxValue = findMax(arr)
  const counts = new Array(maxValue + 1)
  arr.forEach((item) => {
    if (!counts[item]) {
      counts[item] = 0
    }
    counts[item]++
  })

  let sortIndex = 0
  counts.forEach((count, index) => {
    while (count > 0) {
      arr[sortIndex++] = index
      count--
    }
  })

  return arr
}

function findMax(arr) {
  let max = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}

console.log(countSort([1, 3, 5, 2, 0]))

桶排序

也被称为箱排序，是分布式排序算法。它将元素分为不同的桶（较小的数组），再使用一个简单的排序算法，例如插入排序（用来排序小数组不错的算法），来对每个桶进行排序。然后，它将所有的桶合并为结果数组。

function bucketSort(array, bucketSize = 3) {
  if (array.length < 2) {
    return array
  }
  const buckets = createBucket(array, bucketSize)
  return sortBucket(buckets)
}

function createBucket(array, bucketSize) {
  let minValue = array[0]
  let maxValue = array[0]
  for (let i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i]
    } else if (array[i] > maxValue) {
      maxValue = array[i]
    }
  }

  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
  const buckets = []
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = []
  }

  for (let i = 0; i < array.length; i++) {
    const bucketIndex = Math.floor((array[i] - minValue) / bucketSize)
    buckets[bucketIndex].push(array[i])
  }

  return buckets
}

function sortBucket(buckets) {
  const sortedArray = []
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] != null) {
      insertionSort(buckets[i])
      sortedArray.push(...buckets[i])
    }
  }
  return sortedArray
}

function insertionSort(array) {
  const { length } = array
  let temp
  for (let i = 1; i < length; i++) {
    let j = i
    temp = array[i]
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1]
      j--
    }
    array[j] = temp
  }
}

console.log(bucketSort([1, 3, 5, 2, 0]))

基数排序

也是一个分布式排序算法，它根据数字的有效位或基数（这也是它为什么叫基数排序）将整数分布到桶中。基数是基于数组中值的记数制的。

function radixSort(arr) {
  const base = 10
  let divider = 1

  const maxValue = Math.max(...arr)
  while (divider <= maxValue) {
    const buckets = [...Array(10)].map(() => [])
    for (let i of arr) {
      buckets[Math.floor(i / divider) % base].push(i)
    }

    arr = [].concat(...buckets)
    divider *= base
  }

  return arr
}

console.log(radixSort([1, 3, 5, 2, 0]))