BaoTao的前端日志

冒泡排序 Bubble Sort

简明解释

通过依次比较、交换相邻的元素大小（按照由小到大的顺序，如果符合这个顺序就不用交换）。

1 次这样的循环可以得到一个最大值，n - 1 次这样的循环可以排序完毕。

属性

  • 稳定
  • 时间复杂度 O(n²)
  • 交换 O(n²)
  • 对即将排序完成的数组进行排序 O(n)（但是这种情况下不如插入排序块，请继续看下文）

核心概念

  • 利用交换，将最大的数冒泡到最后
  • 使用缓存 postion 来优化
  • 使用双向遍历来优化

实现

const newarr = [2, 5, 7, 3, 4, 1, 10, 9, 8, 6];

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    console.log(arr);
}
bubbleSort(newarr)
1
2
3
4
5
6
7
8
9
10
11
12
13

快速排序 Quick Sort

简明解释

  1. 从数列中挑出一个元素，称为"基准"（pivot），
  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

属性

  • 不稳定
  • O(n²) time, 但是通常都是 O(n·log(n)) time (或者更快)
  • O(log(n)) extra space

When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort

核心概念

  • 使用了分而治之的思想

实现

// 快速排序--和冒泡排序一样是使用交换实现的排序算法
function quickSort(arr) {
    // 常规写法 双指针
    _quickSort(arr, 0, arr.length - 1);
    function _quickSort(arr, left, right) {
        // 递归判断条件
        if (left >= right) return;
        let i = left, j = right, flag = left;
        while (i < j) {
            while (arr[j] > arr[i] && j > i) j--;
            if (i >= j) break;
            while (arr[i] <= arr[flag] && i < j) i++;
            let temp = arr[flag];
            arr[flag] = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            flag = i;
        }
        _quickSort(arr, left, flag - 1);
        _quickSort(arr, flag + 1, right);
    }
    console.log(arr);
}
// 非递归实现快速排序,利用栈来代替递归
function noquickSort(arr) {
    let list = [[0, arr.length - 1]];
    while (list.length) {
        let now = list.pop();
        if (now[0] > now[1]) continue;
        let i = now[0], j = now[1], flag = now[0];
        while (i < j) {
            while (arr[j] > arr[i] && j > i) j--;
            if (i > j) break;
            while (arr[i] <= arr[flag] && i < j) i++;
            let temp = arr[flag];
            arr[flag] = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            flag = i;
        }
        list.push([now[0], flag - 1]);
        list.push([flag + 1, now[1]]);
    }
    console.log(arr)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

选择排序 Selection Sort

简明解释

每一次内循环遍历寻找最小的数，记录下 minIndex，并在这次内循环结束后交换 minIndex 和 i 的位置。

重复这样的循环 n - 1 次即得到结果。

属性

  • 不稳定
  • Θ(n²) 无论什么输入，均为 Θ(n²)
  • Θ(n) 交换: 注意，这里只有 n 次的交换，选择排序的唯一优点

实现

// 选择排序--嵌套循环找出最小值索引实现功能
function selectSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
        }
    }
    console.log(arr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

堆排序 Heap Sort

简明解释

堆排序可以认为是选择排序的改进版，像选择排序一样将输入划分为已排序和待排序。

不一样的是堆排序利用堆这种近似完全二叉树的良好的数据结构来实现排序，本质上使用了二分的思想。

  1. 先将所有的数据堆化
  2. 然后移动 arr[0] 到数组末尾（已排序区域）
  3. 再重新堆化，依次这样循环来排序。

利用堆这种良好的数据结构，它在拥有良好的可预测性的同时（不管输入什么都是 O(n·log(n)) 时间复杂度），但它的缺点也有：即不稳定，而且 O(n·log(n)) 的平均效率决定了它的效率不如快速排序。适用于数据库内引擎排序（需要这样的可预测性性能）。

属性

  • 不稳定
  • O(n·log(n)) time

核心概念

  • 利用良好的数据结构——堆，来排序
  • 二分的思想
  • 选择排序的改进版，继承了"可预测性"（什么数据输入都为 O(n·log(n) time）

实现

// 堆排序
function heapSort(arr) {
    let size = arr.length;
    // 使用Math.floor(arr.length / 2 - 1)表示第一个非叶子结点
    for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
        heapify(arr, i, size);
    }
    for (let i = size - 1; i >= 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        size -= 1;
        // 同下由于产生交换是0和i，则对0开始的堆重新排序
        heapify(arr, 0, size)
    }

    return arr;
    function heapify(arr, i, size) {
        let lastIndex = i;
        // 大顶堆用数组表示，则是arr[i] > arr[2i+1] && arr[i] > arr[2i+2]
        let right = lastIndex * 2 + 1;
        let left = lastIndex * 2 + 2;
        if (right < size && arr[right] > arr[lastIndex]) {
            lastIndex = right;
        }
        if (left < size && arr[left] > arr[lastIndex]) {
            lastIndex = left;
        }
        if (lastIndex !== i) {
            [arr[i], arr[lastIndex]] = [arr[lastIndex], arr[i]];
            // 若产生交换，则对交换之后下面的堆也要进行排序，保证大顶堆顺序
            // e.g:1和4索引内容交换，则对4下面的堆进行重新排序
            heapify(arr, lastIndex, size);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

插入排序 Insertion Sort

默认 a[0] 为已排序数组中的元素，从 arr[1] 开始逐渐往已排序数组中插入元素，从后往前一个个比较，如果待插入元素小于已排序元素，则已排序元素往后移动一位，直到待插入元素找到合适的位置并插入已排序数组。

经过 n - 1 次这样的循环插入后排序完毕。

属性

  • 稳定
  • 适合场景：对快要排序完成的数组时间复杂度为 O(n)
  • 非常低的开销
  • 时间复杂度 O(n²)

由于它的优点（自适应，低开销，稳定，几乎排序时的O（n）时间），插入排序通常用作递归基本情况（当问题规模较小时）针对较高开销分而治之排序算法， 如希尔排序或快速排序。

核心概念

  • 高性能（特别是接近排序完毕时的数组），低开销，且稳定
  • 利用二分查找来优化

实现

// 插入排序
function insertSort(arr) {
    // 默认第一个数排好序，所以是从1开始
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i];
        let index = i - 1;
        // 注意判断条件使用temp进行判断
        while (temp < arr[index]) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = temp;
    }
    console.log(arr)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

希尔排序 Shell Sort

简明解释

希尔排序是插入排序的改进版，它克服了插入排序只能移动一个相邻位置的缺陷（希尔排序可以一次移动 gap 个距离），利用了插入排序在排序几乎已经排序好的数组的非常快的优点。

使用可以动态定义的 gap 来渐进式排序，先排序距离较远的元素，再逐渐递进，而实际上排序中元素最终位置距离初始位置远的概率是很大的，所以希尔排序大大提升了性能（尤其是 reverse 的时候非常快，想象一下这时候冒泡排序和插入排序的速度）。

而且希尔排序不仅效率较高（比冒泡和插入高），它的代码相对要简短，低开销（继承插入排序的优点），追求这些特点（效率要求过得去就好，代码简短，开销低，且数据量较小）的时候希尔排序是好的 O(n·log(n)) 算法的替代品。

总而言之：希尔排序的性能优化来自增量队列的输入和 gap 的设定。

属性

  • 不稳定
  • 在快要排序完成的数组有 O(n·log(n)) 的时间复杂度（并且它对于反转数组的速度非常快）
  • O(n^3/2) time as shown (想要了解更多细节，请查阅 wikipedia Shellsort）

实现

// 希尔排序--就是在插入排序基础上增加了一个gap增量
function shellSort(arr) {
    let gap = Math.floor(arr.length);
    while (gap > 0) {
        for (let i = gap; i < arr.length; i++) {
            let temp = arr[i];
            let index = i - gap;
            while (temp < arr[index]) {
                arr[index + gap] = arr[index];
                index -= gap;
            }
            arr[index + gap] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    console.log(arr)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

归并排序 Merge Sort

简明解释

归并排序使用分而治之的思想，以折半的方式来递归/迭代排序元素，利用空间来换时间，做到了时间复杂度 O(n·log(n)) 的同时保持了稳定。

这让它在一些更考虑排序效率和稳定性，次考虑存储空间的场合非常适用（如数据库内排序，和堆排序相比，归并排序的稳定是优点）。并且归并排序非常适合于链表排序。

属性

  • 稳定 (在 O(n·log(n)) 时间复杂度的排序算法中，归并排序是唯一稳定的)
  • 时间复杂度 O(n·log(n))
  • 对于数组需要 Θ(n) 的额外空间 注意：归并排序需要额外的空间，这是它的不完美之处
  • 对于链表需要 O(log(n)) 的额外空间，所以归并排序非常适合列表的排序
  • Does not require random access to data 因为这个特点，归并排序很适合用来排序列表

核心概念

  • 分而治之的思想
  • 空间换时间，并且稳定，保持稳定性这一点是它的亮点
  • 二分思想

实现

// 归并排序
function mergeSort(arr) {
    function merge(left, right) {
        let result = [];
        while (right.length && left.length) {
            result.push(right[0] < left[0] ? right.shift() : left.shift())
        }
        return result.concat(right, left);
    }
    if (arr.length < 2) {
        return arr
    }
    let mid = Math.floor(arr.length / 2);
    let left = arr.splice(0, mid);
    let right = arr;
    return merge(mergeSort(left), mergeSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结 & 答疑

提出几个问题，可以当做自我检测：

  • 数据几乎快排序完成时？

插入排序不解释

  • 数据量小，对效率要求不高，代码简单时？

性能大小：希尔排序 > 插入排序 > 冒泡排序 > 选择排序

  • 数据量大，要求稳定的效率（不会像快速排序一样有 O(n²) 的情况）（如数据库中）？

堆排序

  • 数据量大，要求效率高，而且要稳定？

归并排序

  • 数据量大，要求最好的平均效率？

性能大小：快速排序 > 堆排序 > 归并排序

因为虽然堆排序做到了 O(n·log(n)，而快速排序的最差情况是 O(n²)，但是快速排序的绝大部分时间的效率比 O(n·log(n) 还要快，所以快速排序真的无愧于它的名字。（十分快速）

  • 选择排序绝对没用吗？

选择排序只需要 O(n) 次交换，这一点它完爆冒泡排序。

参考

优雅的 JavaScript 排序算法

快速排序参考:js实现快速排序

← 二叉树 →