前言
排序算法是《数据结构与算法》中最基本的算法之一，本篇使用JavaScript语言实现各种常见排序算法。
排序算法
冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
/**
* 冒泡排序
* @param {*} arr 传入数组
* @returns 结果
*/
function bubbleSort(arr) {
//每轮确定最后一个数的位置，所以内循环的长度减一
for (let j = arr.length; j > 0; j--) {
//实现两个数比较，并大数在后面
for (let i = 0; i < j; i++) {
if (arr[i + 1] && arr[i] > arr[i + 1]) {
let temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
}
}
return arr
}
选择排序
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
/**
* 选择排序
* @param {*} arr 传入数组
* @returns 结果
*/
function selectionSort(arr) {
//每轮确定最后一个数的位置，所以内循环的长度减一
for (let j = arr.length; j > 0; j--) {
//选中最大的数跟最后一个位置的数交换
let index = 0
for (let i = 0; i < j; i++) {
if (arr[i] > arr[index]) {
index = i
}
}
if (j != index) {
let temp = arr[j - 1]
arr[j - 1] = arr[index]
arr[index] = temp
}
}
return arr
}
插入排序
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
/**
* 插入排序
* @param {*} arr 传入数组
* @returns 结果
*/
function insertionSort(arr) {
//循环整个过程，直到所有数排序
for (let i = 0; i < arr.length; i++) {
//取未排序的第一个数，依次与排序后的数（从后往前）做比较
let temp = arr[i]
let j = i
while (j > 0 && temp <= arr[j - 1]) {
arr[j] = arr[j - 1]
j--
}
arr[j] = temp
}
}
归并排序
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
/**
* 归并排序
* @param {*} arr 传入数组
* @returns 结果
*/
function mergeSort(arr) {
//递归出口为单元数组的长度为1
if (arr.length > 1) {
let middleIndex = Math.floor(arr.length / 2)
let left = mergeSort(arr.slice(0, middleIndex))
let right = mergeSort(arr.slice(middleIndex, arr.length))
arr = merge(left, right)
}
return arr
}
function merge(left, right) {
//将两个数组中的数一一比对，按大小顺序整理到新数组中
let result = []
let i = 0
let j = 0
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))
}
快速排序
- 从数列中挑出一个元素，称为 “基准”（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
/**
* 快速排序
* @param {*} arr 传入数组
* @returns 结果
*/
function quickSort(arr) {
//由于递归的参数不同，所以多套一层
return quick(arr, 0, arr.length - 1)
}
function quick(arr, left, right) {
let index
//递归出口为单元数组的长度为1
if (arr.length > 1) {
index = partition(arr, left, right)
if (index - 1 > left) {
quick(arr, left, index - 1)
}
if (index < right) {
quick(arr, index, right)
}
}
return arr
}
function partition(arr, left, right) {
let pivot = arr[Math.floor((left + right) / 2)]
//left为左边第一个数的索引
let i = left
//right为右边最后一个数的索引
let j = right
while (i <= j) {
while (arr[i] < pivot) {
i++
}
while (arr[j] > pivot) {
j--
}
if (i <= j) {
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
i++
j--
}
}
return i
}
计数排序
使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。
/**
* 计数排序
* @param {*} arr 传入数组
* @returns 结果
*/
function countingSort(arr) {
if (arr.length <= 1) return arr
//找到最大值，创建数据结构进行计数
let maxValue = findMaxValue(arr)
let counts = new Array(maxValue + 1)
arr.forEach(element => {
if (!counts[element]) {
counts[element] = 0
}
counts[element]++
})
//出现的次数对应的索引，即为原数组的值
let sortedIndex = 0
counts.forEach((count, index) => {
while (count > 0) {
arr[sortedIndex++] = index
count--
}
})
return arr
}
function findMaxValue(arr) {
let max = arr[0]
for (let i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i]
}
}
return max
}
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
/**
* 基数排序
* @param {*} arr 传入数组
* @returns 结果
*/
function radixSort(arr, radixBase = 10) {
if (arr.length <= 1) return arr
let minValue = findMinValue(arr)
let maxValue = findMaxValue(arr)
let significantDigit = 1
//使用max和min的意义在于减少计算的无效次数
while ((maxValue - minValue) / significantDigit >= 1) {
arr = countingSortForRadix(arr, radixBase, significantDigit, minValue)
significantDigit *= radixBase
}
return arr
}
function countingSortForRadix(arr, radixBase, significantDigit, minValue) {
let bucketsIndex
let buckets = []
let aux = []
for (let i = 0; i < radixBase; i++) {
buckets[i] = 0
}
//记录桶内的数字出现的次数
for (let i = 0; i < arr.length; i++) {
bucketsIndex = Math.floor(((arr[i] - minValue) / significantDigit) % radixBase)
buckets[bucketsIndex]++
}
//使用累加法，计算桶在临时数组中的真实位置
for (let i = 1; i < radixBase; i++) {
buckets[i] += buckets[i - 1]
}
//先自减获取真实下标，再将数据填充进去
for (let i = arr.length - 1; i >= 0; i--) {
bucketsIndex = Math.floor(((arr[i] - minValue) / significantDigit) % radixBase)
aux[--buckets[bucketsIndex]] = arr[i]
}
//将原数组的值替换为临时数组的值
for (let i = 0; i < arr.length; i++) {
arr[i] = aux[i]
}
return arr
}
function findMinValue(arr) {
let min = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i]
}
}
return min
}
桶排序
桶排序（也被称为箱排序）也是分布式排序算法，它将元素分为不同的桶（较小的数组），再使用一个简单的排序算法，例如插入排序（用来排序小数组的不错的算法），来对每个桶进行排序。然后，它将所有的桶合并为结果数组。
/**
* 桶排序
* @param {*} arr 传入数组
* @returns 结果
*/
function bucketSort(arr, bucketSize = 5) {
if (arr.length <= 1) return arr
let buckets = createBuckets(arr, bucketSize)
return sortBuckets(buckets)
}
function createBuckets(arr, bucketSize) {
let minValue = findMinValue(arr)
let maxValue = findMaxValue(arr)
//根据桶容量确定桶数量，创建桶
let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
let buckets = []
for (let i = 0; i < bucketCount; i++) {
buckets[i] = []
}
//将数字分配到桶里
for (let i = 0; i < arr.length; i++) {
let bucketIndex = Math.floor((arr[i] - minValue) / bucketSize)
buckets[bucketIndex].push(arr[i])
}
return buckets
}
function sortBuckets(buckets) {
let sortedArray = []
//每个桶进行插入排序
for (let i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
insertionSort(buckets[i])
sortedArray.push(...buckets[i])
}
}
return sortedArray
}