一些算法思想记录

搜索和排序

JS中通常使用数组的sort方法来排序使用indexOf来进行搜索

资料：https://visualgo.net/zh

可以看动画，喜欢喜欢！

排序算法：

冒泡排序：

最简单，基本用不到

比较相邻元素，如果第一个比第二个大，就交换。一轮下来，最后一个数最大，执行n-1轮，就可以完成排序

Array.prototype.bubbleSort = function () {
    for (let i = 0; i < this.length - 1; i += 1) {
        for (let j = 0; j < this.length - 1 - i; j += 1) {
            if (this[j] > this[j + 1]) {
                const temp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = temp;
            }
        }
    }
};

const arr = [5, 4, 3, 2, 1];
arr.bubbleSort();

时间复杂度：有两个嵌套循环 On^2

选择排序：

找到数组中的最小值，选中它放在第一位，以此类推……

Array.prototype.selectionSort = function () {
    for (let i = 0; i < this.length - 1; i += 1) {
        let indexMin = i;
        for (let j = i; j < this.length; j += 1) {
            if (this[j] < this[indexMin]) {
                indexMin = j;
            }
        }
        if (indexMin !== i) {
            const temp = this[i];
            this[i] = this[indexMin];
            this[indexMin] = temp;
        }
    }
};

const arr = [5, 4, 3, 2, 1];
arr.selectionSort();

时间复杂度同样是On^2

插入排序：

是从第二个数开始往前比，如果比它大，就往后排，以此类推进行

Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i += 1) {
        const temp = this[i];
        let j = i;
        while (j > 0) {
            if (this[j - 1] > temp) {
                this[j] = this[j - 1];
            } else {
                break;
            }
            j -= 1;
        }
        this[j] = temp;
    }
};

const arr = [2, 4, 5, 3, 1];
arr.insertionSort();

归并排序：

性能好一些

份：把数组分成两半在递归的分开子数组，吃到成为一个个单独的数

合：把两个数合并为有序数组把多个有序数组合并

Array.prototype.mergeSort = function () {
    const rec = (arr) => {
        if (arr.length === 1) { return arr; }
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, arr.length);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        const res = [];
        while (orderLeft.length || orderRight.length) {
            if (orderLeft.length && orderRight.length) {
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
            } else if (orderLeft.length) {
                res.push(orderLeft.shift());
            } else if (orderRight.length) {
                res.push(orderRight.shift());
            }
        }
        return res;
    };
    const res = rec(this);
    res.forEach((n, i) => { this[i] = n; });
};

const arr = [5, 4, 3, 2, 1];
arr.mergeSort();

分的时间复杂度是 OlogN 二分的操作基本都是这个

合的时间复杂度ON

所以总体是On*logn

快速排序：

我的最爱来了！

首先分区：从数组中任意选择一个作为基准，小的放前面，大的放后面

接着对基准前后的子数组进行分区操作

Array.prototype.quickSort = function () {
    const rec = (arr) => {
        if (arr.length === 1) { return arr; }
        const left = [];
        const right = [];
        const mid = arr[0];
        for (let i = 1; i < arr.length; i += 1) {
            if (arr[i] < mid) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...rec(left), mid, ...rec(right)];
    };
    const res = rec(this);
    res.forEach((n, i) => { this[i] = n });
};

const arr = [2, 4, 5, 3, 1];
arr.quickSort();

搜索算法：