JavaScript 数据结构与算法之美
全栈修炼
算法为王。
想学好前端,先练好内功,只有内功深厚者,前端之路才会走得更远。
笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便以后复习。
之所以把冒泡排序、选择排序、插入排序
放在一起比较,是因为它们的平均时间复杂度都为 O(n2)。
请大家带着问题:为什么插入排序比冒泡排序更受欢迎 ?
来阅读下文。
复杂度分析是整个算法学习的精髓。
时间和空间复杂度的详解,请看 JavaScript 数据结构与算法之美 - 时间和空间复杂度。
学习排序算法,我们除了学习它的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。
分析一个排序算法,要从 执行效率
、内存消耗
、稳定性
三方面入手。
1. 最好情况、最坏情况、平均情况时间复杂度
我们在分析排序算法的时间复杂度时,要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外,你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。
2. 时间复杂度的系数、常数 、低阶
我们知道,时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。
但是实际的软件开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,在对同一阶时间复杂度的排序算法性能对比的时候,我们就要把系数、常数、低阶也考虑进来。
3. 比较次数和交换(或移动)次数
这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。
所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。
也就是看空间复杂度。
还需要知道如下术语:
相等
的元素,经过排序之后,相等元素之间原有的先后顺序不变
。比如:a 原本在 b 前面,而 a = b,排序之后,a 仍然在 b 的前面;相等
的元素,经过排序之后,相等元素之间原有的先后顺序改变
。比如:a 原本在 b 的前面,而 a = b,排序之后, a 在 b 的后面;冒泡
思想
特点
实现
// 冒泡排序(未优化)
const bubbleSort = arr => {
console.time('改进前冒泡排序耗时');
const length = arr.length;
if (length <= 1) return;
// i < length - 1 是因为外层只需要 length-1 次就排好了,第 length 次比较是多余的。
for (let i = 0; i < length - 1; i++) {
// j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了,不需要再比较一次。
for (let j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log('改进前 arr :', arr);
console.timeEnd('改进前冒泡排序耗时');
};
优化:当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不用再继续执行后续的冒泡操作。
// 冒泡排序(已优化)
const bubbleSort2 = arr => {
console.time('改进后冒泡排序耗时');
const length = arr.length;
if (length <= 1) return;
// i < length - 1 是因为外层只需要 length-1 次就排好了,第 length 次比较是多余的。
for (let i = 0; i < length - 1; i++) {
let hasChange = false; // 提前退出冒泡循环的标志位
// j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了,不需要再比较一次。
for (let j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
hasChange = true; // 表示有数据交换
}
}
if (!hasChange) break; // 如果 false 说明所有元素已经到位,没有数据交换,提前退出
}
console.log('改进后 arr :', arr);
console.timeEnd('改进后冒泡排序耗时');
};
测试
// 测试
const arr = [7, 8, 4, 5, 6, 3, 2, 1];
bubbleSort(arr);
// 改进前 arr : [1, 2, 3, 4, 5, 6, 7, 8]
// 改进前冒泡排序耗时: 0.43798828125ms
const arr2 = [7, 8, 4, 5, 6, 3, 2, 1];
bubbleSort2(arr2);
// 改进后 arr : [1, 2, 3, 4, 5, 6, 7, 8]
// 改进后冒泡排序耗时: 0.318115234375ms
分析
原地
排序算法。稳定
的排序算法。动画
冒泡排序动画 4. 插入排序
插入排序又为分为 直接插入排序 和优化后的 拆半插入排序 与 希尔排序,我们通常说的插入排序是指直接插入排序。
一、直接插入
思想
一般人打扑克牌,整理牌的时候,都是按牌的大小(从小到大或者从大到小)整理牌的,那每摸一张新牌,就扫描自己的牌,把新牌插入到相应的位置。
插入排序的工作原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
步骤
实现
// 插入排序
const insertionSort = array => {
const len = array.length;
if (len <= 1) return
let preIndex, current;
for (let i = 1; i < len; i++) {
preIndex = i - 1; //待比较元素的下标
current = array[i]; //当前元素
while (preIndex >= 0 && array[preIndex] > current) {
//前置条件之一: 待比较元素比当前元素大
array[preIndex + 1] = array[preIndex]; //将待比较元素后移一位
preIndex--; //游标前移一位
}
if (preIndex + 1 != i) {
//避免同一个元素赋值给自身
array[preIndex + 1] = current; //将当前元素插入预留空位
console.log('array :', array);
}
}
return array;
};
测试
// 测试
const array = [5, 4, 3, 2, 1];
console.log("原始 array :", array);
insertionSort(array);
// 原始 array: [5, 4, 3, 2, 1]
// array: [4, 5, 3, 2, 1]
// array: [3, 4, 5, 2, 1]
// array: [2, 3, 4, 5, 1]
// array: [1, 2, 3, 4, 5]
分析
原地
排序算法。稳定
的排序算法。动画
insertion-sort.gif
二、拆半插入
插入排序也有一种优化算法,叫做拆半插入
。
思想
折半插入排序是直接插入排序的升级版,鉴于插入排序第一部分为已排好序的数组, 我们不必按顺序依次寻找插入点, 只需比较它们的中间值与待插入元素的大小即可。
步骤
注:x>>1 是位运算中的右移运算,表示右移一位,等同于 x 除以 2 再取整,即 x>>1 == Math.floor(x/2) 。
// 折半插入排序
const binaryInsertionSort = array => {
const len = array.length;
if (len <= 1) return;
let current, i, j, low, high, m;
for (i = 1; i < len; i++) {
low = 0;
high = i - 1;
current = array[i];
while (low <= high) {
//步骤 1 & 2 : 折半查找
m = (low + high) >> 1; // 注: x>>1 是位运算中的右移运算, 表示右移一位, 等同于 x 除以 2 再取整, 即 x>>1 == Math.floor(x/2) .
if (array[i] >= array[m]) {
//值相同时, 切换到高半区,保证稳定性
low = m + 1; //插入点在高半区
} else {
high = m - 1; //插入点在低半区
}
}
for (j = i; j > low; j--) {
//步骤 3: 插入位置之后的元素全部后移一位
array[j] = array[j - 1];
console.log('array2 :', JSON.parse(JSON.stringify(array)));
}
array[low] = current; //步骤 4: 插入该元素
}
console.log('array2 :', JSON.parse(JSON.stringify(array)));
return array;
};
测试
const array2 = [5, 4, 3, 2, 1];
console.log('原始 array2:', array2);
binaryInsertionSort(array2);
// 原始 array2: [5, 4, 3, 2, 1]
// array2 : [5, 5, 3, 2, 1]
// array2 : [4, 5, 5, 2, 1]
// array2 : [4, 4, 5, 2, 1]
// array2 : [3, 4, 5, 5, 1]
// array2 : [3, 4, 4, 5, 1]
// array2 : [3, 3, 4, 5, 1]
// array2 : [2, 3, 4, 5, 5]
// array2 : [2, 3, 4, 4, 5]
// array2 : [2, 3, 3, 4, 5]
// array2 : [2, 2, 3, 4, 5]
// array2 : [1, 2, 3, 4, 5]
注意
:和直接插入排序类似,折半插入排序每次交换的是相邻的且值为不同的元素,它并不会改变值相同的元素之间的顺序,因此它是稳定的。
三、希尔排序
希尔排序是一个平均时间复杂度为 O(nlogn) 的算法,会在下一个章节和 归并排序、快速排序、堆排序 一起讲,本文就不展开了。
思路
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
步骤
实现
const selectionSort = array => {
const len = array.length;
let minIndex, temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (array[j] < array[minIndex]) {
// 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
console.log('array: ', array);
}
return array;
};
测试
// 测试
const array = [5, 4, 3, 2, 1];
console.log('原始array:', array);
selectionSort(array);
// 原始 array: [5, 4, 3, 2, 1]
// array: [1, 4, 3, 2, 5]
// array: [1, 2, 3, 4, 5]
// array: [1, 2, 3, 4, 5]
// array: [1, 2, 3, 4, 5]
分析
原地
排序算法。不稳定
的排序算法。动画
selection-sort.gif
为什么插入排序比冒泡排序更受欢迎 ?
冒泡排序和插入排序的时间复杂度都是 O(n2),都是原地排序算法,为什么插入排序要比冒泡排序更受欢迎呢 ?
这里关乎到 逆序度、满有序度、有序度。
有序元素对:a[i] <= a[j], 如果 i < j。
逆序元素对:a[i] > a[j], 如果 i < j。
同理,对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是 n(n-1)/2* ,也就是满有序度为 15。
原因
复杂性对比
名称 | 最好 | 平均 | 最坏 | 内存 | 稳定性 | 备注 |
---|---|---|---|---|---|---|
冒泡 | n | n2 | n2 | 1 | Yes | ... |
插入 | n | n2 | n2 | 1 | Yes | ... |
选择 | n2 | n2 | n2 | 1 | No | ... |
算法可视化工具
这里推荐一个算法可视化工具。
算法可视化工具 algorithm-visualizer 是一个交互式的在线平台,可以从代码中可视化算法,还可以看到代码执行的过程。
效果如下图。
算法可视化工具
JavaScript 数据结构与算法之美 的系列文章,坚持 3 - 7 天左右更新一篇,暂定计划如下表。
标题 | 链接 |
---|---|
时间和空间复杂度 | https://github.com/biaochenxuying/blog/issues/29 |
线性表(数组、链表、栈、队列) | https://github.com/biaochenxuying/blog/issues/34 |
实现一个前端路由,如何实现浏览器的前进与后退 ? | https://github.com/biaochenxuying/blog/issues/30 |
栈内存与堆内存 、浅拷贝与深拷贝 | https://github.com/biaochenxuying/blog/issues/35 |
递归 | https://github.com/biaochenxuying/blog/issues/36 |
非线性表(树、堆) | https://github.com/biaochenxuying/blog/issues/37 |
冒泡排序、选择排序、插入排序 | https://github.com/biaochenxuying/blog/issues/39 |
归并排序、快速排序、希尔排序、堆排序 | 精彩待续 |
计数排序、桶排序、基数排序 | 精彩待续 |
十大经典排序汇总 | 精彩待续 |
强烈推荐 GitHub 上值得前端学习的数据结构与算法项目 | https://github.com/biaochenxuying/blog/issues/43 |
如果有错误或者不严谨的地方,请务必给予指正,十分感谢。