常用的排序查找

冒泡排序

function bubbleSort(array) {
    let length = array.length;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

选择排序

function selectSort(array) {
    let length = array.length;
    for (let i = 0; i < length; i++) {
        let min = i;
        for (let j = i + 1; j < length; j++) {
            if (array[min] > array[j]) {
                min = j;
            }
        }
        [array[min], array[i]] = [array[i], array[min]];
    }
    return array;
}

插入排序

function insertSort(array) {
    let length = array.length;
    for (let i = 1; i < length; i++) {
        let current = array[i];
        let j;
        for (j = i; j > 0 && array[j - 1] > current; j--) {
            array[j] = array[j - 1];
        }
        array[j] = current;
    }
    return array;
}

归并排序

function merge(left, right) {
    let result = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    if (left.length > 0) {
        result = result.concat(left);
    }
    if (right.length > 0) {
        result = result.concat(right);
    }
    return result;
}
function mergeSort(array) {
    let length = array.length;
    if (length <= 1) return array;
    let mid = Math.floor(length / 2);
    let left = array.slice(0, mid);
    let right = array.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

快速排序

快排的思路是得先找到一个基准值（pivot），然后把数组中比基准值小的数都放到它的左边，把数组中比基准值大的值都放到它的右边，同时返回这个基准值后，再分别对两边的数据进行继续快排，直到排序完成。

function quickSort(array, left, right) {
    let partIndex;
    if (left < right) {
        partIndex = partition(array, left, right);
        quickSort(array, left, partIndex - 1);
        quickSort(array, partIndex + 1, right);
    }
    return array;
}
function partition(array, left, right) {
    let pivot = left,
        index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (array[pivot] > array[i]) {
            [array[index], array[i]] = [array[i], array[index]];
            index++;
        }
    }
    [array[pivot], array[index - 1]] = [array[index - 1], array[pivot]];
    return index - 1;
}
const sortArray = quickSort(array, 0, array.length - 1);

二分法

function half(array, target) {
    let left = 0,
        right = array.length - 1;
    while (left <= right) {
        const mid = Math.floor((right - left) / 2) + left;
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else if (array[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}

二叉树遍历

深度优先遍历

深度优先遍历也可以分为三种：前序遍历（preorder）、中序遍历（inorder）和后序遍历（postorder）。三种方式都类似，实现过程中可以理解为在哪个阶段访问根节点。

// 前序遍历
var preorderTraversal = function(root) {
    let result= [];
    if(!root) return result;
    result.push(root.val);
    result = result.concat(preorderTraversal(root.left));
    result = result.concat(preorderTraversal(root.right));
    return result;
};
// 中序遍历
var inorderTraversal = function(root) {
    let result= [];
    if(!root) return result;
    result = result.concat(preorderTraversal(root.left));
      result.push(root.val);
    result = result.concat(preorderTraversal(root.right));
    return result;
};
// 后序遍历
var postorderTraversal = function(root) {
    let result= [];
    if(!root) return result;
    result = result.concat(preorderTraversal(root.left));
    result = result.concat(preorderTraversal(root.right));
      result.push(root.val);
    return result;
};

广度优先遍历

广度优先遍历的思路是维护一个队列，在每次循环中对当层的元素项进行收集，后续通过先进先出，一个个输出元素项到 ret 目标数组中。

var levelOrder = function(root) {
    let q = [], ret = [];
    if(!root) return ret;
    q.push(root);
    while(q.length !== 0) {
        let currentLevelSize = q.length;
        ret.push([]);
        for(let i=0; i<currentLevelSize; i++) {
            const node = q.shift();
            ret[ret.length-1].push(node.val);
            if(node.left) q.push(node.left);
            if(node.right) q.push(node.right);
        }
    }
    return ret;
};