个人主页: 鑫宝Code 热门专栏: 闲话杂谈｜ 炫酷HTML | JavaScript基础 个人格言: "如无必要，勿增实体"
文章目录
引入正文冒泡排序插入排序选择排序快速排序
引入
这章主要讲的是数组的排序篇，我们知道面试的时候，数组的排序是经常出现的题目。所以这块还是有必要进行一下讲解的。笔者观察了下前端这块的常用算法排序题，大概可以分为如下
冒泡排–> 稳定排序插入排序–> 稳定排序选择排序–> 不稳定排序快速排序–> 不稳定排序
所以笔者在该章节只会讲解这4大排序算法的实现，至于有些读者问如果面试题出了其他的排序算法呢？例如希尔排序,堆排序等，我个人认为如果一家公司给候选人出堆排序，那我觉得他可能就不太想让候选人通过，如果出希尔排序,那我建议你这次面试可以不用面了，因为95%以上是KPI面试。
正文
冒泡排序
冒泡排序工作原理:
比较相邻的元素。如果第一个比第二个大，就交换它们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2) 代码如下：
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
// 每轮循环最后i个元素已经是有序的，所以内层循环可以减去i
for (let j = 0; j < len - 1 - i; j++) {
// 如果前一个元素大于后一个元素，则交换它们的位置
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
// 测试
const arr = [2, 3, 1, 4, 5];
console.log(bubbleSort(arr));
// 输出: [1, 2, 3, 4, 5]
插入排序
插入排序工作原理:
从第一个元素开始，该元素可以认为已经被排序。取出下一个元素，在已经排序的元素序列中从后向前扫描。如果该元素（已排序）大于新元素，将该元素移到下一位置。重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位置后。重复步骤2~5。
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2) 代码如下：
function insertionSort(arr) {
const len = arr.length;
for (let i = 1; i < len; i++) {
const key = arr[i];
let j = i - 1;
// 将arr[i]元素移到已排序部分的正确位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
// 测试
const arr = [2, 3, 1, 4, 5];
console.log(insertionSort(arr));
// 输出: [1, 2, 3, 4, 5]
选择排序
选择排序工作原理：
在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2) 代码如下：
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// 测试
const arr = [2, 3, 1, 4, 5];
console.log(selectionSort(arr));
// 输出: [1, 2, 3, 4, 5]
快速排序
快速排序工作原理：
从数列中挑出一个元素作为基准（pivot），通常选择第一个或最后一个元素。重新排列数列，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
时间复杂度：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 代码如下：
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
相关文章
您阅读本篇文章共花了：
发表评论