侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

归并排序

kaixindeken
2021-04-19 / 0 评论 / 0 点赞 / 58 阅读 / 1,030 字

实现原理

今天介绍比前面三个排序算法性能更好的排序算法,归并排序。

所谓归并排序,指的是如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

归并排序使用了分治思想,分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。说到这里,可能你就能联想起我们之前讲到的一个编程技巧 —— 递归,没错,归并排序就是通过递归来实现的。这个递归的公式是每次都将传入的待排序数组一分为二,直到不能分割,然后将排序后序列合并,最终返回排序后的数组。

原理图如下所示:

1.jpeg

由于涉及到递归,所以归并排序从理解上要比前面三个排序要困难一些,还是建议通过这个动态图帮助理解:https://visualgo.net/zh/sorting

示例代码

void merge(int a[], int low, int mid, int high) {
  // subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
  int N = high-low+1;
  int b[N]; // discuss: why do we need a temporary array b?
  int left = low, right = mid+1, bIdx = 0;
  while (left <= mid && right <= high) // the merging
    b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
  while (left <= mid) b[bIdx++] = a[left++]; // leftover, if any
  while (right <= high) b[bIdx++] = a[right++]; // leftover, if any
  for (int k = 0; k < N; k++) a[low+k] = b[k]; // copy back
}

性能分析

归并排序不涉及相等元素位置交换,是稳定的排序算法,时间复杂度是 O(nlogn),要优于冒泡排序和插入排序的 O(n2),但是归并排序需要额外的空间存放排序数据,不是原地排序,最多需要和待排序数组同样大小的空间,所以空间复杂度是 O(n)。

归并排序的时间复杂度计算过程:

归并的思路时将一个复杂的问题 a 递归拆解为子问题 b 和 c,再将子问题计算结果合并,最终得到问题的答案,这里我们将归并排序总的时间复杂度设为 T(n),则 T(n) = 2*T(n/2) + n,其中 T(n/2) 是递归拆解的第一步对应子问题的时间复杂度,n 则是合并函数的时间复杂度(一个循环遍历),依次类推,我们可以推导 T(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
        = ...
        = 2^k*T(n/2^k) + k*n

递归到最后,T(n/2k)≈T(1),也就是 n/2k = 1,计算归并排序的时间复杂度,就演变成了计算 k 的值,2k = n,所以 k=log2n,我们把 k 的值带入上述 T(n) 的推导公式,得到:

T(n) = n*T(1) + n*log2n = n(C + log2n)

注:上述公式中2是下标。

把常量和低阶忽略,所以 T(n) = nlogn。

0

评论区