前言
排序算法是《数据结构与算法》中最基本的算法之一，本篇使用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 } 
