您现在的位置是:首页 > Javascript
当前栏目
JS手撕(十) 冒泡排序、插入排序
2023-02-19 12:20:03 时间
JS手撕(十) 冒泡排序、插入排序
冒泡排序
原理
冒泡排序原理就是依次比较相邻元素,如果前面的比后面的大,那就互换位置。从第一对比到最后一对。第一轮比较完最大的数就会浮到最右边,第二轮,第二个大叔浮到倒数第二个位置……
依次针对所有元素执行以上步骤,最后一个不需要,因为已经排好顺序了。
下面的动图来自于菜鸟教程(贴出来主要是为了能更好的理解)
JS实现
实现:
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 如果前面的数比后面的大,那就要互换位置
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
简单讲一下边界的依据:
i < len - 1
:这是因为第一轮排序是轮数,上面也说过需要针对所有元素执行比较相邻元素的步骤,除了最后一个元素。因为已经排完顺序了。所以轮数应该是数组长度-1j < len - 1 - i
:这里的len - 1
和上面的len - 1
是不同原因。len - 1
是因为我们比较的时候是比较arr[j]
和arr[j + 1]
,如果是len
,最后数组会越界。至于后面的- i
就是因为每一轮都会排好一个值,所以就不需要比较已经排好了的。
测试:
小优化
当其中的一趟排序,没有互换过位置的时候,其实就是已经排好序了,但是按上面的程序跑的话,一定要够n-1
趟排序。所以可以定义一个flag
变量,当排序过程中发现已经排序好了(一趟排序中没有互换过位置),直接退出循环。
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 如果前面的数比后面的大,那就要互换位置
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
性能
时间复杂度:O(n²)
排序稳定性:稳定
注:排序稳定性指的是大小相同的两个值在排序前和排序后的先后顺序是否不变。如果是不变的,那就是稳定的,否则是不稳定的。
插入排序
原理
插入排序原理就是每一步将一个待插入元素插入到前面的有序序列的适当位置。(如果待插入元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面,这是为了让插入排序是稳定的)
JS实现
function insertSort(arr) {
const len = arr.length;
let temp;
for (let i = 1; i < len; i++) {
// 从i = 1开始,是因为第一个元素默认是有序的(因为只有一个元素)
// temp是待插入元素
temp = arr[i];
for (let j = i; j >= 0; j--) {
if (temp < arr[j - 1]) {
// 从后向前顺序比较,并依次后移
arr[j] = arr[j - 1];
} else {
// 待插入元素大于等于有序序列元素的时候,插入元素后退出循环
arr[j] = temp;
break;
}
}
}
return arr;
}
测试:
const insertionSort = require('./sort.js');
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 26, 4, 19, 50, 48];
console.log(insertSort(arr))
性能
时间复杂度:O(n²)
排序稳定性:稳定
参考链接
相关文章
- 用自己的编程语言实现了一个网站(增强版)
- JVM 的栈上分配、TLAB、PLAB 有啥区别?
- Webpack中给CSS自动添加前辍
- 深入理解New操作符
- 加入事务和嵌套事务有什么区别?你明白了吗?
- 聊聊 JS 断点的实现
- 如何写一个 JS 运行时
- 同事改Bug飞快,原来掌握了这些代码Debug技巧
- 快速在你的Vue/React应用中实现Ssr(服务端渲染)
- 如何使用流程 中的 DataObject 并为流程设置租户
- 如何实现 JS 运行时的 Inspector 能力
- ES性能优化原理揭秘!初看一脸懵逼,看懂直接跪下
- Web 应用开发是怎么一步一步演变的?
- package.json 配置完全解读
- 老板:你干了五年前端,为什么还犯这个简单的错误?
- 五星红旗国庆头像制作教程来了
- Vite 或 Vue CLI,我该选择哪一个
- 重置期望以更有意义的方式构建和领导
- 客服系统切换中英文多语言 - 使用js更新URL参数来实现切换 【唯一客服】网站网页客服源码教程
- 说透游戏中常用的两种随机算法