排序算法之歸并排序

歸并排序原理即将兩個有序的數組合并成一個，歸并排序有兩種方法：遞歸和循環。

/*遞歸方法*/      

void Merge(int TR1[], int TR2[], int low, int mid, int high)
{//将TR2歸并入TR1中
  int pos1 = low;
  int pos2 = mid + 1;
  for (int i = low; i <= high; ++i)
  {
    if (pos1 <= mid && pos2 <= high)
    {   
      if (TR2[pos1]>TR2[pos2])
      {
        TR1[i] = TR2[pos2];
        pos2++;
      }
      else
      {
        TR1[i] = TR2[pos1];
        pos1++;
      }
      }
    else if (pos1<=mid)
    {
      TR1[i] = TR2[pos1++];
    }
    else
    {
      TR1[i] = TR2[pos2++];
    }   
  }
}
void Msort(int SR[],int TR1[], int low, int high)
{
  int TR2[MAXSIZE + 1];
  if (low < high)
  {//先所有存放到TR2中，再由TR2歸并到TR1
    int mid = (low + high) / 2;
    Msort(SR,TR2,low, mid);
    Msort(SR,TR2,mid + 1, high);
    Merge(TR1, TR2, low, mid, high);
  }
  else
  {
    TR1[low] = SR[low];
  }
}
void MergeSort1(SqList* list)
{
  Msort(list->data,list->data,0,list->length-1);
}      

/*循環方法*/
void MergePass(int TR[], int SR[], int k, int length)
{
  int i = 0;
  while (i <= length-2*k+1)
  {//兩兩合并
    Merge(TR, SR, i, i + k-1, i + 2 * k - 1);
    i = i + 2 * k;
  }

  if (i <= length - k + 1)
  {//說明後面還剩兩個子數組，一個是完整的k個，還有一個小于k
    Merge(TR, SR, i, i + k - 1, length);
  }
  else
  {//最後僅僅剩一個子數組，
    for (int j = i; j <= length; j++)
    {
      TR[j] = SR[j];
    }
  }
}
void MergeSort2(SqList* list)
{/*從最小的序列開始歸并，直至完畢歸并*/
  int* TR = new int[list->length];
  int k = 1;
  while (k < list->length)
  {//兩次轉存。先從data轉存到TR,再從TR轉存到data; 
    MergePass(TR, list->data, k, list->length - 1);
    k = k * 2;
    MergePass(list->data, TR, k, list->length - 1);
    k = k * 2;
  }
}