北京pk10网站建设,新洲网站建设,福田瑞沃前四后四车价格,济南网站建设方案服务就这么跟你说吧#xff0c;面试中肯定会出排序算法的算法题#xff0c;你只需要背下来代码背下来他们的时间复杂度和空间复杂度就能蒙混过关。 不管你是前端还是后端#xff0c;关于排序的算法有且仅有这 10个#xff0c;如果你用心了#xff0c;怎么会记不住呢。看完这篇… 就这么跟你说吧面试中肯定会出排序算法的算法题你只需要背下来代码背下来他们的时间复杂度和空间复杂度就能蒙混过关。 不管你是前端还是后端关于排序的算法有且仅有这 10个如果你用心了怎么会记不住呢。看完这篇文章你还没记住就说明你是笨蛋。 好吧最最坏的情况下也需要记住这个8【冒泡、选择、插入、希尔、归并、快速、桶、堆】 可以把所有排序分成三类
第一类【冒泡 选择 插入 希尔】重点是使用【循环交换】
第二类【归并 堆排序 快速】重点是【辅助函数 递归】
第三类【快速排序】他自己一组说明很重要使用【递归思想】
第三类【计数 桶 基数】重点是使用【额外空间桶】
一、循环交换
1.1 冒泡排序 这个是你必须会的我记得之前最先学的就是这个算法因为他最简单但是因为他的时间复杂度大所以考的概率确实最小的但是你怎么可以不会这么简单的排序呢 冒泡排序分为三个一个是基本的冒泡排序二个改进的冒泡排序我建议是至少记住一个基本的一个改进的。冒泡排序的时间复杂度都是 on^2 改进的冒泡排序你一定要学会因为如果你在面试中答了简单的冒泡排序面试官一定会问你有没有什么地方可以优化如果你一步到位写出改进的冒泡排序说不定人家就放过你了。 1.1.1 基本的冒泡排序
记住一个关键字【双层 for 循环】
外层 for 循环 i len内层 for 循环 j 初始化为 0j len - i - 1使用内层 for 循环交换元素时间复杂度是 n^2 因为有两层 for 循环注意是升序排序还是降序排序
function bubbleSort(arr) {let len arr.lengthfor (let i 0; i len; i) {for (let j 0; j len - i - 1; j) {if (arr[j] arr[j 1]) {let temp arr[j 1]arr[j 1] arr[j]arr[j] temp}}}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));
1.1.2 改进的冒泡排序
记住关键子【while 循环 for 循环 pos 位置信息】
设置一个位置信息 pos 记录每趟排序中最后一次进行交换的位置pos 初始化为0 在 while 循环内初始化每次循环都重置pos 位置之后的记录均已经交换到位在交换的时候 if 语句内更新 pos内层 for 循环 j i 在下一趟排序时只需要扫描到 pos 位置即可【说明 posm是用来改变循环终止位置的】注意 while 循环一定要有更改 while 循环条件的语句这里就使用 pos 时间复杂度还是为O(N^2) function bubbleSort(arr) {let i arr.length - 1while (i 0) {let pos 0for (let j 0; j i; j) {if (arr[j] arr[j 1]) {// 记录位置pos jlet temp arr[j 1]arr[j 1] arr[j]arr[j] temp}}// 更改 while 循环条件i pos}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));
1.1.3 终极版的冒泡排序
关键值【while 循环和2个for循环 下标 最大值和最小值】
这个是在 1.2 的基础上再进行优化的关键是使用最大值和最小值的概念【这里是指的下标的最大最小值】正向冒泡找到最大值反向冒泡 找到最小值2个 for 循环不是双层 for 循环while 循环条件是 low high 所以内部有high-- low 的语句要定义四个变量排序趟数几乎减少了一半
function bubbleSort(arr) {let low 0;let high arr.length - 1let temp, jwhile (low high) {// 注意这个是 j 1 和 j 的交换for (j low; j high; j) {if (arr[j] arr[j 1]) {temp arr[j 1]arr[j 1] arr[j]arr[j] temp}}high--// 这个 for 循环是 j - 1 和 j的交换for (j high; j low; j--) {if (arr[j - 1] arr[j]) {temp arr[j - 1]arr[j - 1] arr[j]arr[j] temp}}low}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));1.2 选择排序
重点【双层 for 循环】
找到数据结构中的最小值并把放在第一位。选择排序的时间复杂度也是O(n^2)也是使用 双层的for循环外层 for 循环交换当前值和 最小值外层循环小于 len - 1,因为内层循环初始化为i1内层 for 循环用来寻找最小值【j i 1】使用 minIndex 存最小值的下标初始化为 i
function selectSort(arr) {let len arr.lengthlet temp, minIndexfor (let i 0; i len - 1; i) {minIndex ifor (let j i 1; j len; j) {if (arr[j] arr[minIndex]) {minIndex j}}temp arr[i]arr[i] arr[minIndex]arr[minIndex] temp}return arr}
var arr [1, 10, 8, 2, 30];
console.log(selectSort(arr));1.3 插入排序
这个插入排序也一定要会
重点【外层 for 内层 while 】
时间复杂度依旧为 O(n^2)外层使用 for 循环初始化 i 1【这就意味着使用j-1】内层使用 while 循环 j i关键是 while 循环的条件 比较放在 while 循环的条件中 arr[j-1] arr[i]使用的是 j - 1, j--交换发生在 for 循环中适用于排小数组
function insertSort(arr) {let len arr.lengthlet tempfor (let i 1; i len; i) {temp arr[i]let j iwhile (j 0 arr[j - 1] temp) {arr[j] arr[j - 1]j--}arr[j] temp}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(insertSort(arr));
1.4 希尔排序
希尔排序可以说是特殊的插入排序
重点是有一个【间隔 while 循环 for 循环 while 循环】
gap 初始化为 len /2更新 gap gap /2while 循环条件是 gap 0在插入排序的基础上外面加了一个 gap 的while循环gap 是for 循环的初始值【普通插入排序是1】插入排序的 j-1 变成 j -gap大幅减少数据移动的次数
function shellSort(arr) {let len arr.lengthlet gap Math.floor(len / 2)while (gap 0) {for (let i gap; i len; i) {const temp arr[i]let j iwhile (j gap arr[j - gap] temp) {arr[j] arr[j - gap]j - gap}arr[j] temp}gap Math.floor(gap / 2)}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(希尔排序, shellSort(arr));
二、辅助函数递归
2.1 归并排序
重点【两个函数 递归】
时间复杂度是O(nlogn)将整个数组分为两个数组对两个数组分别使用递归调用两次写一个辅助函数第二个函数类似合并两个有序数组【使用双指针】最后调用辅助函数
function merge(left, right) {let res []let i 0, j 0while (i left.length j right.length) {if (left[i] right[j]) {res.push(left[i])i}else {res.push(right[j])j}}if (i left.length) {res res.concat(left.slice(i))}if (j right.length) {res res.concat(right.slice(j))}return res
}
function mergeSort(arr) {let len arr.lengthif (len 2) {return arr}let middle Math.floor(len / 2)let left arr.slice(0, middle)let right arr.slice(middle)return merge(mergeSort(left), mergeSort(right))
}
var arr [1, 10, 8, 2, 30];
console.log(mergeSort(arr));
2.2 堆排序
重点是【3个函数递归】
总共需要3个函数其中两个辅助函数一个构建最大堆一个调整堆每个函数都需要调用调整堆的函数 heapifyheapify 递归调用自身两个 for 循环都是递减的堆的性质在一个最大堆或最小堆中堆顶元素总是数组中最大或最小的元素时间复杂度是O(n log n) function heapSort(arr) {// 构建最大堆buildMaxHeap(arr);// 从最后一个非叶子节点开始向上调整堆for (let i arr.length - 1; i 0; i--) {// 将堆顶元素最大值与当前未排序部分的最后一个元素交换[arr[0], arr[i]] [arr[i], arr[0]];// 调整堆使其满足最大堆性质heapify(arr, 0, i);}return arr;
}// 构建最大堆
function buildMaxHeap(arr) {const len arr.length;// 从最后一个非叶子节点开始向上调整堆for (let i Math.floor(len / 2) - 1; i 0; i--) {heapify(arr, i, len);}
}// 调整堆
function heapify(arr, i, len) {let largest i; // 当前节点const left 2 * i 1; // 左子节点const right 2 * i 2; // 右子节点// 如果左子节点比当前节点大则更新最大值索引if (left len arr[left] arr[largest]) {largest left;}// 如果右子节点比当前节点大则更新最大值索引if (right len arr[right] arr[largest]) {largest right;}// 如果最大值索引不是当前节点则交换节点并递归调整堆if (largest ! i) {[arr[i], arr[largest]] [arr[largest], arr[i]];heapify(arr, largest, len);}
}var arr [1, 10, 8, 2, 30];
console.log(堆-排序, heapSort(arr));
三、快速排序 快速排序是一定一定会考的频率最高的算法就算被也要背下来你看他的名字里面有快速两个字就说明他的重要性。 通过一趟排序将待排序记录分割成独立的两部分其中一步跟记录的关键字均比另一部分的关键字小则可分别将两部分记录继续进行排序达到整个序列有序。
关键字【分治法 递归】
时间复杂度为 O(nlogn)有一个基准每次递归只初始化一次基准不会手动修改有一个小于基准的数组一个大于基准的数组有一个 for 循环有一个 continue 语句在函数返回的地方使用递归
function quickSort(arr) {if (arr.length 1) {return arr}let baseIndex Math.floor(arr.length / 2)let base arr[baseIndex]let less []let greater []for(let i 0; i arr.length; i ) {if (i baseIndex) {continue}if(arr[i] base) {less.push(arr[i])} else {greater.push(arr[i])}}return [...quickSort(less), base, ...quickSort(greater)]
}
var arr [1, 10, 8, 2, 30];
console.log(quickSort(arr));四、额外桶空间
4.1 计数排序
分布式排序使用一个用来存储每个元素在原始数组中出现次数的临时数组在所有元素都计数完成后临时数组已排好序,并可以带以构建排序后的结果数组
重点【找到最大值和最小值一个计数数组】
时间复杂度是O(ok)k是临时计数数组的大小找出数组中的最大值最小值计算每个元素的出现次数 arr[i] -min 计数数组重建排序后的数组适用于整数数组的排序
function countSort(arr) {// 找出最大值和最小值let min max arr[0]for (let i 1; i arr.length; i) {if (arr[i] min) {min arr[i]}if (arr[i] max) {max arr[i]}}// 由于是计数排序适用于整数数组所以这样初始化数组const countArr new Array(max - min 1).fill(0)for (let i 0; i arr.length; i) {countArr[arr[i] - min] // 用数组下标对应一个元素}// 结果数组的 indexlet sortedIndex 0for (let i 0; i countArr.length; i) {while (countArr[i] 0) {// 因为计数数组中减去了 min// 所以这里面要使用循环的下标 i 加上 最小值 minarr[sortedIndex] i minsortedIndexcountArr[i]--}}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(countSort(arr));
4.2 桶排序
也是分布式排序重点是【分桶插入排序】
和计数排序一样先找到最大值和最小值 最大最小值用于计算桶的个数最小值还用于把元素加入桶有两个函数第一个个函数将元素分成不同的桶 有两个参数第二个参数是桶的大小将元素插入桶重点是计算bucketIndex (arr[i]-min )/ bucketSize第二个函数对桶进行排序使用插入排序因为插入排序用来排小数组不错时间复杂度 O(nk) function bucketSort(arr, bucketSize 5) {if (arr.length 0) {return arr}let min arr[0]let max arr[0]for(let i 1; i arr.length; i) {if(arr[i] min) {min arr[i]}if (arr[i] max) {max arr[i]}}const bucketCount Math.floor((max- min)/bucketSize ) 1const bucketArr Array.from({length: bucketCount}, () [])for(let i 0; i arr.length; i) {let bucketIndex Math.floor((arr[i] - min) / bucketSize)bucketArr[bucketIndex].push(arr[i])}let sortedArr []for(let i 0; i bucketArr.length; i ) {insertSort(bucketArr[i])sortedArr.push(...bucketArr[i])}return sortedArr
}
var arr [1, 10, 8, 2, 30];
console.log(bucketSort(arr));
4.3 基数排序
重点是【获取最大数的位数桶的个数时基数的大小】
需要获取数组中的最大值桶的个数时基数的大小通常是10进制就是10使用一个辅助函数获取指定位置上的数字时间复杂度是 O(nk)
function radixSort(arr) {let maxNum Math.max(...arr)let maxLen ${maxNum}.length// 通常创建桶的数量是基数的大小// Array.from 的第二个参数时map函数依次迭代let buckets Array.from({ length: 10 }, () [])// 获取数字num的指定位数上的数字const getDigit (num, digit) {// Math.pow返回基数得幂return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10}for (let i 0; i maxLen; i) {for (let j 0; j arr.length; j) {let digit getDigit(arr[j], i)buckets[digit].push(arr[j])}arr [].concat(...buckets)for (let j 0; j 10; j) {buckets[j] []}}return arr
}
var arr [1, 10, 8, 2, 30];
console.log(radixSort(arr));
