常见排序算法的 JS 实现

发表于   |   分类于   |     |   阅读量

前言

排序算法有很多，本文就最常见的冒泡排序、选择排序、插入排序、归并排序与快速排序进行一下总结，并将它们用 JavaScript 语言实现。

首先放一个总表：

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) In-place 稳定
选择排序 O(n2) O(n2) O(n2) O(1) In-place 不稳定
插入排序 O(n2) O(n) O(n2) O(1) In-place 稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) Out-place 稳定
快速排序 O(n log n) O(n log n) O(n2) O(log n) In-place 不稳定

名词解释：

  • n: 数据规模
  • In-place: 占用常数内存，不占用额外内存
  • Out-place: 占用额外内存
  • 稳定性： 2个相等值的相对顺序在排序前后相同

冒泡排序（Bubble Sort）

算法原理

冒泡排序重复的走访需要排序的数列，比较任何两个相邻的项，如果前一个比第二个大，则交换它们。元素项会慢慢向上移动到正确的位置，就好像气泡升至表面一样，因此得名冒泡排序。

算法实现

冒泡排序的 JavaScript 代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const bubbleSort = arr => {
    let i, j, len1, len2, tmp;
    for (i = 0, len1 = arr.length; i < len1; i++) {
        for (j = 0, len2 = len1 - 1 - i; j < len2; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
};
let arr = [34,67,33,1,128,56,8,42,90,17,256];
bubbleSort(arr);  //[1, 8, 17, 33, 34, 42, 56, 67, 90, 128, 256]

算法分析

冒泡排序是最简单的排序算法，它可以原地排序，然而，它也是最没有效率的。

  • 最佳情况： T(n) = O(n)
  • 最差情况： T(n) = O(n2)
  • 平均情况： T(n) = O(n2)

选择排序（Selection Sort）

算法原理

选择排序算法的大致思路是找到数组中最小的值并将其放在第一位，接着找到第二小的值并将其放在第二位。以此类推，直到所有元素排序完毕。

算法实现

选择排序的 JavaScript 代码实现如下：

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
const selectionSort = arr => {
    let len = arr.length,
        indexMin, i, j, tmp;
    for (i = 0; i < len - 1; i++) {
        indexMin = i;
        for (j = i + 1; j < len; j++) {
            if (arr[indexMin] > arr[j]) {
                indexMin = j;
            }
        }
        if (i !== indexMin) {
            tmp = arr[i];
            arr[i] = arr[indexMin];
            arr[indexMin] = tmp;
        }
    }
    return arr;
};
let arr = [34,67,33,1,128,56,8,42,90,17,256];
selectionSort(arr);  //[1, 8, 17, 33, 34, 42, 56, 67, 90, 128, 256]

算法分析

在所有的 完全依靠交换 去移动元素的排序方法中，选择排序属于非常好的一种。与冒泡排序一样，选择排序也是一种原址比较排序算法，但这也几乎是选择排序的唯一优点了，当空间复杂度要求较高时可以考虑选择排序，否则其实际适用场合非常罕见。

  • 最佳情况： T(n) = O(n2)
  • 最差情况： T(n) = O(n2)
  • 平均情况： T(n) = O(n2)

插入排序（Insertion Sort）

算法原理

插入排序将数组分成“已排序”和“未排序”两部分，一开始的时候，“已排序”的部分只有一个元素，然后将它后面一个元素从“未排序”部分插入“已排序”部分，从而“已排序”部分增加一个元素，“未排序”部分减少一个元素。以此类推，完成全部排序。

只要你打过扑克牌，并且尝试过将扑克牌在手中按从小到大排列，插入排序的原理就很容易理解。在摸牌时，把手上的牌当做“已排序”的部分，把还没摸的牌当做“未排序”部分，每次从桌上摸一张牌并插入到手中合适的位置，这就是插入排序的原理。

算法实现

插入排序的 JavaScript 代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const insertionSort = arr => {
    let len = arr.length,
        i, j, tmp;
    for (i = 1; i < len; i++) {
        j = i;
        tmp = arr[i];
        while (j > 0 && arr[j - 1] > tmp) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = tmp;
    }
    return arr;
};
let arr = [34,67,33,1,128,56,8,42,90,17,256];
insertionSort(arr);  //[1, 8, 17, 33, 34, 42, 56, 67, 90, 128, 256]

算法分析

插入排序也是一种原地排序算法，在排序小型数组时，它比冒泡排序和选择排序都要好。

  • 最佳情况： T(n) = O(n)
  • 最差情况： T(n) = O(n2)
  • 平均情况： T(n) = O(n2)

归并排序（Merge Sort）

算法原理

归并排序是一种 分治 算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

归并排序的过程如下图所示：

归并排序

算法实现

归并排序的 JavaScript 代码实现如下：

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
const mergeSort = arr => {
    let len = arr.length;
    if (len === 1) {
        return arr;
    }
    let mid = Math.floor(len / 2),
        left = arr.slice(0, mid),
        right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
};
const merge = (left, right) => {
    let res = [],
        len1 = left.length,
        len2 = right.length;
    while (len1 > 0 && len2 > 0) {
        if (left[0] <= right[0]) {
            res.push(left.shift());
            len1--;
        } else {
            res.push(right.shift());
            len2--;
        }
    }
    if (len1 > 0) {
        res = res.concat(left);
    }
    if (len2 > 0) {
        res = res.concat(right);
    }
    return res;
};
let arr = [34,67,33,1,128,56,8,42,90,17,256];
mergeSort(arr);  //[1, 8, 17, 33, 34, 42, 56, 67, 90, 128, 256]

算法分析

归并排序是第一个可以被实际使用的排序算法，Firefox 浏览器内部实现的 Array.prototype.sort() 方法就采用的归并排序。归并排序是以内存空间为代价来换取时间性能的提高，它的时间复杂度始终是 O(n log n) ，空间复杂度是 O(n) 。

  • 最佳情况： T(n) = O(n log n)
  • 最差情况： T(n) = O(n log n)
  • 平均情况： T(n) = O(n log n)

快速排序（Quick Sort）

算法原理

与归并排序一样，它也使用 分治 的思想，将原始数组分为较小的数组。但不同的是，它没有像归并排序那样将他们分割开。

算法实现

快速排序的实现过程如下：

  1. 从数列中挑出一个元素（一般是中间的元素），称为 “基准”（pivot）。
  2. 重新排序数列，把所有比基准值小的元素放到基准前面，所有元素比基准值大的元素放到基准后面（相同的数可以放到任一边）。这个步骤被称为分区（partition）操作，在这个分区退出之后，该基准就处于数列的中间位置。
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列重复前两个步骤，直至数组已完全排序。

快速排序的 JavaScript 代码实现如下：

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
const quickSort = arr => {
    let len = arr.length;
    if (len <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(len / 2),
        pivot = arr.splice(pivotIndex, 1)[0],
        left = [],
        right = [];
    len--;
    for (let i = 0; i < len; i++) {
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
};
let arr = [34,67,33,1,128,56,8,42,90,17,256];
quickSort(arr);  //[1, 8, 17, 33, 34, 42, 56, 67, 90, 128, 256]

算法分析

快速排序也许是最常用的排序算法了。Chrome 浏览器与 Microsoft Edge 浏览器内部实现的 Array.prototype.sort() 方法就采用的快速排序，不过它们都针对一些具体情况做出了优化，这里暂且不表。快速排序的最坏时间复杂度是 O(n<sup>2</sup>) （比如顺序数列的快排），但它的平均时间复杂度是 O(n log n) ，且 O(n log n) 记号中隐含的常数因子很小，比时间复杂度稳定等于 O(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序的。

  • 最佳情况： T(n) = O(n log n)
  • 最差情况： T(n) = O(n2)
  • 平均情况： T(n) = O(n log n)

附

本文的相关代码在这里，仅供参考。

------ 本文结束 ------
坚持原创技术分享，您的支持将鼓励我继续创作！