上一篇数据结构与算法 --- 排序算法(一)中,学习了冒泡排序,插入排序,选择排序这三种时间复杂度为
的算法。实时上
时间复杂度是非常高的,所以一般只适合小规模数据排序,那接下来,就在看一看时间复杂度为
的算法:归并排序和快速排序。
归并排序和快速排序的核心思想就是分治算法思想,所以先介绍一下分治算法思想:
「分治算法思想简单来说就是将一个复杂的问题分解成几个较简单的子问题,再递归地解决这些子问题」。通常遵循以下三个步骤:
归并排序(Merge Sort)是一种基于分治思想的排序算法。它的基本思路是将待排序的数组分成两个子序列,然后对每个子序列进行递归排序,最后将排好序的两个子序列合并成一个有序序列。
来看一下归并排序的执行过程如下图:
接下来考虑如何使用C#代码实现一个归并排序算法?
一般归并排序就是通过递归实现的,那么在数据结构与算法 --- 递归(一)中总结了递归代码的编写技巧:写递推公式,寻找终止条件,最后将递推公式翻译为代码。
那么看一下归并排序的递归代码的递推公式为:
其终止条件为:
。
公式中
表示对下标从
到
的数组数据进行归并排序,然后将这个问题拆分成了两个子问题:
和
,其中下标
表示
到
的中间位置,也就是
,当这两个子数组排好序之后,再将这两个有序子数组合并(
),就完成了该数组的排序。
这里还需要着重讲解一下两个有序子数组的合并,实际上一般在这里合并方法使用的是双指针法,双指针法是合并两个有序数组最高效的算法,其时间复杂度为
,其中
和
分别是两个数组的长度。具体实现步骤如下:
综上,用C#代码实现一个归并算法如下:
public static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
//将待排序的数组分成两个子序列进行递归排序
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
//合并
Merge(arr, left, mid, right);
}
}
public static void Merge(int[] arr, int left, int mid, int right)
{
//双指针法合并数据到temp数组
int i = left, j = mid + 1, k = 0;
int[] temp = new int[right - left + 1];
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[k] = arr[i];
i++;
}
else
{
temp[k] = arr[j];
j++;
}
k++;
}
//当一边遍历完成后,将另一边剩余元素直接放入temp。
while (i <= mid)
{
temp[k] = arr[i];
i++;
k++;
}
while (j <= right)
{
temp[k] = arr[j];
j++;
k++;
}
for (int p = 0; p < k; p++)
{
arr[left + p] = temp[p];
}
}
「稳定性:」
归并排序是否稳定关键要看 Merge()
方法这部分逻辑。
在合并过程中,如果前半部分(图解左侧)和后半部分(图解右侧)之间有相同元素,先把前半部分中相同的值放入临时数组temp,再把后半部分中的相同的值放入临时数组temp,那么就能保证值相同的元素在合并前后的先后顺序不变,因此,归并排序是稳定排序算法。
「时间复杂度:」
归并排序的时间复杂度可以通过递归树和递推式来分析,具体分为以下几个步骤:
现在我们来分析归并排序的时间复杂度:
,其中n是待排序数组的长度。
,所以合并的时间复杂度是
。而在每一层的递归中,总共有
个元素需要进行合并操作,所以合并的时间复杂度也是
。
次递归操作。
综上所述,归并排序的时间复杂度可以表示为:
所以,归并排序的时间复杂度是O(nlogn)。无论输入数组的初始状态如何,归并排序的时间复杂度都保持不变。
「内存消耗:」很明显,归并排序使用了额外的内存空间,所以它不是原地排序算法。
我们不能像分析时间复杂度那样分析空间复杂度,因为空间复杂度是一个峰值,而时间复杂度是一个累加值,递归代码的空间消耗并不能像时间消耗那样累加,空间复杂度表示在程序运行过程中的最大消耗,而不是累加的内存消耗。
尽管每次合并操作都需要申请额外的临时数组temp,但在函数完成之后,临时数组temp所占的内存就被释放了。
在任意时刻,只会有一个函数在执行,也就只会有一个临时数组temp在使用,占用的临时空间内存最大也不会超过 n 个数据的大小,对应的空间复杂度也就是
。
除此之外,在归并排序的过程中,递归调用栈的空间复杂度取决于递归深度。对于一个长度为n的数组进行归并排序,递归深度为
。每一层递归都需要保存一些临时变量,如左右指针、中间指针等,这些变量的空间复杂度为
。因此,递归调用栈的空间复杂度为
。
综上所述,归并排序的空间复杂度为
。可以省略低阶部分,那就是
。
❝参考 [1] 数据结构与算法之美 / 王争 著. --北京:人民邮电出版社,2021.6 ❞
本文分享自 Niuery Diary 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!