挑战全网，自下而上的迭代法——飞速运行的归并排序方法

#来点儿干货#

情景回顾

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

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

本节重点

本节重点：自下而上的迭代法——一种让你的电脑飞速运行的归并排序方法，你不可不知！

关注不迷路

工控小新

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

在上一篇文章中，我们介绍了如何用C语言实现归并排序的自上而下的递归方法，它的基本思想是将序列不断地分成两半，直到每个子序列只有一个元素，然后再将这些子序列按照大小顺序合并起来。这种方法的优点是简单直观，但是缺点是需要使用递归，这会消耗额外的栈空间和函数调用开销，而且在某些情况下，可能会导致栈溢出的错误。

为了避免这些问题，我们可以使用另一种实现方法，即自下而上的迭代方法，它的基本思想是将序列看作是由若干个长度为1的有序子序列组成，然后将这些子序列两两合并，得到长度为2的有序子序列，再将这些子序列两两合并，得到长度为4的有序子序列，以此类推，直到得到一个完全有序的序列。这种方法的优点是不需要使用递归，只需要使用一个循环，而且可以更好地利用缓存，提高性能。

为了实现这个方法，我们仍然需要定义一个辅助函数，用来将两个有序的子序列合并成一个有序的序列。这个函数的参数和上一篇文章中的一样，只是我们不再需要传入子序列的中间索引mid，因为我们可以根据子序列的长度和起始索引计算出来。这个函数的代码也和上一篇文章中的一样，只是我们需要在循环中加入一个判断条件，防止指针越界。

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

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

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

一个待排序的序列（数组）arr；

一个临时的存储空间（数组）temp，用来存放合并后的序列，它的大小应该和arr一样。

这个函数的步骤是：

定义一个变量len，表示子序列的长度，初始为1；

定义一个循环，每次将len乘以2，直到len大于等于arr的长度；

在循环中，定义一个变量i，表示子序列的起始索引，初始为0；

定义一个内层循环，每次将i加上len的两倍，直到i大于等于arr的长度；

在内层循环中，将arr中从i开始的两个长度为len的子序列合并，调用辅助函数。

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

// 对一个序列进行归并排序
void merge_sort(int arr[], int temp[])
{
    int len = 1; // 子序列的长度，初始为1
    while(len < arr.length)
    {
    // 当子序列的长度小于数组的长度时
      int i = 0; // 子序列的起始索引，初始为0
       while(i < arr.length)
       {
      // 当子序列的起始索引小于数组的长度时
        merge(arr, temp, i, i + len, len);
      // 将arr中从i开始的两个长度为len的子序列合并，调用辅助函数
          i += 2 * len;
      // 将子序列的起始索引加上len的两倍，移动到下一对子序列
        }
      len *= 2;
      // 将子序列的长度乘以2，扩大合并的范围
    }
}

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

为了更好地理解这个方法的过程，我们可以用一个具体的例子来演示一下。假设我们要对以下的序列进行归并排序：

[8, 4, 5, 7, 1, 3, 6, 2]

#include<stdio.h>
#include<stdlib.h>
void merge(int arr[], int temp[], int left, int right, int len)
{
  int i = left; // 左子序列的起始索引
  int j = left + len; // 右子序列的起始索引
  int k = left; // 临时空间的起始索引
  while(i < left + len && j < right + len && j <8)
  {
    // 当两个子序列都有元素时，且没有越界时
    if(arr[i] <= arr[j])
    {
      // 如果左子序列的元素小于等于右子序列的元素
      temp[k++] = arr[i++]; 
      // 将左子序列的元素复制到临时空间，并移动指针
    }
    else
    {
      // 如果右子序列的元素小于左子序列的元素
      temp[k++] = arr[j++]; 
      // 将右子序列的元素复制到临时空间，并移动指针
    }
  }
  while(i < left + len && i <8)
  {
    // 当左子序列还有剩余元素时，且没有越界时
    temp[k++] = arr[i++]; 
    // 将左子序列的剩余元素复制到临时空间
  }
  while(j < right + len && j <8)
  {
    // 当右子序列还有剩余元素时，且没有越界时
    temp[k++] = arr[j++]; 
    // 将右子序列的剩余元素复制到临时空间
  }
  for(i = left; i < right + len && i <8; i++)
  {
    // 将临时空间的内容复制回原数组
    arr[i] = temp[i];
  }
}
void merge_sort(int arr[], int temp[])
{
    int len = 1; // 子序列的长度，初始为1
  while(len <8)
  {
    // 当子序列的长度小于数组的长度时
    int i = 0; // 子序列的起始索引，初始为0
    while(i <8)
    {
      // 当子序列的起始索引小于数组的长度时
      merge(arr, temp, i, i + len, len);
      // 将arr中从i开始的两个长度为len的子序列合并，调用辅助函数
      i += 2 * len; 
      // 将子序列的起始索引加上len的两倍，移动到下一对子序列
    }
    len *= 2; 
    // 将子序列的长度乘以2，扩大合并的范围
  }
}

int main()
{
  // 定义一个待排序的序列
  int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
  // 定义一个临时的存储空间，大小和序列一样
  int temp[8];
  // 调用归并排序函数，传入序列，临时空间，起始索引和结束索引
  merge_sort(arr,temp);
  // 打印排序后的序列
  for(int i = 0; i < 8; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
  return 0;
}

我们可以按照以下的步骤进行：

1、将序列看作是由8个长度为1的有序子序列组成，即：

[8], [4], [5], [7], [1], [3], [6], [2]

2、将相邻的两个子序列合并，得到4个长度为2的有序子序列，即：

[4, 8], [5, 7], [1, 3], [2, 6]

3、将相邻的两个子序列合并，得到2个长度为4的有序子序列，即：

[4, 5, 7, 8], [1, 2, 3, 6]

4、将相邻的两个子序列合并，得到1个长度为8的有序子序列，即：

[1, 2, 3, 4, 5, 6, 7, 8]

这样，我们就完成了归并排序，得到了一个完全有序的序列。

通过这篇文章，我们希望你能够了解归并排序的自下而上的迭代方法

原文链接：

挑战全网，详细的介绍自下而上的迭代法——一种让你的电脑飞速运行的归并排序方法，你不可不知！