JavaScript 数据结构与算法（移植于Java）

这个仓库很早之前就想做了，最近正好有面试，就整理一下，把原来学习的Java相关的数据结构与算法仓库里的内容移植到JavaScript中。

二分查找

const {
    ArrayGenerator
} = require('./util')
const {
    LinerSearch
} = require('./线性查找')
class BinarySearch {
    constructor() {
    }
    /**
     * 二分搜索前提就是数组是有序的单调的
     *
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    static searchRWrapper(data, target) {
        return BinarySearch.searchR(data, 0, data.length - 1, target);
    }
    static searchR(data, l, r, target) {
        if (l > r) {
            return -1;
        }
        let mid = Math.floor(l + (r - l) / 2);
        if (target === data[mid]) {
            return mid;
        } else if (target > data[mid]) {
            // target > data[mid]
            return BinarySearch.searchR(data, mid + 1, r, target);
        } else { //  target < data[mid]
            return BinarySearch.searchR(data, l, mid - 1, target);
        }
    }
    static main() {
        // 使用二分搜索，必须保证待查找集合是单调的
        const STATUS = {
            order: '有序单调',
            random: '随机无需'
        }
        const status = STATUS.random
        let count = 100000;
        let arr = []
        if (status === STATUS.order) {
            // 有序单调数组
            arr = ArrayGenerator.generateOrderArray(count);
        } else {
            // 无序数组，极有可能查询不到待查元素
            arr = ArrayGenerator.generateRandomArray(count, count);
        }
        // let arr = [-1, 0, 3, 5, 9, 12];
        const target = Math.floor(Math.random() * count)
        let startTime = new Date().valueOf()
        let result = -1
        for (let i = 0; i < 10000; i++) {
            result = BinarySearch.searchRWrapper(arr, target);
        }
        console.log(`result ${result}`)
        let endTime = new Date().valueOf()
        console.log(`BinarySearch time is ${endTime - startTime}ms`)
        startTime = new Date().valueOf()
        for (let i = 0; i < 10000; i++) {
            result = LinerSearch.search(arr, target)
        }
        console.log(`result ${result}`)
        endTime = new Date().valueOf()
        console.log(`LinerSearch time is ${endTime - startTime}ms`)
    }
}
BinarySearch.main()

二叉树

const {
    arr2tree
} = require('./util')
class BinaryTree {
    // 非递归前序遍历
    // 深度优先遍历
    /** 深度优先遍历 */
    static preOrderNR(root) {
        let stack = [];
        stack.push(root);
        while (stack.length) {
            let top = stack.pop();
            console.log(top);
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
    }
    /** 前序遍历 */
    static preOrder(node) {
        if (node == null) {
            return;
        }
        // 访问节点
        // 前序遍历 开始
        console.log(node);
        BinaryTree.preOrder(node.left);
        BinaryTree.preOrder(node.right);
        // 前序遍历 结束
    }
    /** 中序遍历 */
    static inOrder(node) {
        if (node == null) {
            return;
        }
        // 访问节点
        // 中序遍历 开始
        BinaryTree.inOrder(node.left);
        console.log(node);
        BinaryTree.inOrder(node.right);
        // 中序遍历 结束
    }
    // 层序遍历
    // 广度优先遍历
    // 如果做图的遍历，要做记录，查看当前节点是否遍历过，否则会产生重复（一个节点的父亲节点可能有多个）
    // 树结构不存在这个情况
    /** 层序遍历 */
    static levelOrder(root) {
        let queue = [];
        queue.push(root);
        while (queue.length) {
            let cur = queue.shift();
            console.log(cur);
            if (cur.left != null) {
                queue.push(cur.left);
            }
            if (cur.right != null) {
                queue.push(cur.right);
            }
        }
    }
    /** 层序遍历，并将每层元素放到对用数组中 */
    static inorderTraversal(root) {
        let res = [];
        let queue = [root];
        while (queue.length) {
            let cur = [];
            // 当前层
            let index = queue.length;
            // 遍历当前层得到下一层
            for (let i = 0; i < index; i++) {
                let qu = queue.shift();
                cur.push(qu);
                if (qu.left) {
                    queue.push(qu.left);
                }
                if (qu.right) {
                    queue.push(qu.right);
                }
            }
            res.push(cur);
        }
        console.log(res)
        return res
    }
    static main(root) {
        // BinaryTree.preOrderNR(root)
        // BinaryTree.preOrder(root)
        // BinaryTree.inOrder(root)
        // BinaryTree.levelOrder(root)
        BinaryTree.inorderTraversal(root)
    }
}
const tree = arr2tree([1, 2, 3, 4, 5, 6, 7])
BinaryTree.main(tree)
/*
      1
  2       3
4   5   6   7
*/
// 4 2 5 1 6 3 7 中序遍历
// 1 2 4 5 3 6 7 前序遍历
// 4 5 2 6 7 3 1 后序遍历

常用快排

function sort(arr) {
    quickSort(arr, 0, arr.length - 1)
}
function quickSort(arr, l, r) {
    if (l > r) return;
    let p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}
function partition(arr, l, r) {
    // [l/i,j.....r]
    // [l - i] < v
    // [i - j - 1] > v
    let i = l;
    let j = i + 1;
    let v = arr[l];
    while (j <= r) {
        // 小交换，大向前走
        if (arr[j] < v) { // 看索引j位置的成员是否小于v
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
        j++;
    }
    [arr[l], arr[i]] = [arr[i], arr[l]];
    return i;
}
let arr = [4, 6, 8, 2, 3, 1, 0];
sort(arr);
console.log(arr);