常见的排序算法

本博客 hjy-xh，转载请申明出处

常见的排序

冒泡排序

说明：重复遍历要排序的数列，一次比较两个元素，按排序顺序交换元素值，不断遍历直到没有再需要交换

const bubbleSort = (input) => {
    const output = [...input];
    const length = output.length;
    let hasSwap = false;
    for(let i = 1; i <= length - 1; i++) {
        for (let j = 0; j < length - 1; j++) {
            if (output[j] > output[j + 1]) {
                let temp = output[j];
                output[j] = output[j + 1];
                output[j + 1] = temp;
                hasSwap = true;
            }
        }
        if (!hasSwap) break;
    }
    return output;
}

插入排序

说明：遍历数组，找到数据应该插入的位置将其插入即可

const insertSort = (input) => {
    const output = [...input];
    const length = output.length;
    for (let i = 1; i <= length - 1; i++) {
        const temp = output[i];
        let j = i - 1;
        while (j >= 0 && output[j] > temp) {
            output[j + 1] = output[j];
            j--;
        }
        output[j + 1] = temp;
    }
    return output;
}

选择排序

说明: 每一次从待排序的数据元素中选出最小（或最大）的一个元素，放到已排序数组的末尾

const selectSort = (input) => {
    const output = [...input];
    const length = output.length;
    let minIndex = 0;
    let temp = 0;
    for (let i = 0; i < length; i++) {
        minIndex = i;
        for (let j = i + 1; j < length; j++) {
            if (output[j] < output[minIndex]) {
                minIndex = j;
            }
        }
        temp = output[i];
        output[i] = input[minIndex];
        output[minIndex] = temp;
    }
    return output;
}

归并排序

说明：归并的的核心思想是分治。它把数组从中间划分成两个数组，一直递归把子数组划分成更小的数组，知道数组中元素个数为1时进行排序。按大小顺序合并两个数组，接着按照递归的顺序返回，不断合并排好序的数组。

const mergeSort = (input) => {
    const length = input.length;
    if (length < 2) {
        return input;
    }
    const middle = Math.floor(length / 2);
    const left = input.slice(0, middle);
    const right = input.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
    const result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) {
        result.push(left.shift());
    }
    while (right.length) {
        result.push(right.shift());
    }
    return result;
}

快速排序

说明：它是冒泡排序的一种改进，通过元素之间的比较和交换位置来达到排序的目的。快排在每一轮挑选一个基准元素，把剩下的元素同它进行比较，大于它的放到数列的一边，小于它的放到数列的另一边，一轮比较完成后，整个序列以选取的基准元素位为界，左侧均小于基准元素，右侧均大于基准元素。但左右两侧内部并不是有序的(左右两侧关键字个数也不一定相同)。进而继续将左右两侧分别再以这种方式进行排序，直到将序列拆分的剩余一个关键字为止，整个序列即变成有序。

const quickSort = (input) => {
    if (input.length <= 1) { return input; }
    const left = [];
    const right = [];
    const middle = input.splice(Math.round(input.length / 2), 1)[0];

    for (let i = 0; i < input.length; i++) {
        (middle > input[i] ? left : right).push(input[i]);
    }

    return [...quickSort(left), middle, ...quickSort(right)];
}