目录
  1. 1. 前言
  2. 2. 正文
    1. 2.1. Array.prototype.sort
    2. 2.2. 冒泡排序(Bubble Sort)
    3. 2.3. 插入排序(Insert Sort)
    4. 2.4. 快速排序(Quick Sort)
    5. 2.5. 待更新
JS 排序算法总结

前言

现在的前端对计算机基础要求越来越高了,排序和查找也是热门的算法面试题。本篇总结一下前端中的一些排序算法。如果有什么问题或建议,欢迎下方留言评论,共同探讨。


正文

Array.prototype.sort

原生 JS 自身的排序算法 sort(),有其本身的优缺点;

1
2
3
4
5
6
let arr = [1, 20, 10, 22, 11, 24, 100]

console.log(arr.sort())
// [1, 10, 100, 11, 20, 22, 24]
console.log(arr.sort((a, b) => a - b))
// [1, 10, 11, 20, 22, 24, 100]

直接调用会将元素转化成字符串进行排序;可通过传入内部函数来实现升序或排序,内部算法同样是快速排序,在实现上肯定是比我们所使用的快速排序复杂的多,主要是做了性能上的优化。所以,我们可以放心的使用 Array.prototype.sort() 进行排序。


冒泡排序(Bubble Sort)

冒泡排序图解

原理:如名字一般,泡泡越往上越大,循环遍历,每次循环找出一个最大值往最后放;

思路:如图,每次循环能找出一个最大值,每次循环里得比较所有剩余元素,所以需要嵌套循环,一次为比较的轮数(arr.length - 1),一次为每轮的比较次数 (arr.length - 1 - i已经比较的轮数);每次比较前元素比后元素大则交换位置;

性能:

  • 时间复杂度:平均时间复杂度是 O(n^2)
  • 空间复杂度:由于辅助空间为常数,所以空间复杂度是 O(1)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort (arr) {
let temp = 0
// 比较的轮数
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]) {
temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
return arr
}

插入排序(Insert Sort)

插入排序图解

原理:构建有序数列,对未排序元素,在有序数列中的元素从后向前扫描(正向亦可),找到位置并插入;(原理如抽牌一般,抽牌与手中的牌比较,找到位置插入)

思路:嵌套循环,外循环遍历未排序数组,里循环遍历有序数组,未排序元素与有序数组元素从后往前比较,比有序元素大则往后插入,并跳出内循环,继续比较未排序元素;

性能:

  • 时间复杂度:平均算法复杂度为 O(n^2)
  • 空间复杂度:辅助空间为常数,空间复杂度是 O(1)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function insertSort (arr) {
let res = [] // 有序数组
res.push(arr[0]) // 放入第一个元素
// 外循环遍历未排序数组
for (let i=1; i<arr.length; i++) {
// 内循环遍历有序数组
for (let j=res.length-1; j>=0; j--) {
// 原数组元素比新数组元素大,往后插入元素,并跳出内循环
if (arr[i] > res[j]) {
res.splice(j+1, 0, arr[i])
break
}
// 循环到头,未排序元素都比有序元素小,则在头部插入元素
if (j === 0){
res.unshift(arr[i])
}
}
}
return res
}

快速排序(Quick Sort)

快速排序图解

原理:快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。

思路:挑选一个元素作为基准值,循环遍历整个数组,每个元素与基准值比较,分为两个数组,此时递归这两个数组,直到数组中的元素个数小于等于一个,则返回该数组,组合所有数组和基准值及得到有序数组;

性能:

  • 时间复杂度:平均时间复杂度 O(nlogn)
  • 空间复杂度:辅助空间是logn,所以空间复杂度为 O(logn)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quickSort (arr) {
// 当数组元素个数小于等于一个时结束递归
if (arr.length <= 1) {
return arr
}
let arrLeft = []
let arrRight = []
let middleIndex = Math.floor(arr.length/2) // 基准值这里取中间项
let middleValue = arr.splice(middleIndex, 1)[0] // 获取元素,并删除原数组的该元素
// 遍历整个数组,比较放入两个数组中
for (let i=0; i<arr.length; i++) {
arr[i] < middleValue ? arrLeft.push(arr[i]) : arrRight.push(arr[i])
}
// 将两个数组递归调用,并组合数组
return [...quickSort(arrLeft), middleValue, ...quickSort(arrRight)]

// 组合数组用到了 ES6 中的解构赋值,也可使用 Array.prototype.concat 组合数组,如下
// return quickSort(arrLeft).concat(middleValue, quickSort(arrRight))
}

待更新

排序算法还有很多,归并排序、希尔排序等等,后续再总结更新;



文章作者: Vincent F0ng
文章链接: https://vincef0ng.cn/post/javascript-sorting/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Vincent F0ng

评论(支持Markdown)