排序算法

排序算法分析

算法 时间复杂度 是否基于比较
冒泡、插入、选择 O(n^2) 是
快排、归并 O(nlogn) 是
桶、计数、基数 O(n) 否

算法的执行效率

  • 最好、最坏、平均情况时间复杂度比较：根据数据的特点(无序、基本有序等)选择合适的算法。
  • 时间复杂度的系数、常数、低阶：数据规模很大时一般忽略了这几个量，但是当同一阶的算法比较时也需要把这几个量考虑进来
  • 比较次数和交换次数：基于比较的算法有两个操作：比较和移动，在分析效率时也需要考虑。

算法的内存消耗

  • 数据量较大时，执行时也需要考虑内存的消耗，原地排序特指空间复杂度是 $O(1)$ 的排序算法。

排序算法的稳定性

  • 稳定性：排序队列中存在值相同的元素，经过排序之后想等元素之间原有的先后顺序不变。（这个特点主要实际项目中一组对象的排序时比较重要）

冒泡排序

比较相邻的两个元素，并且移动元素让其满足大小关系要求。经过一次冒泡至少有一个元素移动到他应该在的位置。

复杂度分析

稳定性：冒泡排序中相等的两个元素不做交换时是稳定的排序算法
空间复杂度：只需要常量级的临时空间，空间复杂度为 $O(1)$，是一个原地排序算法
时间复杂度：

  • 最好的情况下只需要一次冒泡：时间复杂度为：$O(1)$
  • 最坏的情况下是需要 n 次，时间复杂度为：$O(n^2)$
  • 平均时间复杂度：$O(n^2)$

有序度

数组中具有有序关系的元素对的个数，比如 [2,4,3,1,5,6] 这组数据的有序度就是 11，分别是 [2,4][2,3][2,5][2,6][4,5][4,6][3,5][3,6][1,5][1,6][5,6]。对于一个倒序数组，比如 [6,5,4,3,2,1]，有序度是 0；对于一个完全有序的数组，比如 [1,2,3,4,5,6]，有序度为 $n(n-1)/2$，完全有序的情况称为满有序度。即有 *逆序度=满有序度-有序度**。
排序过程，就是有序度增加，逆序度减少的过程，最后达到满有序度。

插入排序

通过比较将无序队列中的元素不断的插入到有序队列中。插入时要保证有序队列是一直有序的。

复杂度分析

稳定性：出现相等的元素可以保持插入到前面元素的后面，即是稳定的。

空间复杂度：插入排序不需要额外的空间，复杂度为 $O(1)$，是原地排序。

时间复杂度：

  • 最好的情况下只需要一次冒泡：时间复杂度为：$O(1)$
  • 最坏的情况下是需要 n 次，时间复杂度为 $O(n^2)$。
  • 平均时间复杂度为 $O(n^2)$

选择排序

区分有序和无序队列，每次从无序队列中找出最小元素发到有序队列的末尾。

复杂度分析

稳定性：不能保证稳定性。例如：5，8，5，2，9第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了。
空间复杂度：插入排序不需要额外的空间，复杂度为 $O(1)$，是原地排序。
时间复杂度：

  • 最好的情况下只需要一次冒泡：时间复杂度为：$O(1)$
  • 最坏的情况下是需要 n 次，时间复杂度为 $O(n^2)$。
  • 平均时间复杂度为 $O(n^2)$

归并排序

归并排序采用分治思想，将整体划分为小部分，最后归并在一起达到整体有序。

实现

分治和递归比较相像，分治是一种解决问题的思想，递归是一种编程技巧。归并排序的递归公式：

1
2
3
4
// 递推公式
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q + 1, r))
// 终止条件，当子数组不可再分解
p >= r

伪代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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 函数将有序子数组合并，伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
merge(A[p, r], A[p, q], A[q + 1, r]) {
    var i = p, j = q + 1, k = 0
    //申请一个和 A[p, r]一样大的数组
    var temp = new Array[0, r - p]
    while(i <= q AND j <= r) do {
        if A[i] < A[j] {
            temp[k++] = A[i++]
        } else {
            temp[k++] = A[j++]
        }
    }
    //判断哪个子数组中只有剩余元素将其拷贝到temp
    var start = i, end = q
    if j <= r then start = j, end = r
    //将剩余数组拷贝到临时数组中
    while start <= end do {
        temp[k++] = A[start++]
    }
    //将临时数组拷贝到 A 数组中
    A = temp
}

复杂度分析

稳定性

归并排序是否稳定主要是最后的 merge 函数，合并的时候如果遇到值相等的元素，保持 A[p, q] 的元素在前即可保证稳定性。

时间复杂度

归并排序采用了分治的思想，时间复杂度是求解各个子问题的和加上最后归并的时间。

1
2
//将问题 a 分解为 b 和 c，K是最后合并b和c的时间 
T(a) = T(b) + T(c) + K

归并排序的复杂度公示：

1
2
3
4
5
6
7
8
9
10
11
T(1) = C;

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(1)$ 时，有 

1
2
3
4
5
n/2^k = 1

k = nlog_2n

T(n) = 2^kT(n/2^k) + kn = 2^kC + kn = nC + nlog_2n

归并排序和原数组的有序程度无关，时间复杂度都是 $nlog_2n$

空间复杂度

归并排序需要开辟和原数组一样大的空间辅助排序，空间复杂度时 $O(n)$

快速排序

快速排序也利用分治思想，对 A[p, r] 进行排序，选择 p-r 之间任意一个数据 pivot 作为分区点，遍历 p-r 的数据，将小于 pivot 的数据移到左边，大于 pivot 的数据放到右边，pivot 的位置为 q，原数组分为 A[p, q-1]、A[q] 和 A[q+1, r]，如此区分直到区间缩小为1，则所有数据都有序。

实现

1
2
3
4
// 递推公式：
quick_sort(p, r) = quick_sort(p, q-1) + quick_sort(q+1, r)
//终止条件：
p >= r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 快速排序，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(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

这里分区函数的处理类似于插入排序，将 A[p, r-1] 分为两部分，A[p, i-1] 的元素都小于 pivot，暂叫做已处理区间，每次从未处理区间 A[i, r-1] 取出一个元素和 pivot 比较，如果小于则交换到未处理区间

复杂度分析

稳定性

由于分区函数存在元素交换，所以快速排序是不稳定的算法

时间复杂度

正常情况下，如果分区合理则快速排序的时间复杂度与归并排序一样是 $O(nlog_2n)$

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

如果选择的最后一个分区元素是最大的，则分区就不均衡，会退化成 $O(n^2)$

空间复杂度

在排序过程中，分区函数的实现在原数组中，原地处理。空间复杂度是 $O(1)$

归并排序与快速排序区别

  • 归并排序：先递归调用然后合并处理。从下往上先处理子问题。
  • 快速排序：先分区在递归调用，从上往下处理，到最后已经有序。

选择分区点

  • 三位取中法：从区间的首、中、尾分别选取三个元素，选取三个元素的中位元素位置作为分区点
  • 随机法：随机选取元素作为分区点，降低最大元素成为分区点的概率

桶排序

先对原有的值域进行划分，将元素区分到每个桶中，然后每个桶各自排序，最后将桶合并。桶排序是针对一些有特征的数据集效果较好。

实现

  • 值域划分，通过规则将每个元素映射到对应的桶，确定桶的个数。需要根据数据集的特征来确定映射规则。例如：
    1
    2
    3
    // f(x) 是元素 x 所在桶的编号；length 是原数据集的大小
    f(x) = (x - min) / length
    bucketNum = (max - min) / length + 1
  • 排序算法，每个桶的排序算法可以自定。

复杂度分析

时间复杂度

数据集有 n 个元素，桶的个数为 m，如果是均匀的划分，每个桶内的元素个数为 $k = n/m$。桶内使用快速排序来实现，每个桶的时间复杂度是 $O(klogk)$，m 个桶的时间为 $O(mklogk)$，$k = n/m$ 则有 $O(nlog(n/m))$，当桶的个数接近 n 时，则时间复杂度接近为 $O(n)$。

空间复杂度

需要申请 m 个桶空间，整体的空间复杂度是 $O(m + n)$

稳定性

桶排序的稳定性与每个桶内所采用的排序算法相关

计数排序

通过辅助数组，遍历原集合将每个元素标记在对应的位置，遇到相同的元素则对应的位置计数器自增。

实现

  • 计算辅助数组的大小
    1
    size = max + 1
  • 遍历待排序集合，将每个元素出现的次数记录到辅助数组中
  • 计算每个元素的最终位置，从后往前遍历保证稳定性
  • 例如，数组 A[2, 4, 5, 3, 4, 1]：
  • 辅助数组大小为 6，遍历后得到 C[0, 1, 1, 1, 2, 1]
  • 计算小于等于每个元素的个数，可以通过 C 数组得到，即为 C[i - 1] + C[i]，得到 C[0, 1, 2, 3, 5, 6]
  • 临时数组 R 存放排序后的元素，从后往前遍历数组 A，A[5] = 1，对应的小于等于 1 的元素 C[1] 是 1，则元素 1 应该排在 R 的第一个位置即 R[0] = 1，同时 C[1] 的值自减 1；A[4] = 4，小于等于 4 的元素 C[4] = 5，则 A[4] 元素放在 R[4] 的位置。同时 C[4] 自减 1；……循环到数组 A 被遍历完。
  • 最后得到的 R 数组就是数组 A 排序后的结果。

复杂度分析

时间复杂度

原数组大小是 N，辅助数组大小是 M，原数组存在多次遍历，但是去掉系数后时间复杂度是 $O(N + M)$

空间复杂度

申请了一个辅助排序的数组，空间复杂度是 $O(N + M)$

稳定性

如果在确定了元素位置后直接输出，是不稳定的，通过上述事例中的处理则是稳定的

适用范围

计数排序适用在范围不大的数据集中，而且要求数据是正整数，对于负数或者小数需要将其处理为整数。

基数排序

将元素先按照低位排序，在按照高位排序。元素位数不够的，按照最大元素的位数在不够的元素前面补 0。

实现

  • 确定最大元素及其位数
  • 申请一个基数数组 C[] 用于统计每一位元素出现的次数
  • 计算元素排序后的位置，这与计数排序中类似，计算小于等于 C[i] 的个数
  • 申请一个临时数组 R[] 存储排序后的元素

复杂度分析

时间复杂度

如果最大的元素只有一位，则时间复杂度是 $O(n)$，最大元素的位数为 k，则基数排序的时间复杂度是 $O(k*n)$

空间复杂度

空间复杂度是 $O(n + k)$

稳定性

与计数排序类似，实现过程中的处理可以保证稳定性