如何分析一个“排序算法”？

排序算法的执行效率

对于排序算法执行效率的分析，我们一般会从这几个方面来衡量：

1. 最好情况、最坏情况、平均情况时间复杂度

我们在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

2. 时间复杂度的系数、常数 、低阶

我们知道，时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

3. 比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

带你看下冒泡排序的整个过程。我们要对一组数据 4，5，6，3，2，1，从小到大进行排序。第一次冒泡操作的详细过程就是这样：

排序算法 - 图1

可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。

排序算法 - 图2

实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。这里还有另外一个例子，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。

排序算法 - 图3

  1. function bubbleSort(a, n) {
  2.   if (n <=1) return;
  3.   for(let i = 0; i < n;i++) {
  4.     // 提前退出冒泡循环的标志位
  5.       let flag = false;
  6.     for(let j = 0; j < n - i - 1; j++) {
  7.         if (a[j] > a[j+1]) { // 交换
  8.         let tmp = a[j];
  9.         a[j] = a[j+1];
  10.         a[j+1] = tmp;
  11.         flag = true; // 表示有数据交换   
  12.       }
  13.     }
  14.     if (!flag) break;  // 没有数据交换，提前退出
  15.   }
  16. }

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

时间复杂度就是 O(n2)。

插入排序（Insertion Sort）

我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

排序算法 - 图4

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

  1. function insertionSort(a, n) {
  2.     if (n <= 1) return;
  3.   for(let i = 1; i < n; i++) {
  4.       let value = arr[i];
  5.     let j = i - 1;
  6.     for(; j >=0; j--) {
  7.         if (arr[j] > value) {
  8.           arr[j + 1] = a[j];
  9.       } else {
  10.           break;
  11.       }
  12.     }
  13.     a[j + 1] = value;
  14.   }
  15. }

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

时间复杂度为 O(n2)。

选择排序（Selection Sort）

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

排序算法 - 图5

  1. function selectSort(a, n) {
  2.         if (n <= 1) return;
  3.   for(let i = 0; i< n; i++) {
  4.       let min = i;
  5.     for(let j = i + 1; j < n; j++){
  6.         if (a[j] < a[min]) {
  7.           min = j;
  8.       }
  9.     }
  10.     if (min !== i) {
  11.         let temp = arr[i];
  12.       arr[i] = arr[min];
  13.       arr[min] = temp;
  14.     }
  15.   }
  16. }

选择排序空间复杂度为 O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

归并排序

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

排序算法 - 图6

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

  1. function merge_sort(a, p, r) {
  2.   if (p >= r) return;
  3.   let q = Math.floor((p + r) / 2);
  4.   merge_sort(a, p, q);
  5.   merge_sort(a, q +1, r);
  6.   merge(a, p, q, r);
  7. }
  9. function merge(a, p, q, r) {
  10.   let i = p;
  11.   let j = q + 1;
  12.   let k = 0;
  13.   let temp = [];
  14.   while(i <= q && j <= r) {
  15.     if (a[i] <= a[j]) {
  16.       temp[k++] = a[i++];
  17.     } else {
  18.       temp[k++] = a[j++];
  19.     }
  20.   }
  21.   while(i <= q) {
  22.     temp[k++] = a[i++]
  23.   }
  24.   while(j <= r) {
  25.     temp[k++] = a[j++];
  26.   }
  27.   for(let l = 0; l< k;l++) {
  28.     a[l + p] = temp[l];
  29.   }
  30. }

排序算法 - 图7

归并排序是一个稳定的排序算法。时间复杂度是 O(nlogn)。空间复杂度是 O(n)。

快速排序

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

排序算法 - 图8

  1. function swap(A, i, j) {
  2.     const t = A[i];
  3.     A[i] = A[j];
  4.     A[j] = t;
  5. }
  6. function quickSort(A, p, r) {
  7.   if (p >= r) return;
  8.   let q = partition(A, p, r);
  9.   quickSort(A, p, q - 1);
  10.   quickSort(A, q + 1, r);
  11. }
  12. function partition(A, p, r) {
  13.   let pivot = A[r];
  14.   let i = p;
  15.   for (let j = p; j < r; j++) {
  16.     if (A[j] < pivot) {
  17.       swap(A, i, j);
  18.       i++;
  19.     }
  20.   }
  21.   swap(A, i, r);
  22.   return i;
  23. }

排序算法 - 图9

快排是一种原地、不稳定的排序算法。快排的时间复杂度也是 O(nlogn)。

桶排序（Bucket sort）

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

排序算法 - 图10

计数排序（Counting sort）

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

基数排序（Radix sort）