首页 > 算法 > 算法系列之四 归并排序

算法系列之四 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

一、两路归并递归算法思路
数组a[first...last] mid = (first + last) / 2;
可以把数组分成两组a[first...mid]以及a[mid+1...last],然后让这两组都是有序的,合并这两组从而让a[first...last]有序
怎么让a[first...mid]以及a[mid+1...last]有序呢,可以把a[first...mid]跟a[mid+1...last]分别再分成两组,依次类推。
直到当分出来的小组只有一个元素时,可以认为这个小组已经有序,然后再合并相邻的两个小组。
这样通过先递归的分解数列,再合并数列就完成了归并排序。

归并排序

//将有两个有序序列a[first...mid]和a[mid+1...last]合并。借助一个跟a大小一样的temp数组
void Merge(int a[], int first, int mid, int last, int temp[]) 
{
     int i = first, j = mid+1;
     int k = 0;
     while (i <= mid && j <= last)
     {
          if (a[i] <= a[j])
          {
               temp[k++] = a[i++];
          } else {
               temp[k++] = a[j++];
          }
     }
     while (i <= mid ) 
     {
          temp[k++] = a[i++];
     }
     while (j <= last)
     {
          temp[k++] = a[j++];
     }
     for(int v = 0; v < k; v++)
     {
          a[first + v] = temp [v];
     }
}

//归并排序
void MergeSort(int a[], int first, int last, int temp[])
{
     if (first < last) //递归的终结条件:子区间长度为1(一个记录自然有序
     {
          int mid = (first + last)/2;
          MergeSort(a, first, mid, temp); //让左边a[first...mid]有序
          MergeSort(a, mid+1, last, temp); //让右边[mid+1...last]有序
          Merge(a, first, mid, last, temp); //再将两个有序序列合并
     }
}

二、.两路归并排序非递归实现
1.把 n 个记录看成 n 个长度为 l 的有序子序列;
2.进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子序列;
3.重复第2步直到所有记录归并成一个长度为 n 的有序子序列为止。

void MergeSort2(int a[], int n, int temp[])
{
     int first, mid, last;
     int i = 0;
     //步长
     for (int step = 1; step < n; step *= 2)
     {
          for (i = 0; i < n; i += 2 * step)
          {
               first = i;
               mid = i + step - 1;
               last = i + 2 * step - 1;
               if (mid >= n) {
                    break;
               }
               if (last >= n) {
                    last = n-1;
               }
               Merge(a, first, mid, last, temp);
          }
     }
}

时间复杂度:
设数组长度为N,将数组二分法分成N个小组,需要logN步,每一步都是一个合并有序序列的过程,时间复杂度为N,故一共为N * logN
空间复杂度:
需要另外一个辅助数组,空间复杂度为N
稳定性:
稳定的,因为在将两个有序的序列合并成一个大的有序序列时,在元素相等的情况下,可以优先选择左边有序序列的元素

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.