数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

简介: 数据结构排序——详细讲解归并排序(c语言实现递归及非递归)

上次是快排和冒泡

今天为大家带来归并排序


1.基本思想


归并排序是一种分治算法,它将序列分成两个子序列,分别对子序列进行排序,然后将排序好的子序列合并起来。这个过程可以递归地进行,直到序列长度小于等于1时停止递归。


在合并子序列的过程中,需要比较两个子序列的元素,并按顺序将它们合并成一个有序序列


注意:归并排序的关键在于合并两个有序的子序列,这一步需要额外的空间来存储中间结果。在实际的实现中,可以使用递归或非递归的方式来完成归并排序


2.递归实现


递归归并排序:

  1. 如果序列长度小于等于1,无需排序,直接返回
  2. 将序列分成两个子序列,分别进行递归归并排序
  3. 合并两个已排序的子序列


void _MergeSort(int* a, int* tmp, int left, int right)//是下标,不是值
{
  if (left >= right)//只有一个元素或不存在这样的区间递归停止
  {
    return;
  }
  int mid = (left + right) / 2;//分成两部分,分别有序后再进行归并
  // [begin, mid][mid+1, end]
  _MergeSort(a, tmp, left, mid);
  _MergeSort(a, tmp, mid+1,right );//这两部分都有序啦
  //开始归并:归并到到tmp数组的相同位置,再拷贝回去
  int left1 = left; int right1 = mid;//第一个数组的两端
  int left2 = mid+1; int right2 = right;//第二个数组的两端
  int index = left;//两个数组是从left开始的,left给index就是到相同区间上
  while (left1 <= right1 && left2 <= right2)//两个比,小的放进去
  {
    if (a[left1] < a[left2])
    {
      tmp[index] = a[left1];
      index++;
      left1++;
    }
    else
    {
      tmp[index] = a[left2];
      index++;
      left2++;
    }
  }//有一个排完了,剩下的一个就直接放
  while (left1 <= right1)
  {
    tmp[index] = a[left1];
    index++;
    left1++;
  }
  while (left2 <= right2)
  {
    tmp[index] = a[left2];
    index++;
    left2++;
  }//到此,tmp内已经归并成功,接下来复制回a中
  memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{
  //创建一个临时数组
  int tmp = (int*)malloc(sizeof(int) * n);
  assert(tmp);
  _MergeSort(a, tmp, 0, n - 1);//子函数,在这里递归不好,有动态开辟
  free(tmp);
}
int main()
{
  int a[] = { 10,6,7,1,3,9,4,2 };
  //MergeSortNonR(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));//用来打印数组的
  MergeSort(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));
  return 0;
}


3.非递归实现


非递归实现归并排序是一种迭代式的排序算法,它避免了递归调用带来的额外开销,通常使用循环和迭代来实现归并排序的过程:


确定归并区间的思路:对于给定的数组,首先将相邻的元素两两归并(gap=1),然后将归并的区间长度不断扩大,依次归并相邻的区间、长度为 2 的区间、长度为 4 的区间,直到整个数组都归并完成(gap=2)。*

归并的逻辑:在每次归并的过程中,根据当前的区间长度,确定待归并的两个区间的边界。然后比较这两个区间的元素,并将较小的元素依次放入临时数组中。当某一个区间的元素已经全部放入临时数组后,将另一个区间剩余的元素直接放入临时数组中。

复制回原数组:在每次归并完成后,将临时数组中归并好的结果复制回原数组中,以便进行下一轮的归并操作。

不断扩大归并区间:通过不断扩大归并的区间长度,最终完成整个序列的排序

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  assert(tmp);
  int gap = 1;//第一次1为长度
  while (gap < n)
  {
    for (int i = 0; i < n ; i += 2*gap)//每次两个区间的左起点都是i ,每次跳过两个gap
    {
      //一个区间里有gap个元素
      int left1 = i; int right1 = i + gap - 1;//第一个区间
      int left2 = i+gap; int right2 = i + 2*gap - 1;//第二个
      if (left2 > n)//没有与之相归并的第二个数组
      {
        break;//直接出去,进行下一层
      }
      if (right2 > n)
      {
        right2 = n - 1;
      }
      //开始归并
      int index = i;
      while (left1 <= right1 && left2 <= right2)//两个比,小的放进去
      {
        if (a[left1] < a[left2])
        {
          tmp[index] = a[left1];
          index++;
          left1++;
        }
        else
        {
          tmp[index] = a[left2];
          index++;
          left2++;
        }
      }//有一个排完了,剩下的一个就直接放
      while (left1 <= right1)
      {
        tmp[index] = a[left1];
        index++;
        left1++;
      }
      while (left2 <= right2)
      {
        tmp[index] = a[left2];
        index++;
        left2++;
      }//到此,tmp内已经归并成功,接下来复制回a中
      memcpy(a + i, tmp + i, sizeof(int) * (right2 - i + 1));
    }
    gap *= 2;
  }
}

目录
相关文章
|
25天前
|
存储 编译器 C语言
【数据结构】C语言实现链队列(附完整运行代码)
【数据结构】C语言实现链队列(附完整运行代码)
35 0
|
25天前
|
存储 算法 程序员
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
38 0
数据结构|排序总结(1)|直接插入排序
数据结构|排序总结(1)|直接插入排序
|
21天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
|
21天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
|
21天前
|
C语言 索引
【C语言】C语言⻘蛙跳台阶问题--递归问题
【C语言】C语言⻘蛙跳台阶问题--递归问题
|
25天前
|
存储 搜索推荐 算法
【数据结构】八大排序之计数排序算法
【数据结构】八大排序之计数排序算法
11 4
|
25天前
|
搜索推荐 算法
【数据结构】八大排序之归并排序算法
【数据结构】八大排序之归并排序算法
20 5
|
25天前
|
搜索推荐 算法 编译器
【数据结构】八大排序之快速排序算法
【数据结构】八大排序之快速排序算法
35 4
|
26天前
|
搜索推荐 算法 编译器
【C语言】qsort()函数详解:能给万物排序的神奇函数
【C语言】qsort()函数详解:能给万物排序的神奇函数
41 0