07 排序

0.1. 分析排序算法

0.1.1. 执行效率

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

  1. 最好情况、最坏情况、平均情况时间复杂度（最好、最坏情况对应的待排序原始数据是什么样的？）：有序度不同的数据，对排序的执行时间有影响
  2. 时间复杂度的系数、常数 、低阶：实际开发中，待排序的数据规模是 10/100/1000 这样的小规模，所以，在对同一阶时间复杂度的排序算法性能对比时，要把系数、常数、低阶也考虑进来
  3. 比较次数和交换（或移动）次数：基于比较的排序算法的执行过程，会涉及元素比较和元素交换/移动的操作。所以，在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去

0.1.2. 内存消耗

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

0.1.3. 稳定性

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

排序算法是否稳定的影响，主要是在实际的软件开发中，使用对象的某个key来排序而非一个整数（key的先后顺序有实际的业务意义，而一个整数的先后顺序没有影响）。看下面具体的例子来感受一下。

现在要给电商交易系统中的“订单”排序。订单有两个属性：

  • 下单时间
  • 订单金额

排序的需求：

  1. 现在有 10 万条订单数据，按照金额从小到大对订单数据排序
  2. 对于金额相同的订单，按照下单时间从早到晚有序

最先想到的方法是：

  1. 先按照金额对订单数据进行排序
  2. 再遍历排序之后的订单数据，对于每个金额相同的小区间按照下单时间排序

这种排序思路理解起来不难，但是实现起来会很复杂。借助稳定排序算法，这个问题可以非常简洁地解决。

解决思路是这样的：

  1. 先按照下单时间（注意是按照下单时间，不是金额）给订单排序
  2. 排序完成之后，用稳定排序算法，按照订单金额重新排序

两遍排序之后，得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。

因为，稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。

  1. 第一次排序之后，所有的订单按照下单时间从早到晚有序
  2. 在第二次排序中，使用稳定排序算法，经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序

image

0.2. 常见排序算法

0.2.1. 冒泡排序

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

假设待排序数据为4,5,6,3,2,1，从小到大进行排序，第一次冒泡的详细过程如下图：

image

要完成所有数据的排序，需要进行6次冒泡操作：

image

将上述冒泡过程进行优化，当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再执行冒泡操作，如下示例：

image

  1. 在冒泡的过程，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 \(O(1)\)，是原地排序算法。
  2. 在冒泡的过程中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换，相同大小的数据在排序前后不会改变顺序，是稳定排序算法。
  3. 时间复杂度：
    1. 最好情况，待排序数据有序（满有序度），只需要进行一次冒泡，时间复杂度是\(O(n)\)
    2. 最坏情况，待排序数据倒序（有序度为0），要进行n次冒泡，时间复杂度是\(O(n^2)\)
    3. 平均情况，根据数据初始的有序度假设为满有序度的一般即\(\frac{n*(n-1)}{4}\)，时间复杂度是\(O(n^2)\)

0.2.1.1. 有序度

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示：a[i] <= a[j], 如果i < j 逆序度的定义正好跟有序度相反（默认从小到大为有序）：a[i] > a[j], 如果i < j

逆序度 = 满有序度 - 有序度。排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

如{2,4,3,1,5,6}的有序度是11，{6,5,4,3,2,1}的有序度是0。

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。

不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是\(\frac{n*(n-1)}{2}\)减去初始有序度。

0.2.2. 插入排序

使用动态排序向一个已经有序的数据集合中添加数据，插入后依然保持数据有序，即遍历数组，找到数据应该插入的位置将其插入即可。

对于一组静态数据（即数据集合的元素个数不变），借助上面的思想实现插入排序。

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

假设有待排序数据为4,5,6,3,2,1，左侧为已排序区间，右侧为未排序区间。

image

插入排序也包含两种操作：

  • 元素的比较
  • 元素的移动

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

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

  1. 插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 \(O(1)\)，是原地排序算法
  2. 在插入排序中，对于值相同的元素，可以将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定排序算法
  3. 时间复杂度
    1. 最好情况，待排序数据有序（满有序度），只需从尾到头遍历一遍有序数据，时间复杂度是\(O(n)\)
    2. 最坏情况，待排序数据倒序（有序度为0），则每次插入都相当于在数组的第一个位置插入新的数据，时间复杂度是\(O(n^2)\)
    3. 平均情况，（数组这种数据结构插入数据的平均时间复杂度是\(O(n)\)）对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度是\(O(n^2)\)

0.2.3. 选择排序

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

  1. 选择排序算法运行过程中不需要额外的空间，空间复杂度为 \(O(1)\)，是原地排序算法。
  2. 在选择排序中，对于值相同的元素，选择先出现的值为最小值，这样就可以保持原有的前后顺序不变，但是，最小值会和前面的数据交换位置，这会导致其他的相同值的位置改变，所以选择排序是不稳定排序算法
  3. 时间复杂度：
    1. 最好情况，待排序数据有序（满有序度），每个数据都要与数据集合中剩下的数据进行比较，时间复杂度\(O(n^2)\)
    2. 最坏情况，待排序数据倒序（有序度为0），每个数据都要与数据集合中剩下的数据进行比较，时间复杂度\(O(n^2)\)
    3. 平均情况，对选择排序来说，没有最好最坏情况，所有数据都要进行比较，时间复杂度\(O(n^2)\)

0.2.4. 插入比冒泡更受欢迎

冒泡排序和插入排序的时间复杂度都是 \(O(n^2)\)，都是原地排序算法：

  • 冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度
  • 插入排序不管怎么优化，元素移动的次数是一个固定值，是原始数据的逆序度

从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。

// 冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   a[j], a[j+1] = a[j+1], a[j]
   flag = true;
}

// 插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。

  • 冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时就是 3*K 单位时间。
  • 插入排序，数据移动操作只需要 K 个单位时间。
// 测试数据集合 []int{4, 5, 1, 6, 2, 3, 4, 5, 1, 6, 2, 3, 4, 5, 1, 6, 2, 3}

// 冒泡排序，每秒调用6659475次
goos: linux
goarch: amd64
pkg: deal/sort
BenchmarkBubbleSort
BenchmarkBubbleSort-4     6659475        183 ns/op
PASS

// 插入排序，每秒调用11622802次
goos: linux
goarch: amd64
pkg: deal/sort
BenchmarkInsertionSort
BenchmarkInsertionSort-4    11622802         99.2 ns/op
PASS

实际结果相差两倍，所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 \(O(n^2)\)，但是如果希望把性能优化做到极致，那肯定首选插入排序，它的算法思路也有很大的优化空间，如希尔排序。

0.2.5. 三者对比

特定算法依赖特定的数据结构，这三种算法都依赖数组实现。

算法是否原地排序是否稳定最好最坏平均
冒泡YY\(O(n)\)\(O(n^2)\)\(O(n^2)\)
插入YY\(O(n)\)\(O(n^2)\)\(O(n^2)\)
选择YN\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)

冒泡排序、插入排序、选择排序这三种排序算法，它们的平均时间复杂度都是 \(O(n^2)\)，比较高，适合小规模数据的排序。下面是两种时间复杂度为 \(O(nlogn)\) 的排序算法，归并排序和快速排序，都用到了分治的思想，适合大规模数据排序。

0.2.6. 归并排序

归并排序的核心思想是：

  1. 先把数组从中间分成前后两部分
  2. 然后对前后两部分分别排序
  3. 再将排好序的两部分合并在一起，这样整个数组就都有序了

image

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

分治思想和递归思想很像，分治算法一般都是用递归来实现。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。

归并排序使用分治思想，用递归实现：

  1. 分析递推公式：MergeSort(p...r)=merge(mergeSort(p...q)+mergeSort(q+1...r)),q=(p+r/2)
  2. 找到终止条件：p>=r
  3. 将递推公式翻译成递归代码

在递推公式中，mergeSort()函数是被分解后的子问题，merge()函数是将已经有序的前后两部分合并为一个整体有序的数据集合，具体过程如下：

  1. 在函数内申请一个临时数组
  2. 分别从头开始比较已经有序的前后两部分
  3. 将较小的那一个先放入临时数组中
  4. 继续整个过程直到一个子数组中没有数据
  5. 将剩下的数组中全部数据直接插入临时数组末尾
  6. 将临时数组中的数据拷贝到原数组中

0.2.6.1. 性能分析

  1. 归并排序稳不稳定关键要看 merge() 函数，即两个有序子数组合并成一个有序数组的那部分代码，可以保证值相同的元素，在合并前后的先后顺序不变，是稳定排序算法。

  2. 递归的是时间复杂度公式：\(T(a)=T(b)+T(c)+K\)，其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。所以归并排序的时间复杂度的计算公式是：

# n=1时，只需要常量级的执行时间，所以表示为C。
T(1) = C

# n>1
T(n) = 2*T(n/2) + n；

# 继续分解
T(n) = 2*T(n/2) + n
   = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
   = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
   = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
   ......
   = 2^k * T(n/2^k) + k * n
   ......

# 得到结果
T(n) = 2^k ×　T(n/2^k)　+　kn
# 当ｎ＝１时
T(n/2^k)=T(1)
n/2^k=1
k=log2n

# 将ｋ带入公式
T(n)=Cn+nlog2n

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 \(O(nlogn)\)。

不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。

  1. 在merge()函数中，创建了一个临时数据（额外申请的临时内存空间）用于存储中间结果。因此，归并排序不是原地排序算法，空间复杂度是\(O(n)\)。因为，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小。

0.2.7. 快速排序

快速排序，简称快排，利用的也是分治思想，有点像归并排序，但是思路完全不一样。快排的思想是：

  1. 要排序数组中下标从 p 到 r 之间的一组数据，选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
  2. 遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
  3. 经过这上述步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

image

分治的思想，可以用递归的方式来实现：

  1. 递推公式：QuickSort(p...r)=quickSort(p...q)+quickSort(q+1...r)
  2. 终止条件：p>=r
  3. 递推公式翻译为递归代码
// 快速排序，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（一般情况下，可以选择 p 到 r 区间的最后一个元素），然后对 \(A[p…r]\)分区，函数返回 pivot 的下标。

在不考虑空间复杂度的情况下，申请两个临时数组分别存放大于和小于pivot的数据，最后将两个数组的数据以此拷贝到原数组中。

希望快排是原地排序算法，即空间复杂度得是 \(O(1)\)，所以 partition() 分区函数就不能占用太多额外的内存空间，就需要在 \(A[p…r]\)的原地完成分区操作。

func partition(list []int, head int, tail int) int {
 pivot := list[tail]
 i := head
 for j := head; j < tail; j++ {
  if list[j] < pivot {
    list[i], list[j] = list[j], list[i]
   i++
  }
 }
// 遍历一遍数组，说明i之前的都是小于pivot
// 交换i与pivot的值
 list[i], list[tail] = list[tail], list[i]
 return i
}

这里的处理有点类似选择排序：

  1. 通过游标 i 把 \(A[p…r-1]\)分成两部分
  2. \(A[p…i-1]\)的元素都是小于 pivot 的，称为“已处理区间”，\(A[i…r-1]\)是“未处理区间”
  3. 每次都从未处理的区间 \(A[i…r-1]\) 中取一个元素 \(A[j]\)，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 \(A[i]\) 的位置

数组的插入操作，需要搬移数据，非常耗时。有一种处理技巧，就是交换，在 \(O(1)\) 的时间复杂度内完成插入操作。这里借助这个思想，只需要将 \(A[i]\) 与 \(A[j]\) 交换，就可以在 \(O(1)\) 时间复杂度内将\(A[j]\)放到下标为 i 的位置。

image

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，那么元素的位置可能发生改变，所以快速排序不是稳定的排序算法。

0.2.7.1. 性能分析

  1. 时间复杂度

快排也是递归实现的，根据归并的分析思路，快排的时间复杂度也是\(O(nlogn)\)：

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

这里的前提条件是，pivot的选择很合适刚好可以将数组分成比较均匀的两部分，这是一种最好情况。

那么在最坏情况下，pivot不能将数组划分的较均匀，如原数组已经有序，需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 \(\frac{n}{2}\) 个元素，这种情况下，快排的时间复杂度就从 \(O(nlogn)\) 退化成了 \(O(n^2)\)。

  1. 空间复杂度：\(O(1)\)，不稳定的原地排序算法。

0.2.8. 归并与快排对比

image

  • 归并排序的处理过程是由下到上，先处理子问题，然后再合并。

  • 快速排序的处理过程是由上到下，先分区，然后再处理子问题。

  • 归并排序虽然是稳定的、时间复杂度很稳定为 \(O(nlogn)\) 的排序算法，但它是非原地排序算法（合并函数无法在原地执行），所以应用没有快排广泛。

  • 快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

算法是否原地排序是否稳定最好最坏平均
归并NY\(O(nlogn)\)\(O(nlogn)\)\(O(nlogn)\)
快排YN\(O(nlogn)\)\(O(n^2)\)\(O(nlogn)\)

0.3. 线性排序算法

时间复杂度都是线性的，因为是非基于比较的排序算法，不涉及元素之间的比较操作，但是对要排序的数据要求很苛刻，所以重点的是掌握这些排序算法的适用场景。

0.3.1. 桶排序

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

image

时间复杂度：

  1. 假设待排序的数据有 n 个，
  2. 把它们均匀地划分到 m 个桶内，每个桶里就有 \(k=\frac{n}{m}\) 个元素。
  3. 每个桶内部使用快速排序，时间复杂度为 \(O(k *logk)\)。
  4. m 个桶排序的时间复杂度就是 \(O(m*k*logk)\)，因为 \(k=\frac{n}{m}\)，所以整个桶排序的时间复杂度就是 \(O(n*log(\frac{n}{m}))\)。
  5. 当桶的个数 m 接近数据个数 n 时，\(log(\frac{n}{m})\) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 \(O(n)\)

桶排序对数据的要求非常苛刻：

  1. 待排序数据需要容易划分成 m 个桶，并且，桶与桶之间有天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
  2. 数据在各个桶之间的分布要比较均匀，否则桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 \(O(nlogn)\) 的排序算法了。

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

0.3.2. 计数排序

计数排序是桶排序的一种特例。当要排序的 n 个数据，这n个数据的范围并不大，如最大值是 k，把数据划分成 k 个桶，那么每个桶内的数据的值都是相同的，只是每个桶内的数据量不同，这样省掉了桶内排序的时间，只需要遍历数据并放入对应的桶中。

0.3.2.1. 例子

假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩放在一个数组 \(A[8]\)中，它们分别是：2，5，3，0，2，3，0，3。

考生的成绩从 0 到 5 分，使用大小为 6 的数组 \(C[6]\)表示桶，其中下标对应分数。\(C[6]\)内存储的并不是考生，而是对应的考生个数，只需要遍历一遍考生分数，就可以得到 \(C[6]\)的值。

分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以，成绩为 3 分的考生在排序之后的有序数组 \(R[8]\)中，会保存下标 4，5，6 的位置。

A[8]={2,5,3,0,2,3,0,3}
C[6]={2,0,2,3,0,1}
R[8]={0,0,2,2,3,3,3,5}

如何快速计算出，每个分数的考生在有序数组\(R[8]\)中对应的存储位置呢？这个处理方法非常巧妙，很不容易想到。

思路是这样的：对 \(C[6]\)数组顺序求和，\(C[6]\)存储的数据就变成了下面这样子。\(C[k]\)里存储小于等于分数 k 的考生个数。

C[6]={2,2,4,7,7,8}

数据准备完成后开始计数排序：

  1. 从后到前（算法稳定的根源）依次扫描数组 A，当扫描到 3 时，从数组 C 中取出下标为 3 的值 7
  2. 到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个
    1. 也就是说， 3 是数组 R 中的第 7 个元素
    2. 也就是说，数组 R 中下标为 6 的位置
  3. 把 3 放入到数组 R 中
  4. 此时小于等于 3 的元素就只剩下了 6 个了，所以相应的 \(C[3]\)要减 1，变成 6
  5. 以此类推，扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的

image

这种利用另外一个数组来计数的实现方式就很巧妙了。

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

如果数据精确到小数点后一位，需要将数据都乘以10转化为整数；如果数据是\([-1000,1000]\)需要将数据都加1000转化为整数。

0.3.3. 基数排序

如何实现手机号码的排序，借助稳定排序算法，这里有一个巧妙的实现思路：

  1. 先按照最后一位来排序手机号码，
  2. 再按照倒数第二位重新排序，
  3. 以此类推，
  4. 最后按照第一位重新排序。
  5. 经过 11 次排序之后，手机号码就都有序了。

注意，这里按照每位来排序的排序算法要是稳定的，否则最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。

根据每一位来排序，可以用桶排序或者计数排序，它们的时间复杂度是 \(O(n)\)。

如果要排序的数据有 k 位，就需要 k 次桶排序或者计数排序，总的时间复杂度是 \(O(k*n)\)。当 k 不大的时候，基数排序的时间复杂度就近似于 \(O(n)\)。

对于非等长数据排序，如字典中的英文单词。可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，然后就可以使用基数排序。

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

0.4. 排序优化

0.4.1. 选择合适的排序算法

算法时间复杂度稳定原地
冒泡\(O(n^2)\)YY
插入\(O(n^2)\)YY
选择\(O(n^2)\)YY
归并\(O(nlogn)\)YN
快排\(O(nlogn)\)NY
桶\(o(n+k)\)，k是数据范围YN
计数\(o(n)\)YN
基数\(o(dn)\)，d是维度YN
  1. 线性排序算法的时间复杂度比较低，适用场景比较特殊
  2. 如果对小规模数据进行排序，选择时间复杂度是 \(O(n^2)\) 的算法
  3. 如果对大规模数据进行排序，选择时间复杂度是 \(O(nlogn)\) 的算法更加高效
  4. 归并排序空间复杂度是\(O(n)\)，消耗的内存空间翻倍，应用不广泛
  5. 快速排序在最坏情况下的时间复杂度是 \(O(n^2)\)，需要优化一下，降低出现最坏情况的概率

0.4.2. 优化快速排序

如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为 \(O(n^2)\)，主要原因是分区点选的不够合理。

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

如果很粗暴地直接选择第一个或者最后一个数据作为分区点，不考虑数据的特点，肯定会出现最坏情况，时间复杂度是 \(O(n^2)\)。

为了提高排序算法的性能，要尽可能地让每次分区都比较平均。下面是两种比较常见和简单的分区算法：

  • 三数取中法：从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点（如果要排序的数组比较大，可用“五数取中”或者“十数取中”）
  • 随机法：每次从要排序的区间中，随机选择一个元素作为分区点，从概率的角度来看，不大可能会出现每次分区点都选的很差的情况
  • 更多其他的方法

快速排序使用递归实现，因此递归存在的问题，快排也需要注意警惕堆栈溢出：

  • 限制递归深度
  • 通过在堆上模拟手动实现函数调用栈手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制

0.4.3. 实例

glibc中的qsort()函数：

  1. qsort() 会优先使用归并排序来排序输入数据（数据量小，空间换时间，归并时间复杂度稳定）
  2. 要排序的数据量比较大的时候，qsort() 会改为用快速排序算法来排序（数据量大，时间换空间）
  3. 通过实现堆上栈来解决递归过深导致堆栈溢出的问题
  4. 在快排过程中，当待排序区间中，元素的个数<=4 时，qsort()退化为插入排序（小规模数据量，\(O(n^2)\) 时间复杂度并不一定比 \(O(nlogn)\) 执行时间长）

算法的性能可以通过时间复杂度来分析，但是，这种复杂度分析是比较偏理论的，实际上时间复杂度并不等于代码实际的运行时间。时间复杂度代表的是一个增长趋势。对于小数据量的排序，可以选择比较简单、不需要递归的插入排序算法。

假设 k=1000，c=200，当对小规模数据（比如 n=100）排序时，\(n^2\)的值实际上比 \(knlogn+c\) 还要小。

knlogn+c = 1000 * 100 * log100 + 200 远大于10000

n^2 = 100*100 = 10000
// 对于小规模数据的排序，O(n^2) 的排序算法并不一定比 O(nlogn) 排序算法执行的时间长
上次修改: 22 June 2020