js自带的排序方法 Array.prototype.sort(compareFunction)
MDN 文档 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort 关于浏览器排序实现相关文章推荐 https://efe.baidu.com/blog/talk-about-sort-in-front-end/
这个方法会把数字转换为字符串再按照字典顺序进行比较, 传入一个函数可以改变其行为
compareFunction 接受两个参数, 表示进行比较的前一项和后一项, 返回一个数字, 用 ts 表示为 fn(a: any, b: any): number
若返回的数字大于0, 则第一个项排在第二个项后面; 其余情况(包括0), 第一个项排在第一个项前面
注意: 这个方法排序产生的结果是不稳定的, 内部实现方式也根据浏览器不同而有所差异
v8 源码中, 在数组长度较小时使用插入排序(稳定), 其余情况使用快速排序(不稳定) https://github.com/v8/v8/blob/ad82a40509c5b5b4680d4299c8f08d6c6d31af3c/src/js/array.js
// 711 行
// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.
// 763 行
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}例子
// 正序排列
const array = [1111, 111, 11]
array.sort((a, b) => a - b) // 倒序时返回 b - a
console.log(array) // [11, 111, 1111]冒泡排序
时间复杂度 O(n) - O(n²), 稳定, 原地
按顺序比较每两个项, 若前一项大于后一项则交换这两个项, 最小的项最终会"冒泡"到最前面。
function bubbleSort(arr) {
for(let i = 0; i < arr.length - 1; i++) {
for(let j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]) {
let temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
return arr
}算法执行两个 for 循环，每一次内层循环结束，就有一个数就被排序到正确的位置。
选择排序
时间复杂度 O(n²), 不稳定, 原地
从未排序的序列中找到最小的元素, 放在序列的起始位置, 重复这个过程。
function selectionSort(arr) {
let minIndex, temp
for(let i = 0; i < arr.length - 1; i++) {
minIndex = i
for(let j = i+1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j
}
}
temp = arr[minIndex]
arr[minIndex] = arr[i]
arr[i] = temp
}
return arr
}算法执行两个 for 循环，每一次内层循环结束，就找到一个最小的元素，和首个元素交换位置。
插入排序
时间复杂度 O(n) - O(n²), 稳定, 原地
将第一个元素看作有序序列, 将后面的元素依次插入到前面的合适的位置形成新的有序序列
function insertionSort(arr) {
let preIndex, current
for(let i = 1; i < arr.length; i++) {
preIndex = i - 1
current = arr[i] // 抽取一个数
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex] // 往前移
preIndex--
}
arr[preIndex + 1] = current // 插回去
}
return arr
}算法执行两个循环，内层循环将后一个数和前面所有数进行比较，插入到有序的位置形成新的有序序列。
希尔排序
希尔排序是对插入排序的优化, 时间复杂度 O(nLogn), 不稳定, 原地
希尔排序先将序列按一定的步长分割成若干子序列进行插入排序, 再逐步缩减步长到1, 步长为1时即为一次插入排序; 希尔排序比插入排序每次循环只能移动一个元素相比, 效率得到了很大的提升，相当于二分法的插入排序。
// 3个 for 一个 if
function shellSort(arr) {
for(let d = Math.floor(arr.length / 2); d > 0; d = Math.floor(d / 2)) {
for(let i = d; i < arr.length; i++) {
for(let j = i - d; j >= 0; j -= d) {
if(arr[j] > arr[j + d]) {
let temp = arr[j + d]
arr[j + d] = arr[j]
arr[j] = temp
}
}
}
}
return arr
}归并排序
时间O(nlogn), 空间O(n), 稳定
归并排序采用分治法, 利用了额外的空间, 比较两个有序的数组并依次选出最小的数, 合并成一个有序的数组, 通过递归把"有序数组"缩小到只有一个元素的情况
// 自上而下的递归, 3个 while
function mergeSort(arr) {
if(arr.length < 2) return arr
let middle = Math.floor(arr.length / 2),
left = arr.slice(0, middle),
right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = [] // 额外空间
while(left.length && right.length) {
if(left[0] <= right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
while(left.length) {
result.push(left.shift())
}
while(right.length) {
result.push(right.shift())
}
return result
}
// 自下而上的迭代, 利用for循环取代递归
function iterativeMergeSort(arr) {
for(let step = 1; step < arr.length * 2; step *= 2) {
for(let left = 0; left + step < arr.length; left += step * 2) { // left + step >= arr.length 时只有左数组, 没有归并的必要
let right = left + step
let arrLeft = arr.slice(left, right), // 左数组
arrRight
// 右数组凑不够, 或刚刚够
if(right + step >= arr.length) {
arrRight = arr.slice(right)
} else {
arrRight = arr.slice(right, right + step) // 右数组
}
let current = left
while(arrLeft.length && arrRight.length) {
if(arrLeft[0] <= arrRight[0]) {
arr[current++] = arrLeft.shift()
} else {
arr[current++] = arrRight.shift()
}
}
while(arrLeft.length) {
arr[current++] = arrLeft.shift()
}
while(arrRight.length) {
arr[current++] = arrRight.shift()
}
}
}
return arr
}快速排序
时间nlogn - n², 空间logn, 原地, 不稳定
快速排序同样采用分治法, 首先以第一个数为基准值, 比基准值小的数放在基准值的左边，比基准值大的数放在基准值的右边。然后对基准值左边的数和右边的数执行同样的过程，直到其中一边只有一个数。
function quickSort(arr, left, right) {
let partitionIndex
left = typeof left === 'number' ? left : 0 // 初始只传入一个 arr
right = typeof right === 'number' ? right : arr.length - 1
if(left < right) {
partitionIndex = partition(arr, left, right) // 分组, 获取中间的基准值的位置, 此时左边数字的比基准值小, 右边的数字比基准值大
quickSort(arr, left, partitionIndex - 1) // 快排左数组
quickSort(arr, partitionIndex + 1, right) // 快排右数组
} // 其他情况说明已经切分到最小单位了, 直接返回
return arr
}
function partition(arr, left, right) {
let pivot = left, // 基准
index = pivot + 1
for(let i = index; i <= right; i++) { // 一开始，指针重合，i是小数指针，index是大数指针，小数指针总是大于等于大数指针
if(arr[i] < arr[pivot]) { // 当前值小于基准值，则两个指针的数字交换位置，把小数和大数交换
swap(arr, i, index)
index ++ // 交换之后，大数指针指的是交换后的小数，因此要后移一位
}
}
swap(arr, pivot, index - 1) // 大数指针的前一位是基准的位置，指针的右边比基准大，左边比基准小，交换
return index - 1 // 返回基准数当前的位置
}
function swap(arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}堆排序
时间复杂度nlogn, 原地, 不稳定
堆排序是利用堆这种数据结构, 把数组理解成一个完全二叉树, 把这棵完全二叉树做成大顶堆(父节点的值大于等于子节点的值); 交换堆顶的数和堆尾的数(把最大的数放到了最后面); 无视最后一个数(认为数组长度-1), 对堆顶进行一次大顶堆的调整, 重复上面两个过程直到数组长度为1
数组就会从堆尾开始变得有序, 大顶堆的话就会排列成递增的数组
// 初始化建立大顶堆
function buildMaxHeap(arr) {
for(let i = Math.floor(arr.length / 2); i >= 0; i--) { // 从有叶节点的节点开始进行堆调整, length / 2 正好是最后一个有叶节点的节点
heapify(arr, i, arr.length)
}
return arr
}
// 堆调整
function heapify(arr, i, len) {
let left = 2 * i + 1, // 左儿子
right = 2 * i + 2, // 右儿子
largest = i
if(left < len && arr[left] > arr[largest]) {
largest = left
}
if(right < len && arr[right] > arr[largest]) {
largest = right
}
if(largest !== i) {
swap(arr, i, largest)
heapify(arr, largest, len)
}
}
function swap(arr, i, j) {
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
function heapSort(arr) {
arr = buildMaxHeap(arr)
for(let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i) // 交换堆顶和堆尾
heapify(arr, 0, i) // 调整堆顶
}
return arr
}计数排序
具有线性时间复杂度, 但要求输入的数据是有确定范围的整数(0 - k), 局限性较大; 以最大的整数+1为总长度创建一个数组(具有0-k下标的数组), 用数组的下标为输入的整数进行计数, 每有一个数k就对下标为k的元素+1, 最终从小到大把数重新列出来; 因此会消耗大量空间
计数排序的时间复杂度为 n+k, 空间复杂度为 O(k), 是稳定的排序算法
function countingSort(arr, maxValue) {
let bucket = new Array(maxValue + 1),
sortedIndex = 0,
arrLen = arr.length,
bucketLen = maxValue + 1
for(let i = 0; i < arrLen; i++) {
if(!bucket[arr[i]]) {
bucket[arr[i]] = 0
}
bucket[arr[i]]++ // 记录下这个数有多少个
}
for(let j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j
bucket[j]--
}
}
return arr
}桶排序
是计数排序的优化版本, 用一个桶(可以装多个元素)取代计数排序中的一个萝卜一个坑的计数方式, 比如0-9放在第一个桶中, 10-19放在第二个桶中, 对每个桶进行分别排序, 再合并, 是否快速关键在于元素能否均匀地分配到各个桶中, 分配的越均匀, 效率越高
设有 k 个桶, 则平均时间复杂度为 n + k, 但最坏的情况(所有数都集中在一个桶中)时间复杂度达到 n², 是稳定的排序算法
function bucketSort(arr, bucketSize = 5) { // bucketSize: 每个桶里面装多少个数据
if(!arr.length) return arr
// 找到数组中的最小值和最大值
let min = arr[0], max = arr[0]
for(let i = 1; i < arr.length; i++) {
if(arr[i] < min) min = arr[i]
else if(arr[i] > max) max = arr[i]
}
// 初始化桶
let bucketCount = Math.floor((max - min) / bucketSize) + 1 // 有多少个桶
let buckets = new Array(bucketCount)
for(let i = 0; i < buckets.length; i++) {
buckets[i] = []
}
// 分配元素到各个桶中
for(let i = 0; i < arr.length; i++) {
buckets[Math.floor(
(arr[i] - min) / bucketSize
)].push(arr[i]) // 分配到桶中
}
let resultArr = []
for(let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]) // 对每个桶进行排序
for(let j = 0; j < buckets[i].length; j++) { // 排序之后就可以直接插入
resultArr.push(buckets[i][j])
}
}
return resultArr
}基数排序
将整数按位切割成不同的数字, 然后按每个位数分别比较, 设 k 是整数的位数, 时间复杂度为 kn, 稳定的排序方法
function radixSort(arr, maxDigit) { // maxDigit: 最大位数
let counter = []
let mod = 10, dev = 1
for(let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { // 按位循环: k
for(let j = 0; j < arr.length; j++) { // 分配到桶里面: n
let bucket = parseInt((arr[j] % mod) / dev)
if(counter[bucket] == null) {
counter[bucket] = []
}
counter[bucket].push(arr[j])
}
let pos = 0
for(let j = 0; j < counter.length; j++) { // 写回数组
if(counter[j]) {
while(counter[j].length) {
arr[pos++] = counter[j].shift()
}
}
}
}
return arr
}示例数组
let arr = [2, 4, 7, 9, 5, 6, 1, 3, 8]