归并排序算法以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;}

评论