经典排序算法的ES6实现（动画演示）

发表于 分类于 阅读次数：

冒泡排序

在未排序序列中从后往前逐个比较相邻的两个元素，将最小的元素交换到开头

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n) O(n2) O(n2) O(1) 稳定 

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(array) {
    array = [...array];
    const len = array.length;
    for (let i = 0; i < len; i++) {
        for (let j = len - 1; j > i; j--) {
            if (array[j - 1] > array[j]) {
                [array[j - 1], array[j]] = [array[j], array[j - 1]];//元素交换
            }
        }
    }
    return array;
}
bubbleSort([5, 2, 4, 3, 8]);//[2, 3, 4, 5, 8]

选择排序

在未排序序列中选择最小元素，交换到开头

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectionSort(array) {
    array = [...array];
    const len = array.length;
    for (let i = 0; i < len; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (array[minIndex] > array[j]) {
                minIndex = j;//寻找最小元素的索引
            }
        }
        if (i !== minIndex) {
            [array[i], array[minIndex]] = [array[minIndex], array[i]];
        }
    }
    return array;
}
selectionSort([4, 2, 3, 6, 5]);//[2, 3, 4, 5, 6]

插入排序

在已排序序列中寻找正确位置插入当前元素

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
插入排序 O(n) O(n2) O(n2) O(1) 稳定 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertionSort(array) {
    array = [...array];
    const len = array.length;
    for (let i = 1; i < len; i++) {
        let insertIndex = 0;
        let current = array[i];
        for (let j = i - 1; j >= 0; j--) {
            if (array[j] > current) {
                array[j + 1] = array[j];//大于当前元素的后移一位
            } else {
                insertIndex = j + 1;//找到插入位置
                break;
            }
        }
        array[insertIndex] = current;
    }
    return array;
}
insertionSort([5, 3, 4, 7, 2]);//[2, 3, 4, 5, 7]

快速排序

找一个基准，小的放左边、大的放右边，然后都递归

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
快速排序 O(n log n) O(n log n) O(n2) O(log n) 不稳定 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(array) {
    if (array.length < 2) {
        return array;
    } else {
        const pivot = array[array.length - 1];//基准
        const left = [];
        const middle = [];
        const right = [];
        for (const value of array) {
            if (value < pivot) {//小于基准的元素放左边
                left.push(value);
            } else if (value === pivot) {//一样大的放中间
                middle.push(value);
            } else {//大于基准的元素放右边
                right.push(value);
            }
        }
        return [...quickSort(left), ...middle, ...quickSort(right)];//左边和右边递归
    }
}
quickSort([3, 5, 8, 1, 2, 9, 4, 7, 6]);//[1, 2, 3, 4, 5, 6, 7, 8, 9]

归并排序

“分”：将一个数组反复二分为两个小数组，直到每个数组只有一个元素；“治”：从最小数组开始，两两按大小顺序合并

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function mergeSort(array) {
    if (array.length < 2) {
        return array;
    } else {
        let half = Math.floor(array.length / 2);
        let left = array.slice(0, half);
        let right = array.slice(half);
        return merge(mergeSort(left), mergeSort(right));
    }

    function merge(left, right) {
        let result = [];
        while (left.length && right.length) {
            if (left[0] < right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        return [...result, ...left, ...right];
    }
}
mergeSort([6, 4, 3, 7, 5, 1, 2]);//[1, 2, 3, 4, 5, 6, 7]
0%