排序算法（六）---- 歸并排序

對于歸并排序，與快速排序一樣，巧妙的應用了分治算法的核心思想，它将整個序列分成若幹組子序列，對這些子序列進行排序後，在一步一步進行合并有序子序列，進而使得整個序列達到有序。 但針對于歸并排序，有着兩種不同的排序方式，一是通過整個序列進行着手，将這個序列進行一步一步的劃分，自頂向下進行處理，主要步驟包括序列劃分，子序列排序，以及合并，而這一方法可以通過遞歸來實作；與之相對的就是另外一種方式，自底向上，從最小子序列着手，将其進行兩兩合并，一步一步得到整個有序序列，而這也是我們歸并排序的非遞歸實作方式

①自頂向下（遞歸） 方法如下：

void Merge(int arr[],int left,int right,int mid,int* tmp)
{
       int i=left;
       int j=mid+1;
       int idx=0;
       while(i<=mid&&j<=right)
       {
              if(arr[i]<arr[j])
                     tmp[idx++]=arr[i++];
              else
                     tmp[idx++]=arr[j++];
       }

       while(i<=mid)
       {
              tmp[idx++]=arr[i++];
       }
       while(j<=right)
       {
              tmp[idx++]=arr[j++];
       }

}

void MergeSort_Nor(int arr[],int left,int right,int* tmp)
{
       if(left<right)
       {
              int mid=(left&right)+((left^right)>>1);
              MergeSort_Nor(arr,left,mid,tmp);
              MergeSort_Nor(arr,mid+1,right,tmp);
              Merge(arr,left,right,mid,tmp);
              memcpy(arr+left,tmp,(right-left+1)*sizeof(arr[0]));
       }
}

void MergeSort(int arr[],int size)
{
       int* tmp=new int[size];
       int left=0;
       int right=size-1;
       MergeSort_Nor(arr,left,right,tmp);
       delete[] tmp;
}
           

②自底向上（非遞歸） 方法如下：

void Merge(int arr[],int left,int right,int mid,int* tmp)
{
       int i=left;
       int j=mid+1;
       int idx=0;
       while(i<=mid&&j<=right)
       {
              if(arr[i]<arr[j])
                     tmp[idx++]=arr[i++];
              else
                     tmp[idx++]=arr[j++];
       }

       while(i<=mid)
       {
              tmp[idx++]=arr[i++];
       }
       while(j<=right)
       {
              tmp[idx++]=arr[j++];
       }

}

void MergeSort(int arr[],int size)
{
       int* tmp=new int[size];
       int gap=1;
       while(gap<size)
       {
              for(int i=0;i<size;i+=2*gap)
              {
                     int left=i;
                     int right=i+2*gap-1;
                     int mid=i+gap-1;
                     if(right>=size)//注意越界
                           right=size-1;
                     if(mid>=size)//注意越界
                           mid=size-1;
                     Merge(arr,left,right,mid,tmp);
                     memcpy(arr+left,tmp,(right-left+1)*sizeof(arr[0]));
              }
              gap*=2;
       }

       delete[] tmp;
}
           

值得注意的是，歸并排序不管是非遞歸方法，還是遞歸方法，都需要輔助空間的參與，但是對于遞歸而言，一次遞歸就申請一次空間會降低效率，而且需要注意釋放空間，是以這裡在外部直接申請出一塊足夠的空間，然後将其指針作為參數進行傳遞，而在外部進行釋放，也是相當友善。

對于歸并排序的時間複雜度為O(NlogN),空間複雜度為O(N),而且歸并排序是穩定的

與前面所有的排序算法不一樣，歸并排序屬于外部排序，而對于外部排序而言，與内部排序最大的差別在于外部排序在進行排序時，并不需要得到所有資料，可以将大量的資料分成若幹組，分别對其進行排序，最後再綜合起來排序，适合與大量資料的排序