Super Agents of AI

本节主要讲解下列排序算法：

排序算法的执行效率:

1. 最好情况、最坏情况、平均情况时间复杂度
2. 事假复杂度的系数、常数、低阶
3. 比较次数和交换（移动）次数
4. 排序算法的内存消耗：原地排序是指空间复杂度是O(1)的排序算法
5. 排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后相等元素之间原有的先后顺序不变

如何对10完条订单数据按照金额从小到大对订单数据排序:

先按照下单时间给订单排序，排序完成之后，使用稳定排序算法，按照订单金额重新排序，示意图如下：

冒泡、插入和选择排序

冒泡、插入和选择排序的特点如下图所示：

冒泡和选择排序实际开发应用并不多，学习的目的是开阔思维，插入排序在其他的排序函数中会用到。

冒泡排序: Bubble Sort

冒泡排序只会操作相邻的两个数据。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成n个数据的排序操作。

第一次冒泡操作的示意图如下：

经过六次冒泡操作之后的结果如下：

冒泡排序可以提前结束，判断冒泡过程中是否有元素交换即可：

JAVA代码如下：

// 冒泡排序，a 表示数组，n 表示数组大小
public void bubbleSort(int[] a, int n) {
 if (n <= 1) return;
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

冒泡排序特点

• 冒泡过程只涉及相邻数据的交换操作，只需要常量级的临时空间，其空间复杂度为O(1)，是原地排序算法
• 在冒泡排序过程中，只有交换才可以改变两个元素的前后顺序，当两个元素相等时，不交换，即可保证冒泡排序是稳定的排序
• 最好的时间复杂度是O(n)，即要排序的数据已经有序
• 最坏情况是O(n^2)，完全倒序排列

有序度是数组中具有有序关系的元素个数。有序元素对用数学表达式表示公式：

$$ 有序元素对： a[i] <= a[j], if i < j $$

计算示意图如下：

对于一个倒序排列的数组有序度是0. 对于一个完全有序的数组，如[1,2,3,4,5,6]，有序度就是n*(n-1)/2，也就是15。我们将这种完全有序的数组叫做满有序度。

逆序度指数组中具有逆序关系的元素个数，表达式为：

$$ 逆序元素对： a[i] > a[j], if i < j $$

关于这三个概念，有一个公式：逆序度=满有序度-有序度

排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度。

冒泡排序包含两个操作原子，比较和交换，每交换一次，有序度就加1。不管算法怎么变，交换次数是一定的，即为逆序度，也就是n*(n-1)/2-初始有序度。上图中，满有序度为15，有序度为3，逆序度=15-3=12，即代表需要12词交换操作。

插入排序：Insertion Sort

对于一个有序的数组，可以通过遍历数组，找到数据应该插入的位置将其插入的方法添加新的数据并且保持数组有序，这是一个动态排序的过程，示意图如下：

插入排序将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。核心思想是取未排序区间中的元素，在以排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序，重复这个过程，知道排序完成。示意图如下：

插入排序包含元素的比较和移动两个操作。对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的，但是对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。示意图如下：

满有序度为n*(n-1)=12，初始有序度为5，逆序度=移动操作次数=5。

Java代码如下:

// 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

插入排序特点

• 空间复杂度O(1)，是一个原地排序算法
• 对于值相同的元素，可以选择将后面出现的元素，插入到前面出现的元素的后面，这样保持原有的前后顺序不变，故插排是稳定的排序算法
• 完全有序的情况下，从尾到头遍历已经有序的数据，插排的时间复杂度是O(n)；如果是倒序的，每次插入都相当于在数组的第一个位置插入新数据，需要移动大量的数据，最坏时间复杂度为O(n^2)；平均时间复杂度为O(n^2)

选择排序：Selection Sort

选择排序和插入排序想法类似，也分为已排序区间和未排序区间，但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。示意图如下：

选择排序的特点

• 空间复杂度为O(1)，是一种原地排序算法
• 最好时间复杂度、最坏时间复杂度和平均情况时间复杂度都是O(n^2)
• 不是稳定的算法：选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性

为什么插入排序要比冒泡排序好

对于冒泡排序和插入排序，不管代码怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。

从代码实现上看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要三个赋值操作，而插入排序只需要一个，因此，针对同样的数据排序，插入排序的时间复杂度要好于冒泡排序。代码如下：

冒泡排序中数据的交换操作：
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;
}

改进版本的插入排序是希尔排序，通过设置逐渐变小的交换步长来将减少一个数最终交换的次数，代码如下：

def shell_sort(list):
    n = len(list)
    # 初始步長
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步長進行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步長
        gap = gap // 2
    return list

归并排序和快速排序

归并排序和快速排序都运用到了分治思想。

归并排序：Merge Sort

归并排序的核心思想是将要排序的数组，先从中间分成前后两个部分，然后对前后两个部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了，示意图如下：

分治的思想就是分而治之，将一个大问题分解为小的问题，小的问题解决了，大问题也就解决了。分治一般都是用递归来实现的，分治是一种解决问题的处理思想，递归是一种编程思想，两者并不冲突。

归并排序的递推公式：

$$ merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) $$

终止条件：

$$ p >= r 不用再继续分解 $$

伪代码如下：

// 归并排序算法, A 是数组，n 表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return

  // 取 p 到 r 之间的中间位置 q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

merge函数的作用是将A[p…q]和A[q+1…r]两个已经排好序的数组合并为一个A[p…r]的有序数组，示意图如下：

伪代码如下：

merge(A[p...r], A[p...q], A[q+1...r]) {
  var i := p，j := q+1，k := 0 // 初始化变量 i, j, k
  var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
  while i<=q AND j<=r do {
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++ 等于 i:=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }
  
  // 判断哪个子数组中有剩余的数据
  var start := i，end := q
  if j<=r then start := j, end:=r
  
  // 将剩余的数据拷贝到临时数组 tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }
  
  // 将 tmp 中的数组拷贝回 A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

归并排序的特点

• 归并排序是稳定的算法
• 归并排序的时间复杂度是O(nlogn)
• 归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，最好情况、最坏情况、平均时间复杂度都是O(nlogn)
• 尽管归并排序的时间复杂度都是O(nlogn)，但是它的致命弱点是空间复杂度为O(n)，即不是原地排序算法。因为在合并两个已排序数组的过程中，需要额外申请临时空间保存结果。

快速排序：Quick Sort

快速排序也是使用了分治思想，核心思想是：如果要排序数组A[p,r]，选择p到r之间的任意一个数据作为分区点pivot，位置记为q，遍历A[p,r]，将小于pivot的放到左边，大于pivot的放到右边，将pivot放到中间。经过一次该操作，A[p,r]被分成了三个部分，左边是小于pivot的数，中间是等于pivot的数，右边是大于pivot的数，示意图如下：

然后根据分治、递归的思想，递归排序下标A[p,q-1]和A[q+1,r]之间的数，直到区间缩小为1，就说明排序完成了。

快排的递推公式：

$$ quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r) $$

终止条件：

$$ p >= r $$

快排的伪代码如下：

// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

关键是partition分区函数，最简单的方法是将数组最后一个元素的值选为pivot，如果不考虑空间消耗的话，可以临时申请两个数组，分别存储小于pivot和大于pivot的值，然后再拷贝到A中，示意图如下：

但是这样的话快排就不是原地排序算法，原地分区函数的实现思路如下：

partition(A, p, r) {
  pivot := A[r]
  i := p
  for j := p to r-1 do {
    if A[j] < pivot {
      swap A[i] with A[j]
      i := i+1
    }
  }
  swap A[i] with A[r]
  return i

分区过程的示意图如下：

快速排序的特点

• 快排是不稳定的算法
• 快排是原地算法
• 快排最好时间复杂度是O(nlogn)，平均时间复杂度是O(nlogn)，最坏是O(n^2)，但是可以通过合理地选择pivot来避免算法时间复杂度退化到O(n^2)的情况

归并排序 VS 快速排序

从上图可以发现，归并排序的过程是由下到上的，先处理子问题，然后再合并；而快排刚好相反，处理过程是由上到下的，先分区，然后在处理子问题。归并排序尽管时间复杂度都是O(nlogn)，但是是非原地算法，主要原因是合并函数无法在原地进行，快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

如何用快排思想在O(n)内查找第K个大元素

快排的核心思想是分治和分区，可以利用分区的思想来解决求第K大元素的问题。分区函数会将数组分为三个部分，通过比较三个部分的下标值即可判断第K个大的元素的值。

线性排序

线性时间复杂度的排序算法：桶排序、计数排序、基数排序。主要原因是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序：Bucket Sort

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

桶排序对于数据的要求非常的严格：

1. 数据要很容易就能划分成m个桶
2. 桶与桶之间有着天然的大小顺序，这样每个桶内的数据拍完序之后，桶与桶之间的数据不需要在进行排序
3. 数据在各个桶之间的分布是比较均匀的，极端情况下，数据都被划分到一个桶中，就退化为O(nlogn)的排序算法了

桶排序比较适合用于在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

如何给10GB文件排序

针对10GB文件的排序问题，内存有限。可以先扫描一遍数据，看关心数据的取值范围是多少[min, max]，然后将原始文件划分到m个桶里，每个桶代表一个文件，如果数据不均匀，某个桶里的数据仍然超过内存上限，那么将该桶继续划分为多个桶文件，直到单个文件可以放入内存中为止。每个桶中进行快排，最后按照顺序将桶文件读取出来写到另一个文件中即可。

计数排序 Counting Sort

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

如何给50万高考考生成绩排名

扫描遍历所有考生的成绩，将考生划分到[o,max_score]区间中，每个区间统计得分的人数，这样只需要执行一遍即可得出考生的排名信息。

计数排序的代码如下：

// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入 c 中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组 r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给 a 数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

计数排序只能用在数据范围不大的场景中，如果数据范围K比要排序的数据n大很多，就不适合用计数排序了。而且计数排序只能给非负整数排序，如果要排序的数据方式其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。方法如下：

• 如有学生成绩精确到小数点后一位，就先将分数都乘以10，转化为整数，再分桶
• 如果要排序的数据中有负数，数据的范围是[-1000,1000]，就将所有值先加1000，转化成非负数

基数排序 Radix Sort

计数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，计数排序的时间复杂度就无法做到O(n)。

如何对10个手机号码进行排序

利用基数排序的思想，先排序最后一位，然后排序倒数第二位，依次类推，知道最高位。用字符串表示的过程如下：

需要注意这里每位来排序的排序算法要是稳定的，否则这个实现思路就不正确。如果不稳定的排序算法，第i位的排序只会考虑第i位的顺序，而不会管第i-1位的排序结果，这样排序结果的就错了。

根据每一位来排序，可以用刚才的桶排序或者计数排序，时间复杂度是O(n)，如果要排序的数据有K位，那么就需要K次桶排序或者计数排序，总的时间复杂度就是O(k*n)。当K不大的时候，如手机号码的例子，计数排序的时间复杂度就近似于O(n)。

针对要排序的数据并不是等长度的情况，如排序20万个英文单词，我们可以把所有的单词补齐到相同长度，位数不够的可以在前面补“0”，因为根据ASCII值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序，这样就可以继续用计数排序了。

如何根据年龄给100万用户排序

假设年轻的范围为[1,120]岁，遍历这100万个用户，根据年龄将其划分到120个桶中，然后依次顺序遍历这120个桶中的元素，这样就得到了按照年龄排序的100万用户数据。

线性时间复杂度排序算法总结

线性时间复杂度的三种方法桶排序、计数排序、基数排序，它们对于数据都有严苛的要求，应用不是很广泛。

• 桶排序和计数排序的思想比较相似，都是针对范围不大的数据，将数据划分成不同的桶来实现排序
• 基数排序要求数据可以划分成高低位，位之间有递进关系，高位比低位大，就不用继续比较了，对于每一位的数据范围不能太大，因为基数排序需要借助桶排序或者计数排序来完成每一个位的排序工作

排序优化

常见的排序算法特点：

如何设计一个通用的、高效的排序函数

• 线性排序算法的时间复杂度比较低，适用场景比较特殊，不能选择作为通用排序函数
• 对于小规模数据排序，可以选择时间复杂度方式O(n^2)的算法
• 如果对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效

因此，为了兼顾任意规模数据的排序，一般都会选择时间复杂度是O(nlogn)的排序算法来实现排序函数。

Java语言采用堆排序实现排序函数，C语言采用快速排序实现排序函数。

快排与归并排序相比，不需要额外的空间复杂度，在数据量大的情况下，内存的消耗需要特别考虑才行，因此快排经常被用来作为通用的、高效排序算法。

如何优化快速排序时间复杂度

快排在最差的情况下的时间复杂度是O(n^2)，即是当数据原来就是有序或者接近有序的时候，每次分区点都选择最后一个数据，造成快速排序的时间复杂度退化为O(n^2)。实际上，这种情况出现的主要原因是因为我们分区点选的不够合理。

最理想的分区点是： 被分区点分开的两个分区中，数据的数量差不多。因此，为了提高快排算法的性能，我们要尽可能地让每次分区都比较平均。

快排是使用递归实现的，因此要警惕递归溢出，第一种限制是递归深度，一旦递归过深，超过了事先设定的阈值，就停止递归，第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就会没有了系统栈大小的限制。

三数取中法

从区间的首、尾、中间，分别取出一个数，然后对比大小，取这三个数的中间值作为分区点。如果待排序的数据比较大，得改成“五数取中”或者“十数取中”。

随机法

随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。

举例分析排序函数

Glibc中的qsort()函数：

• 当数据量小时，会优先调用归并排序来排序函数，当要排序的数据量比较大的时候，qsort()会改为用快速排序算法来排序
• qsort()底层分区点的选择方法是三数取中法
• 当要排序的区间中，元素的个数小于等于4时，qsort()就退化为插入排序，不再继续用递归来做快速排序
• 在插入排序的过程中使用哨兵减少判断，将性能优化到极致

在小规模的数据面前，O(n^2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。

注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。

Note: Cover Picture