共计 3648 个字符，预计需要花费 10 分钟才能阅读完成。
冒泡排序
在所有排序算法中最简单，然而，从运行时间的角度看，冒泡排序是最差的一个。
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]))
正文完
