归并排序

算法思想

归并排序使用了分治的套路,先将待排序元素划分为个数均等的两部分,然后在对已经划分的两个部分在进行均等
划分,如此递归的划分下去,直到区间无法在划分时停止,然后合并这些子区间即可;合并时每次从两个子区间内选
出最大(降序排序)或者最小(升序排序)的元素放入辅助空间内,直到某个子区间为空,然后在将另一个子区间剩余
的元素全部追加到辅助空间内,然后在将辅助空间的元素覆盖到原来两个子区间即可

 
归并排序的主要代码是合并,例如:{1,13,24,26},{2,15,27,38}这两个已经有序的子区间进行合并,其过程如下:

从上图可以看出:此时i指向的元素1比j指向的元素2小,所以将1放入辅助空间:

从上图可以看出:此时i指向的元素13比j指向的元2大,所以将2放入辅助空间:

从上图可以看出:此时i指向的元素13比j指向的元15小,所以将13放入辅助空间:

从上图可以看出:此时i指向的元素24比j指向的元15大,所以将15放入辅助空间:

从上图可以看出:此时i指向的元素24比j指向的元27小,所以将24放入辅助空间:

从上图可以看出:此时i指向的元素26比j指向的元27小,所以将26放入辅助空间:

此时这一对区间的左侧区间已经复制到辅助空间中,在将右侧区间的剩余元素追加到辅助空间尾部:

至此来两个区间合并暂未完成！！！,还得把辅助空间中的元素覆盖到这对区间中,才算完成
 
例:对38,27,43,3,9,82,10进行升序排序
先对要排序的数组进行划分:

此时区间划分完成,开始从底向上进行合并:
因为在划分时,{38}没有对应的子区间,所以合并时不发生改变:

合并{27},{43}后,如下图:

合并{38},{27,43}后,如下图:

至此,第一次划分时的左侧区间已经有序,则对右侧进行合并:
合并{3},{9}后,如下图:

合并{82},{10}后,如下图:

合并{3,9},{82,10}后,如下图:

此时在进行最后一次合并则排序完成:

代码实现

//************************************************************************
// 函数名称: Merge
// 函数功能:  合并两个有序的分组
// 返回值:   void
// 参数:     int * pUnSortAry:存放两个有序的分组
// 参数:     int * pTempAry:用于合并两个分组的临时数组,与pUnSortAry指向的数组同大小
// 参数:     int nLeftPos:第一个有序数组的起始下标
// 参数:     int nMiddlePos:第一个有序数组的终止下标,也是第二个有序数组的起始下标
// 参数:     int nRightPos:第二个有序数组的终止下标
// 注意:     
//************************************************************************
void Merge(int * pUnSortAry, int * pTempAry, int nLeftPos, int nMiddlePos, int nRightPos)
{
  int nLeftIndex = nLeftPos;
  int nRightIndex = nMiddlePos;
  int nInsertIndex = 0;
  /*对从两个分组中选取的元素进行比较,将较大元素放到临时数组中*/
  while (nLeftIndex < nMiddlePos && nRightIndex < nRightPos)
  {
    if (pUnSortAry[nLeftIndex] < pUnSortAry[nRightIndex])
    {
      pTempAry[nInsertIndex] = pUnSortAry[nLeftIndex];
      nLeftIndex++;
    }
    else
    {
      pTempAry[nInsertIndex] = pUnSortAry[nRightIndex];
      nRightIndex++;
    }
    nInsertIndex++;
  }

  /*可能会有一个分组有剩余元素,则直接将这个分组中的剩余元素追加到临时数组的尾部*/
  while (nLeftIndex  < nMiddlePos)
  {
    pTempAry[nInsertIndex] = pUnSortAry[nLeftIndex];
    nInsertIndex++;
    nLeftIndex++;
  }

  while (nRightIndex  < nRightPos)
  {
    pTempAry[nInsertIndex] = pUnSortAry[nRightIndex];
    nInsertIndex++;
    nRightIndex++;
  }

  /*将临时数组中的元素复制到原待排序数组中*/
  for (nInsertIndex = nLeftPos; nInsertIndex < nRightPos; nInsertIndex++)
  {
    pUnSortAry[nInsertIndex] = pTempAry[nInsertIndex-nLeftPos];
  }
}

//************************************************************************
// 函数名称: MergeSortInternal
// 函数功能: 对一个待排序数组进行划分,并排序
// 返回值:   void
// 参数:     int * pUnSortAry:待排序数组
// 参数:     int * pTempAry:临时数组,与待排序数组等大小
// 参数:     int nStartIndex:待排序数组起始下标
// 参数:     int nEndIndex:待排序数组结束下标(指向数组最后一个元素的下一个位置)
// 注意:     
//************************************************************************
void MergeSortInternal(int * pUnSortAry, int * pTempAry, int nStartIndex, int nEndIndex)
{
  if (nStartIndex+1 < nEndIndex)
  {
    int nMiddleIndex = (nStartIndex + nEndIndex) / 2;
    MergeSortInternal(pUnSortAry, pTempAry, nStartIndex, nMiddleIndex);
    MergeSortInternal(pUnSortAry, pTempAry, nMiddleIndex, nEndIndex);
    Merge(pUnSortAry, pTempAry, nStartIndex, nMiddleIndex, nEndIndex);
  }
}


//************************************************************************
// 函数名称: MergeSort
// 函数功能: 实现归并排序
// 返回值:   bool:成功返回true,否则false
// 参数:     int * pUnSortAry:指向待排序数组
// 参数:     int nSize:数组大小
// 注意:     
//************************************************************************
bool MergeSort(int * pUnSortAry, int nSize)
{
  int * pTempAry = (int *)malloc(sizeof(int)*nSize);
  if (pTempAry == nullptr)
  {
    return false;
  }

  MergeSortInternal(pUnSortAry, pTempAry,0, nSize);
  free(pTempAry);
  return true;
}

测试代码如下:

void PrintData(int*pAry, int nSize)
{
  for (int jIndex = 0; jIndex < nSize; jIndex++)
  {
    printf("%d ", pAry[jIndex]);
  }
  printf("
");
}
int main(int argc, char*argv[])
{
  srand(time(NULL));

  int nArry[30] = { 0 };

  for (int jIndex = 0; jIndex < 10; jIndex++)
  {
    for (int iIndex = 0; iIndex < sizeof(nArry) / sizeof(nArry[0]); iIndex++)
    {
      nArry[iIndex] = rand() % 150;
    }
    printf("排序前:");
    PrintData(nArry, sizeof(nArry) / sizeof(nArry[0]));
    MergeSort(nArry, sizeof(nArry) / sizeof(nArry[0]));
    printf("排序后:");
    PrintData(nArry, sizeof(nArry) / sizeof(nArry[0]));
    printf("
");
  }
  
  return 0;
}

运行结果:

时空复杂度分析

归并排序要用到辅助空间,其大小等同于数组的大小,而归并排序是递归实现的,所以其运行时栈空间消耗为lgn
所以总的空间复杂度为S(n) = n+lgn = O(n);

归并排序的合并操作的时间复杂度为Θ(n),总的时间复杂度为:T(n)=2T(n/2)+Θ(n)=nlgn

稳定性

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换)
然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时
1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程
中,稳定性没有受到破坏,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在
结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。