数据结构:归并排序(非递归)

1,542 阅读4分钟

前言

归并排序,是创建在归并操作上的一种有效的排序算法,效率为O(nlogn)​。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法的一个非常典型的应用,且各层分治递归可以同时进行。(引自维基百科)

原理

以上视频转自www.youtube.com/watch?v=JSc…

由于掘金中无法加载视频,可以直接点击YouTube(需vpn)链接,也可到我博客的原文链接中观看perkyrookie.github.io/PerkyRookie…

用一张图片简单来说就是这样

示例代码(非递归)

  #include <stdio.h>
  #include <stdlib.h>
  #define MAXSIZE 100 //用于要排序数组的最大值 typedef struct      //定义一个顺序表结构 
  {
      int r[MAXSIZE+1];   //用于存储要排序数组,r[0]用作哨兵或者临时变量 
      int length;         //用于存储顺序表的最大长度 
  }SqList;
  ​
  void Merge(int *S, int *T, int low, int m, int high);
  void MergePass(int *S, int *T, int s, int length);
  void MergeSort(SqList *L);
  ​
  int main()
  {
      int i;
      int array[] = {39,80,76,41,13,29,50,78,30,11,100,7,41,86};
      SqList L;
      L.length = sizeof(array)/sizeof(array[0]);  //获取数组长度 
   
      for(i=0;i<L.length;i++)
          L.r[i+1]=array[i];  //把数组存入顺序表结构 
  ​
      MergeSort(&L);
      
      for(i=0;i<L.length;i++)     //输出排序后的数组 
          printf("%d ",L.r[i+1]);
  ​
      return 0;
  }
  ​
  void MergeSort(SqList *L)
  {   
      //申请额外的空间,由于r[0]为哨兵,所以这里长度要+1
      int* TR = (int *)malloc((L->length+1)*sizeof(int));
      int k = 1;/*k用来表示每次k个元素归并*/
      
      while (k < L->length)
      {
          //k每次乘以2是遵循1->2->4->8->16...的二路归并元素个数的原则
          MergePass(L->r, TR, k, L->length);/*先借助辅助空间归并*/
          k *= 2;
          MergePass(TR, L->r, k, L->length);/*再从辅助空间将排过序的序列归并回原数组*/
          k *= 2;
      }
      free(TR);//释放内存
      TR=NULL;
  }
  //将S中相邻长度为s的子系列两两归并到T中
  //这段代码稍微难理解点,文章后面会分析下
  void MergePass(int *S, int *T, int s, int length)
  {
      int i = 1;  //r[0]用作哨兵或者临时变量
      int j;
      
      while (i <= length-2*s+1)   //length-i+1(未合并元素) >= 2s 
      {       
          Merge(S, T, i, i+s-1, i+2*s-1);
          i= i+2*s;   //自增的下一个元素的起始点
      }
      if (i< length-s+1)  //归并最后两个序列 
          Merge(S, T, i, i+s-1, length);
      else
          for (j = i; j <= length; j++)
              T[j] = S[j];
  }
  ​
  //归并排序最主要实现函数
  //将有序的S[low..m]和S[m+1..high]归并到有序的T[low..high]中
  void Merge(int *S, int *T, int low, int m, int high)
  {//j在[m+1,high]区间递增,k用于目标T的下标递增, l是辅助变量
      int j, k, l;
      
      for (k = low,j = m+1; low <= m && j <= high; k++)   //将S中的元素由小到大归并到T中 
      {
          if (S[low] < S[j])
              T[k] = S[low++];    //此处先执行T[k] = S[low],然后low++;
          else
              T[k] = S[j++];      //同理
      }
      
      //for循环过后,可能有j>high 或者 low>m,故分情况处理
      if (low <= m)
      {
          for (l = 0; l <= m-low; l++)
              T[k+l] = S[low+l];      //将剩余的S[low..m]复制到T中 
      }
      
      if (j <= high)
      {
          for (l = 0; l <= high-j; l++)
              T[k+l] = S[j+l];        //将剩余的S[j..high]复制到T中
      }
  }

这里对部分难以理解的代码做个详细分析:

  void MergePass(int *S, int *T, int s, int length)
  {
      int i = 1;  //r[0]用作哨兵或者临时变量
      int j;  
      while (i <= length-2*s+1)   //length-i+1(未合并元素) >= 2s 
      {       
          Merge(S, T, i, i+s-1, i+2*s-1);
          i= i+2*s;   //自增的下一个元素的起始点
      }
      if (i< length-s+1)  //归并最后两个序列 
          Merge(S, T, i, i+s-1, length);
      else
          for (j = i; j <= length; j++)
              T[j] = S[j];
  }

第5~9行:这里实现的是子序列的两两归并。

  • 判断条件i <= length-2*s+1可以看做length-i+1 >= 2s,表示未合并的元素小于2s时跳出循环,即不足以构成两个长度为s的子序列时跳出循环;

  • 未合并元素需要+1的原因可以用个例子解释:即第一次进入循环时,应该是有length个元素未合并,而i起始大小是1,所以这里要+1。

  • 第7行:传入元素-1是因为i+si+2s都是下一个序列的起始点,所以是一个序列的终点就是这两个值-1。

第10~14行:判断条件i< length-s+1一样可以看做length-i+1>s

  • 满足条件:未合并的元素长度大于s,表示还能构成一个长度为s的序列和一个小于s的序列,即最后两个序列,这时还要执行一次归并。

  • else:未合并的元素长度小于s,则只剩一个序列,这时无法归并,直接把元素加到T数组后端。

剩下的应该不难理解了吧。


转载请声明: 

文章作者:窗外蟋蟀 

原始链接:https://juejin.cn/post/6844903750352683016