情景回顾

上节回顾：如何用C语言实现希尔排序——一种比插入排序更快的排序算法

本节重点

本节重点：归并排序的自上而下递归法——如何用C语言实现一种能让你的电脑爆炸的排序算法，你敢试吗？

关注不迷路

微信公众号：工控小新

学习工控知识就来工控小新，为你提供工控笔记知识：EPLAN电气绘图 | TIA博图基础 | CAD | C语言教学 | 单片机基础 | 三菱PLC ... 每日持续更新中

归并排序是一种基于归并操作的排序算法，它可以将一个无序的序列分成若干个有序的子序列，然后再将这些子序列合并成一个完全有序的序列。归并排序的时间复杂度是O(nlogn)，空间复杂度是O(n)，它是一种稳定的排序算法，也就是说，它不会改变相同元素的相对顺序。

归并排序有两种实现方法，一种是自上而下的递归方法，另一种是自下而上的迭代方法。在这篇文章中，我们将介绍如何用C语言实现这两种方法，并给出相应的代码示例。

自上而下的递归方法

自上而下的递归方法是一种分治法的典型应用，它的基本思想是：

• 如果序列只有一个元素，那么它已经是有序的，无需排序；
• 如果序列有多个元素，那么将它分成两个（或更多）的子序列，分别对子序列进行归并排序；
• 将排好序的子序列合并成一个有序的序列。
• 
  

为了实现这个方法，我们需要定义一个辅助函数，用来将两个有序的子序列合并成一个有序的序列。这个函数的参数是：

• 一个待排序的序列（数组）arr；
• 一个临时的存储空间（数组）temp，用来存放合并后的序列，它的大小应该和arr一样；
• 两个子序列的起始索引left和right，以及两个子序列的结束索引mid和end。

这个函数的步骤是：

• 1、定义两个指针i和j，分别指向左右子序列的第一个元素；
• 2、定义一个指针k，指向临时空间的第一个位置；
• 3、比较i和j所指向的元素，将较小的元素复制到临时空间，并移动相应的指针；
• 4、重复上一步，直到某一子序列的所有元素都被复制到临时空间；
• 5、将另一子序列剩余的元素直接复制到临时空间的后面；
• 6、将临时空间的内容复制回原数组的相应位置。

这个函数的C语言代码如下：

// 合并两个有序的子序列
void merge(int arr[], int temp[], int left, int mid, int right)
{
int i = left; // 左子序列的起始索引
int j = mid + 1; // 右子序列的起始索引
int k = left; // 临时空间的起始索引
while(i <= mid && j <= right)
{
// 当两个子序列都有元素时
if(arr[i] <= arr[j])
{
// 如果左子序列的元素小于等于右子序列的元素
temp[k++] = arr[i++]; 
// 将左子序列的元素复制到临时空间，并移动指针
}
else
{
// 如果右子序列的元素小于左子序列的元素
temp[k++] = arr[j++]; 
// 将右子序列的元素复制到临时空间，并移动指针
}
}
while(i <= mid)
{
// 当左子序列还有剩余元素时
temp[k++] = arr[i++]; 
// 将左子序列的剩余元素复制到临时空间
}
while(j <= right)
{
// 当右子序列还有剩余元素时
temp[k++] = arr[j++]; 
// 将右子序列的剩余元素复制到临时空间
}
for(i = left; i <= right; i++)
{
// 将临时空间的内容复制回原数组
arr[i] = temp[i];
}
}

有了这个辅助函数，我们就可以定义一个递归函数，用来对一个序列进行归并排序。这个函数的参数是：

• 一个待排序的序列（数组）arr；
• 一个临时的存储空间（数组）temp，用来存放合并后的序列，它的大小应该和arr一样；
• 一个序列的起始索引left，和一个序列的结束索引right。

这个函数的步骤是：

• 如果left等于right，那么说明序列只有一个元素，无需排序，直接返回；
• 
  
• 如果left小于right，那么说明序列有多个元素，需要排序，继续执行以下步骤：
• 计算序列的中间索引mid，将序列分成两个子序列；
• 对左子序列进行归并排序，调用自身函数；
• 对右子序列进行归并排序，调用自身函数；
• 将排好序的左右子序列合并，调用辅助函数。

这个函数的C语言代码如下：

// 对一个序列进行归并排序
void merge_sort(int arr[], int temp[], int left, int right)
{
if(left == right)
{
// 如果序列只有一个元素，无需排序，直接返回
return;
}
if(left < right)
{
// 如果序列有多个元素，需要排序
int mid = (left + right) / 2;
// 计算序列的中间索引，将序列分成两个子序列
merge_sort(arr, temp, left, mid);
// 对左子序列进行归并排序，递归调用
merge_sort(arr, temp, mid + 1, right);
// 对右子序列进行归并排序，递归调用
merge(arr, temp, left, mid, right);
// 将排好序的左右子序列合并，调用辅助函数
}
}

这样，我们就完成了自上而下的递归方法的实现。

#挑战30天在头条写日记#