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));
}
6. 折半查找（logn）
function halfSearch(target, arr){
let start = 0,
end = arr.length - 1;
while(start <= end){
let mid = parseInt(start + (end - start) / 2); if(target == arr[mid]){
return mid;
}else if(target > arr[mid]){
start = mid+1;
}else{
end = mid-1;
}
}
return -1;
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/7506.html