归并排序算法

源代码如下所示

#include "malloc.h"

//升序排序，A[p]-A[q]，A[q + 1]-A[r]这两部分已经排序好
void Merge(unsigned int* A, unsigned int p, unsigned int q, unsigned int r)
{
  unsigned int n1, n2, i, j, k;
  unsigned int* L;
  unsigned int* R;

  //计算数组1和数组2的大小
  n1 = q - p + 1;
  n2 = r - q;

  //申请动态内存
  L = malloc((n1 + 1) * sizeof(unsigned int));
  R = malloc((n2 + 1) * sizeof(unsigned int));
  if ((NULL == L) || (NULL == R))
  {
    printf("Merge: fail to malloc\r\n");
    while (1) {}
  }

  //保存第一部分数据
  for (i = 0; i < n1; i++){L[i] = A[p + i];}

  //保存第二部分数据
  for (j = 0; j < n2; j++){R[j] = A[q + 1 + j];}

  //设置哨兵
  L[n1] = 0xFFFFFFFF;
  R[n2] = 0xFFFFFFFF;

  //排序
  i = 0; j = 0;
  for (k = p; k <= r; k++)
  {
    if (L[i] <= R[j])
    {
      A[k] = L[i];
      i++;
    }
    else
    {
      A[k] = R[j];
      j++;
    }
  }

  //释放动态内存
  free(L);
  free(R);
}

//归并排序
void MergeSort(unsigned int* A, unsigned int p, unsigned int r)
{
  unsigned int q;
  
  if (p < r)
  {
    q = (p + r) / 2;
    MergeSort(A, p, q);
    MergeSort(A, q + 1, r);
    Merge(A, p, q, r);
  }
}

测试代码如下所示

#include "stdio.h"
#include "malloc.h"
#include <time.h>

#define TEST_LEN 64

void main(void)
{
  unsigned int* a;
  unsigned int i, data;

  //设置随机数种子
  srand((unsigned)time(NULL));

  //申请动态内存
  a = malloc(TEST_LEN * sizeof(unsigned int));
  if (NULL == a)
  {
    printf("main: fail to malloc\r\n");
    while (1) {}
  }

  //填充数组里边的内容
  for (i = 0; i < TEST_LEN; i++)
  {
    do
    {
      data = rand() % 256;
    } while (0xFFFFFFFF == data);
    a[i] = data;
  }

  //排序
  MergeSort(a, 0, TEST_LEN - 1);

  //打印
  for (i = 0; i < TEST_LEN; i++)
  {
    printf("%d, ", a[i]);
  }

  //释放动态内存
  free(a);

  while (1) {}
}