【数据结构】八大排序之归并排序算法

//归并递归子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if ( begin >= end )
    return;
 
  int mid = (begin + end) / 2;
  
  //先递归后访问进行操作,类似于树的后序遍历
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid+1, end, tmp);
 
  //递归到叶子数组后,开始归并
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = begin;
 
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])//循环将小值尾插进新数组
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
 
    //防止合并时有数组没拷贝完
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
 
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
 
  //拷贝tmp回原数组
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
 
}
 
//归并排序
void MergeSort(int* a, int n)//不写区间,因为该函数不递归自己,否则每次都要malloc
{
  //开数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
 
  _MergeSort(a, 0, n - 1, tmp);//归并递归子函数
 
  free(tmp);
}

//归并排序非递归
void MergeSortNonR(int* a, int n)
{
  //开数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
 
  int gap = 1;
 
  while (gap < n)
  {
    for (int i = 0; i < n; i =i+ 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
      //修正数组非2的次方倍数时的越界现象
      if (end1 >= n)
      {
        end1 = n - 1;
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      int j = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
    }
    memcpy(a, tmp, sizeof(int) * n);
    gap *= 2;
  }
 
  free(tmp);
}