排序算法之js实现回顾
程序员文章站
2022-03-18 16:02:14
1. 时间复杂度就是while的次数,二分查找O(h)=O(log2n) 2. 节点的广度优先遍历 3. DOM树的深度优先遍历 4. 冒泡排序(O(n^2)) 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该 ......
1. 时间复杂度就是while的次数,二分查找O(h)=O(log2n)
2. 节点的广度优先遍历
function traverse(root){ const queue = [root]; while(queue.length){ const node = queue.shift(); printInfo(node); if(!node.children.length){ continue; } Array.from(node.children).forEach(x=>queue.push(x)); } } function printInfo(node){ console.log(node.nodeName, node.className) } traverse(root)
3. DOM树的深度优先遍历
function printInfo(node, layer){ var str = '' for (let i = 1; i < layer; i++) { str += ' ' } console.log(`${layer}:${str}${node.tagName}.${node.className}`); } function dfs = (rootNodes, rootLayer) => { const roots = Array.from(rootNodes) while (roots.length) { const root = roots.shift(); printInfo(root, rootLayer); if (root.children.length) { dfs(root.children, rootLayer + 1) } } }
4. 冒泡排序(O(n^2))
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
function bubbleSort(arr){ const len = arr.length; for(let i = 0; i < len; 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; }
5. 快排(O(nlogn))
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
var quickSort = function(arr){ if(arr.length <= 1) {return arr;} const midIndex = Math.floor(arr.length / 2); const mid = arr.splice(midIndex, 1)[0]; const left = [], right = []; arr.forEach(function(item){ if(item < mid){ left.push(item); }else{ right.push(item); } }) return quickSort(left).concat([mid], quickSort(right)); }