排序算法分析总结（附js实现）

本文内容其实不是很多，就是代码占了很多行。

总览

默认需要 排序 的数据结构为数组，时间复杂度为平均时间复杂度。

下面代码实现，排序默认都是 从小到大 排序。

所有代码

我的 js 代码实现都放在 github： https://github.com/F-star/js-...

代码仅供参考。

冒泡排序（Bubble Sort）

假设要进行冒泡排序的数据长度为 n。

冒泡排序会进行多次的冒泡操作，每次都会相邻数据比较，如果前一个数据比后一个数据大，就交换它们的位置（即让大的数据放在后面）。这样每次交换，至少有一个元素会移动到排序后应该在的位置。重复冒泡 n（或者说 n-1） 次，就完成了排序。

详细来说，第 i （i 从 0 开始） 趟冒泡会对数组的前 n - i 个元素进行比较和交换操作，要对比的次数是 size - i - 1 。

冒泡排序总共要进行 n-1 次冒泡（当然你可以说是 n 次冒泡，不过最后一次冒泡只有一个元素，不用进行比较）。

优化

有时候，可能只进行了 n 次冒泡，数组就已经是有序的了，甚至数组本来就是有序的。这时候我们希望：当发现一次冒泡后，数组有序，就停止下一次的冒泡，返回当前的数组。

这时候我们可以在每一趟的冒泡前，声明一个变量 exchangeFlag，将其设置为 true。冒泡过程中，如果发生了数据交换，就将 exchangeFlag 设置为 false。结束一趟冒泡后，我们就可以通过 exchangeFlag 知道 数据是否发生过交换 。如果没有发生交换，就说明数组有序，直接返回该数组即可；否则说明还没有排好序，继续下一趟冒泡。

代码实现

const bubbleSort = (a) => {
    // 每次遍历找到最大（小）的数放到最后面的位置。
    // 优化：如果某次冒泡操作没有数据交换，说明已经有序了。

    // 双重循环。
    if (a.length <= 1) return a;
    // 这里的 i < len 改成 i < len - 1 也是正确的，因为最后第 len - 1次并不会执行。
    for (let i = 0, len = a.length; i < len; i++) {
        let exchangeFlag = false;   // 是否发生过换
        for (let j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]];
                exchangeFlag = true;
            }
            
        }
        console.log(a)
        if (exchangeFlag == false) return a;
    }
}

// 测试
let array = [199, 3, 1, 2, 8, 21,4, 100, 8];
console.log (bubbleSort(array));

分析

1. 冒泡排序的时间复杂度是 O(n^2) 。

最好时间复杂度是 O(n) ，即第一趟进行 n-1 次比较后，发现原数组是有序的，结束冒泡。

最坏时间复杂度是 O(n^2) ，当原数组刚好是倒序排列时，即需要进行 n 次冒泡，要进行 (n-1) + (n-2) ... + 1 次比较后，用等比数列求和公式求和后并化简，即可求出最坏时间复杂度。

平均时间复杂度不好分析，它是 O(n^2)

2. 冒泡排序是 稳定 的排序算法。

这里的“稳定”指的是：排序后，值相等的数据的前后顺序保持不变。

相邻数据如果相等，不交换位置即可。

3. 冒泡排序是原地排序算法

原地排序指的是空间复杂度是 O(1) 的排序算法。

冒泡排序只做了相邻数据交换，另外有两个临时变量（交换时的临时变量、flag），只需要常量级的临时空间，空间复杂度为 O(1)

插入排序（Insertion Sort）

插入排序。本质是从 未排序的区域 内取出数据，放到 已排序区域 内，这个取出的数据会和已排序的区间内数据一一对比，找到正确的位置插入。

我们直接将数组分为 已排序区域 和 未排序区域 。刚开始开始，已排序区域只有一个元素，即数组的第一个元素。插入的方式有两种：从前往后查找插入 和 从后往前查找插入。这里我选择 从后往前查找插入。

代码实现

const insertionSort = a => {
    for (let i = 0, len = a.length; i < len; i++) {
        let curr = a[i];     // 存储当前值，排序的时候，它对应的索引指向的值可能会在排序时被覆盖
        for (let j = i - 1; j >= 0;j--) {
            if (curr < a[j]) {
                a[j + 1] = a[j];
            } else {
                break;
            }
            // 找到位置（0 或 curr >= a[j]时）
            a[j] = curr;
        }
    } 
    return a;
}

分析

1. 插入排序的时间复杂度是： O(n^2)

当要排序的数据是有序的，我们每次插入已排序的区域，只需要比较一次，一共比较 n-1 次就结束了（注意这里是从后往前遍历已排序区域）。所以最好时间复杂度为 O(n)。

最坏时间复杂度是 O(n^2)，是数据刚好是倒序的情况，每次都要遍历完 已排序区域的所有数据。

2. 插入排序是稳定排序

遍历已排序区域时，值相同的时候，放到最后的位置即可。

3. 插入排序是原地排序算法

不需要额外空间，是在数组上进行数据交换，所以插入排序是原地排序算法。

选择排序（Selection Sort）

选择排序也有一个 已排序区域 和一个 未排序区域 。它和插入排序不同的地方在于：选择排序是从 未排序区域 中找出最小的值，放到 已排序区域的末尾。

为了减少内存消耗，我们也是直接在数组上进行数据的交换。

插入排序比冒泡排序优秀的原因

插入排序和冒泡排序的时间复杂度都是 O(n^2)，元素交换次数也相同，但插入排序更优秀。原因是冒泡排序的交换，需要一个 tmp 的中间变量，来进行两个元素交换，这就变成了 3 个赋值操作。而插入排序（从后往前遍历已排序区域），不需要中间遍历，它是直接一些元素后移覆盖，只要1个赋值操作。

冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}
 
插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

此外，插入排序还可以进行优化，变成 希尔排序 。这里不具体说。

代码实现

const selectionSort = a => {
    let tmp;
    for (let i = 0, len = a.length; i < len; i++) {

        let min = a[i],     // 保存最小值，用于比较大小。
            minIndex = i;   // 保存未排序区间中，最小值对应的索引（方便进行元素交换）
        for (let j = i; j < len; j++) {
            if (a[j] < min) {
                minIndex = j;
                min =a[j]
            }
        }
        tmp = a[minIndex];
        a[minIndex] = a[i];
        a[i] = tmp;
    }
    return a;
}

分析

1. 选择排序的时间复杂度是 O(n^2)

最好时间复杂度是 O(n^2)。因为每次从未排序区域内找出最小值，都要遍历未排序区域内的所有元素，一共要查找 n-1 次，所以时间复杂度是 O(n^2)。

最坏时间复杂度也是 O(n^2)，理由同上。

2. 选择排序是原地排序算法

我们找到为排序区域的最小元素，会交换该元素和 排序区域的下一个位置的元素（即排序区域的第一个元素），然后 i 后移。只做了元素的交换，且只用到了常数级的内存空间（交换两个数据需要的一个临时遍历），因此选择排序是原地排序算法。

3. 选择排序是不稳定的排序算法

不稳定，是因为每次都要找最小值和前面的元素进行交换，这样会破坏稳定性。举个反例来证明：3 3 2, 第一次交换后，为 2 3 3，此时两个 3 的相对顺序就改变了。

当然你可以额外的创建一个大小为数组长度的空数组，来作为 已排序区域。这样做就不需要交换元素，可以做到排序稳定，但这样做耗费了额外的内存，变成了非原地排序算法。

归并排序

归并排序用到了 分治思想 。分治思想的核心是：将一个大问题分解成多个小的问题，解决后合并为原问题。分治通常用递归来实现。分治和递归的区别是， 分治是一种解决问题的处理思想，递归是一种编程技巧。

归并排序，会将数组从中间分成左右两部分。然后对这两个部分各自继续从中间分成两部分，直到无法再分。然后将分开的两部分进行排序合并（合并后数组有序），不停地往上排序合并，最终合并成一个有序数组。

说明下 merge 函数。它是将两个有序数组合并为一个有序数组，做法是创建一个空数组，长度为两个有序数组的大的一个。设置指针 i 和 j 分指向两个数组的第一个元素，取其中小的加入数组，对应的数组的指针后移。重复上面这个过程，直到一个数组为空，就将另一个数组的剩余元素都推入新数组。

另外，merge() 函数可以借助 哨兵 进行优化处理。具体我没研究，有空再考虑实现。

代码实现

归并的代码实现用到了递归，所以代码不是很好看懂。

const mergeSort = a => {
    mergeSortC(a, 0, a.length - 1)
    return a;
}

const mergeSortC = (a, p, r) => {
    if (p >= r) return
    let q = Math.floor( (p + r) / 2 ); // 这样取中间值，right.length >= left.length
    mergeSortC(a, p, q);
    mergeSortC(a, q+1, r);
    merge(a, p, q, r)  // p->q （q+1）->r 区域的两个数组合并。
}

/**
 * merge方法（将两个有序数组合并成一个有序数组）
 */
function merge(a, p, q, r) {
    let i = p,
        j = q+1,
        m = new Array(r - q);    // 保存合并数据的数组
    
    let k = 0;
    while (i <= q && j <= r) {
        if (a[i] <= a[j]) {
            m[k] = a[i];
            i++;
        } else {
            m[k] = a[j]
            j++;
        }
        k++;
    }

    // 首先找出两个数组中，有剩余的元素的数组。
    // 然后将剩余元素依次放入数组 m。
    let start = i,
        end = q;
    if (j <= r) {
        start = j;
        end = r;
    }

    while (start <= end) {
        m[k] = a[start];
        start++;
        k++;
    }
    // m的数据拷贝到 a。
    for(let i = p; i <= r; i++) {
        a[i] = m[i-p];
    }
}

性能分析

归并排序的时间复杂度是 O(nlogn)

以下为简单推导过程，摘自 专栏-「数据结构与算法之美」 。

问题a分解为子问题 b 和 c，设求解 a、b、c 的时间为 T(a)、T(b)、Y(c)，则有

T(a) = T(b) + T(c) + K

而合并两个有序子数组的时间复杂度是 O(n)，于是有

T(1) = C；   n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1

化简后，得到 T(n)=Cn+nlog2n 。所以归并排序的时间复杂度是 O(nlogn)。

归并排序是稳定的排序

归并交换元素的情况发生在 合并 过程，只要让比较左右两个子数组时发现相等时，取左边数组的元素，就可以保证有序了。

归并排序不是原地排序

依然归并排序非常优秀（指时间复杂度），但，它的空间复杂度是 O(n)。因为进行合并操作时，需要申请一个临时数组，该数组的长度最大不会超过 n。

快速排序

快速排序，简称 “快排”。快排使用的是分区思想。

快排会取数组中的一个元素作为 pivot（分区点），将数组分为三部分：

1. 小于 pivot 的部分
2. pivot
3. 大于或等于 pivot 的部分。

我们取左右两边的子数组，执行和上面所说的操作，直到区间缩小为0，此时整个数组就变成有序的了。

在归并排序中，我们用到一个 merge() 合并函数，而在快排中，我们也有一个 partition() 分区方法。该方法的作用是根据提供的区间范围，随机取一个 pivot，将该区间的数组的数据进行交换，最终将小于 pivot 的放左边，大于 pivot 的放右边，然后返回此时 pivot 的下标，作为下一次 递归 的参考点。

partition() 分区函数有一种巧妙的实现方式，可以实现原地排序。处理方式有点类似 选择排序。首先我们选一个 pivot，pivot 后的元素全都往前移动一个单位，然后pivot 放到末尾。接着我们将从左往右遍历数组，如果元素小于 pivot，就放入 “已处理区域”，具体操作就是类似插入操作那种，进行直接地交换；如果没有就不做操作，继续下一个元素，直到结束。最后将 pivot 也放 “已处理区间”。这样就实现了原地排序了。

另外，对 partition 进行适当的改造，就可以实现 “查找无序数组内第k大元素” 的算法。

代码实现

const quickSort = a => {
    quickSortC(a, 0, a.length - 1)
    return a;
}

/**
 * 递归函数
 * 参数意义同 partition 方法。
 */
function quickSortC(a, q, r) {
    if (q >= r) {
        // 提供的数组长度为1时，结束迭代。
        return a;
    }
    let p = partition(a, q, r);
    quickSortC(a, q, p - 1);
    quickSortC(a, p + 1, r);
}

/**
 * 随机选择一个元素作为 pivot，进行原地分区，最后返回其下标
 * 
 * @param {Array} a 要排序的数组
 * @param {number} p 起始索引
 * @param {number} r 结束索引
 * @return 基准的索引值，用于后续的递归。
 */
export function partition(a, p, r) {
    // pivot 默认取最后一个，如果取得不是最后一个，就和最后一个交换位置。
    let pivot = a[r],
        tmp,
        i = p;     // 已排序区间的末尾索引。
    // 类似选择排序，把小于 pivot 的元素，放到 已处理区间
    for (; p < r; p++) {
        if (a[p] < pivot) {
            // 将 a[i] 放到 已处理区间。
            tmp = a[p];
            a[p] = a[i];
            a[i] = tmp;    // 这里可以简写为 [x, y] = [y, x]
            i++;
        }
    }

    // 将 pivot（即a[r]）也放进 已处理区间
    tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;   
    return i;   
}

快速排序和归并排序都用到了分治思想，递推公式和递归代码很很相似。它们的区别在于：归并排序是 由下而上 的，排序的过程发生在子数组合并过程。而快速排序是 由上而下 的，分区的时候，数组就开始趋向于有序，直到最后区间长度为1，数组就变得有序。

性能分析

1. 快速排序的时间复杂度是 O(nlogn)

快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。但这个公式成立的前提是每次分区都能正好将区间平分（即最好时间复杂度）。

当然平均复杂度也是 O(nlongn)，不过不好推导，就不分析。

极端情况下，数组的数据已经有序，且取最后一个元素为 pivot，这样的分区是及其不均等的，共需要做大约 n 次的分区操作，才能完成快排。每次分区平均要扫描约 n/2 个元素。所以，快排的最坏时间复杂度是 O(n^2)

2. 快速排序是不稳定的排序

快速排序的分区过程，涉及到了交换操作，该交换操作类似 选择排序，是不稳定的排序。

3. 快速排序是原地排序

为了实现原地排序，我们前面对 parition 分区函数进行了巧妙的处理。

结尾

大概就是这样，做了简单的总结。如果文章有错误的地方，请给我留言。

还有一些排序打算下次再更新，可能会新开一篇文章，也可能直接修改这篇文章。

参考

数据结构与算法之美