需要有肌肉记忆的五种排序方法 | 刷题打卡
分类:javascript
本文正在参与掘金团队号上线活动,点击 查看大厂春招职位
chrome v8 在处理 sort
方法时,使用了插入排序和快排两种方案。当目标数组长度小于 10 时,使用插入排序;反之,使用快排。
所以对我们来说是有必要了解一下这些排序方法的,这些方法有时候也是做其他算法题的基石。
题目描述
给你一个整数数组 nums,请你将该数组升序排列。
示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]
示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]
来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/so…
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
冒泡排序
思路
- 比较两个相邻的元素,然后根据条件不断的交换位置(重点:不断比较相邻的两个元素)
- 每一轮下来最大的或者最小的值就会在末尾了
- 执行
n-1
轮这个过程就好了
图片来源:visualgo.net/zh/sorting
题解
function bundleSort (arr) {
// 一共需要遍历n轮
for (let i = 0; i < arr.length; i += 1) {
// 因为每一轮都会把最大的值放到末尾,所以下次遍历的时候,就不用遍历到排序好的下标处了
// 所以这里用了arr.length - 1 - i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换位置
const tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
};
选择排序
思路
- 假设数组的开头是最小值的下标,然后每次遍历的时候更新最小值
- 内层循环就是找到每轮中最小的,然后对调位置
- 外层循环就是不断重复内层循环的操作,直到所有值排列完毕
- 将最小值与当前遍历的数组头部做交换
- 每一轮结束都会将最小值放到头部,所以下次遍历的时候要将排序好的排除掉
图片来源:visualgo.net/zh/sorting
题解
function selectSort(arr) {
// 遍历n轮
for (let i = 0; i < arr.length; i += 1) {
// 找到当前数组范围内的最小值的小标
let minIndex = i;
for (let j = i; j < arr.length; j += 1) {
// 找到最小的
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 如果最小值下标和头部下标不同就进行交换
if (minIndex !== i) {
const tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
};
插入排序
思路
- 插入排序就是从数组的第二项开始,与它前面的值进行比较
- 如果比前面的值小,就将前一位的值往后挪
- 然后继续拿这个值与前面的进行比较,直到遇到比他小的,进行插入
说是插入排序,其实感觉就是暂定一个值,然后不断的与他前面的值进行比较,如果前面的值大,那就挪到下一位(这里的挪其实就是让
arr[i+1] == arr[i]
).
直到找到比他小的值或者是下标为 0 的时候就停止,将当前坐标的值更改为我暂定的这个值(这一步就是插入)
图片来源:visualgo.net/zh/sorting
题解
function insertSort(arr) {
for (let i = 1; i < arr.length; i += 1) {
// 选择一个值与他前面的值进行比较
let p = i;
const tmp = arr[p];
// 遍历在他前面的所有值
while (p) {
// 如果选择的这个值要小,就将前面的值后移
if (tmp < arr[p - 1]) {
arr[p] = arr[p - 1];
} else {
// 否则就跳出循环
break;
}
// 将坐标不断前移比较
p -= 1;
}
arr[p] = tmp;
}
};
归并排序
思路
- 分
- 找出中点,递归将数组一分为 2,直到数组中被分的只剩一个元素
- 合
- 新建一个数组,将分好的元素的头部进行比较,按照规则取出队头放入 res 中
题解
function mergeSort(nums) {
// 创建递归函数
const innerSort = (nums) => {
// 递归的出口,数组中剩一个元素的时候返回
if (nums.length === 1) return nums;
/** ================分================*/
// 找中点
const mid = Math.floor(nums.length / 2);
// 分为左半部分
const left = nums.slice(0, mid);
// 分为右半部分
const right = nums.slice(mid, nums.length);
// 递归进行分,在这里分好的是已经执行了下面“合”操作的,所以已经是排序好的数组了
const orderLeft = innerSort(left);
const orderRight = innerSort(right);
/** ================合================*/
// 创建数组进行接收
const res = [];
// 遍历
while (orderLeft.length || orderRight.length) {
// 左右数组都存在值的情况
if (orderLeft.length && orderRight.length) {
// 谁小谁就出队,压入res中
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
} else if (orderLeft.length) {
// 只有左侧有值时就将剩余的值不断压入res中即可
res.push(orderLeft.shift());
} else {
// 只有右侧有值时不断压入res
res.push(orderRight.shift);
}
}
// 返回结果
return res;
};
// 调用函数
return innerSort(nums);
}
复杂度
前面几种的复杂度都比较好分析,归并排序的复杂度我们注意一下:
- 时间复杂度: O(n*logn)
- 分: O(logN)
- 和: O(n)
- 空间复杂度:O(n) 数组的长度
快速排序
思路
- 找到基准点(通常使用数组的开头)
- 把基准点后面的值进行与基准值比较,如果比基准小就放入左侧,否则放入右侧
- 将左、基准、右侧组合成新数组
- 递归执行上面的步骤
题解
function quickSort(nums) {
const innerQuickSort = (arr) => {
// 如果当前数组只要一个值或者没有值,直接返回即可
if (arr.length <= 1) return arr;
// 左侧分区
const left = [];
// 右侧分区
const right = [];
// 基准点
const base = arr[0];
// 从当前数组的第二项开始与基准点进行比较
for (let i = 1; i < arr.length; i += 1) {
// 如果比基准点小,就放入左侧
if (arr[i] < base) {
left.push(arr[i]);
} else {
// 比基准点大,就放入右侧
right.push(arr[i]);
}
}
// 进行递归
const orderLeft = innerQuickSort(left);
const orderRight = innerQuickSort(right);
// 讲排序好的数组组合在一起
return [...orderLeft, base, ...orderRight];
};
return innerQuickSort(nums);
}
总结
排序算法可以说是算法入门的敲门砖了,而且我们日常工作中会有很多涉及到排序的东西,虽然我们已经有了现成的方法可以去调用,但是还是需要知道这下面存在的猫腻,退一万步说如果面试官不让你用现成的你怎么办(狗头保命)
一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu