北京网站建设专业公司,wordpress 标签页面,学校网站开发需求,网站建设书引入
这章主要讲的是数组的排序篇#xff0c;我们知道面试的时候#xff0c;数组的排序是经常出现的题目。所以这块还是有必要进行一下讲解的。笔者观察了下前端这块的常用算法排序题#xff0c;大概可以分为如下
冒泡排– 稳定排序插入排序– 稳定排序选择排序–…引入
这章主要讲的是数组的排序篇我们知道面试的时候数组的排序是经常出现的题目。所以这块还是有必要进行一下讲解的。笔者观察了下前端这块的常用算法排序题大概可以分为如下
冒泡排– 稳定排序插入排序– 稳定排序选择排序– 不稳定排序快速排序– 不稳定排序
所以笔者在该章节只会讲解这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个元素已经是有序的所以内层循环可以减去ifor (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)];
}
