JavaScript 经典排序算法

排序算法

现有数组[7, 5, 4, 15, 3, 9, 6, 12]，进行升序排序：

冒泡排序

Array.prototype.bubbleSort = function () {
    // 重复(元素个数-1)次
    for (let i = 0; i < this.length - 1; i++) {
        // 从0开始遍历还没有排序过的元素
        for (let j = 0; j < this.length - 1 - i; j++) {
            // 如果当前元素比下一个大
            if (this[j] > this[j + 1]) {
                // 交换他们的位置
                let temp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = temp;
            }
        }
    }
};

const arr = [7, 5, 4, 15, 3, 9, 6, 12];
arr.bubbleSort();
console.log(arr);

选择排序

Array.prototype.selectionSort = function () {
    // 重复(元素个数-1)次
    for (let i = 0; i < this.length - 1; i++) {
        // 把第一个没有排序过的元素设置为最小值
        let indexMin = i;
        // 遍历每个没有排序过的元素
        for (let j = i; j < this.length; j++) {
            // 如果遍历时出现元素小于现在的最小值
            if (this[j] < this[indexMin]) {
                // 将此元素设置为新的最小值
                indexMin = j;
            }
        }
        // 遍历结束后，将最小值和第一个没有排序过的位置交换
        if (indexMin !== i) {
            let temp = this[i];
            this[i] = this[indexMin];
            this[indexMin] = temp;
        }
    }
};

const arr = [7, 5, 4, 15, 3, 9, 6, 12];
arr.selectionSort();
console.log(arr);

插入排序

Array.prototype.insertionSort = function () {
    // 第一个数默认已经排序
    // 从第二个数开始，遍历没有排序过的数
    for (let i = 1; i < this.length; i++) {
        // 提取当前遍历的元素
        const temp = this[i];
        // 从当前元素位置往前比较
        let j = i;
        while (j > 0) {
            // 如果前一个数比提取的数
            if (this[j - 1] > temp) {
                // 将前一个数后移
                this[j] = this[j - 1];
            } else {
                // 否则退出循环
                break;
            }
            // 每比较一次，往前进一位
            j--;
        }
        // 遍历完成后，将提取的数插入
        this[j] = temp;
    }
};

const arr = [7, 5, 4, 15, 3, 9, 6, 12];
arr.insertionSort();
console.log(arr);

归并排序

Array.prototype.mergeSort = function () {
    const rec = arr => {
        // 若数组长度为一，直接返回该数
        if (arr.length === 1) return arr;
        // slice()：左闭右开，不会改变原数组
        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) {
            // 若两个数组都有值，则头部较小者推入res中
            if (orderLeft.length && orderRight.length) {
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
            } else if (orderLeft.length) {
                // 右侧数组空，左侧数组头部推入res
                res.push(orderLeft.shift());
            } else if (orderRight.length) {
                // 左侧数组空，右侧数组头部推入res
                res.push(orderRight.shift());
            }
        }
        return res;
    };
    const res = rec(this);
    // 将res拷贝到this
    res.forEach((item, index) => {
        this[index] = item;
    });
};

const arr = [7, 5, 15, 4, 9, 3, 12, 6];
arr.mergeSort();
console.log(arr);

快速排序

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++) {
            if (arr[i] < mid) {
                // 比基准小，放到左数组
                left.push(arr[i]);
            } else {
                // 比基准大，放到右数组
                right.push(arr[i]);
            }
        }
        // 返回连接好的数组
        return [...rec(left), mid, ...rec(right)];
    };
    const res = rec(this);
    // 将res拷贝到this
    res.forEach((item, index) => {
        this[index] = item;
    });
};

const arr = [7, 5, 4, 15, 3, 9, 6, 12];
arr.quickSort();
console.log(arr);