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]))

目录