目录前言排序算法冒泡排序选择排序插入排序归并排序快速排序计数排序基数排序桶排序
前言
排序算法是《数据结构与算法》中最基本的算法之一，本篇使用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
}