2025年4月5日 星期六 乙巳(蛇)年 正月初六 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > C语言

我所理解的归并排序算法

时间:01-03来源:作者:点击数:62

归并排序算法以O(nlogn)最坏情形运行时间运行,而所使用的比较次数几乎是最优的。它可以用递归的形式实现,形式简洁易懂。但是需要注意的是当用递归形式时,如果数据较多,则开销很大,实用性很差,所以我们一般采用非递归的形式。我这里两种形式都给出。不管是递归还是非递归,归并排序算法中基本的操作是合并两个已经排序的数组。

递归形式:

  • template <class T>
  • void MSort(T a[], int left, int right)
  • {
  • if (left < right)
  • {
  • int center = (left + right) / 2;
  • MSort(a, left, center);
  • MSort(a, center+1, right);
  • Merge(a, left, center, right, right-left+1);
  • }
  • }
  • template <class T>
  • void MergeSort(T a[], int n)
  • {
  • MSort(a, 0, n-1);
  • }

///////////////////////////////////////////////////////////////////////

非递归形式:

算法介绍:先介绍三个变量beforeLen,afterLen和i的作用:
         int beforeLen; //合并前序列的长度
         int afterLen;//合并后序列的长度,合并后序列的长度是合并前的两倍
         int i = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始
         i,i+beforeLen-1,i+afterLen-1定义被合并的两个序列的边界。

算法的工作过程如下:

开始时,beforeLen被置为1,i被置为0。外部for循环的循环体每执行一次,都使beforeLen和afterLen加倍。内部的while循环执行序列的合并工作,他的循环体每执行一次,i都向前移动afterLen个位置。当n不是afterLen的倍数时,如果被合并序列的起始位置i,加上合并后序列的长度afterLen,超过输入数组的边界n,就结束内部循环;此时如果被合并序列的起始位置i,加上合并前序列的长度beforeLen,小于输入数组的边界n,还需要执行一次合并工作,把最后长度不足afterLen,但超过beforeLen的序列合并起来。这个工作由算法的语句Merge(a, i, i+beforeLen-1, n-1, n);完成。

  • template <class T>
  • void MergeSort(T a[], int n)
  • {
  • int beforeLen; //合并前序列的长度
  • int afterLen = 1;//合并后序列的长度
  • for (beforeLen=1; afterLen<n; beforeLen=afterLen)
  • {
  • int i = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始
  • afterLen = 2 * beforeLen; //合并后序列的长度是合并前的两倍
  • while (i+afterLen < n)
  • {
  • Merge(a, i, i+beforeLen-1, i+afterLen-1, afterLen);
  • i += afterLen;
  • }
  • if (i+beforeLen < n)
  • Merge(a, i, i+beforeLen-1, n-1, n);
  • }
  • }

///////////////////////////////////////////////////////////

上面两种算法都要用到下面的合并函数。

  • /*函数介绍:合并两个有序的子数组
  • 输入:数组a[],下标left,center,right,元素个数n,a[left]~a[center]及a[center+1]~a[right]已经按非递减顺序排序。
  • 输出:按非递减顺序排序的子数组a[left]~a[right]。
  • */
  • template <class T>
  • void Merge(T a[], int left, int center, int right, int n)
  • {
  • T *t = new T[n];//存放被排序的元素
  • int i = left;
  • int j = center + 1;
  • int k = 0;
  • while (i<=center && j<=right)
  • {
  • if (a[i] <= a[j])
  • t[k++] = a[i++];
  • else
  • t[k++] = a[j++];
  • }
  • if (i == center+1)
  • {
  • while (j <= right)
  • t[k++] = a[j++];
  • }
  • else
  • {
  • while (i <= center)
  • t[k++] = a[i++];
  • }
  • //把t[]的元素复制回a[]
  • for (i=left,k=0; i<=right; i++,k++)
  • a[i] = t[k];
  • delete []t;
  • }

 

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门