聊聊時間複雜度為O(nlogn)的歸并排序（上）

歸并排序(Merge Sort)

概念

歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

歸并

歸并操作，也叫歸并算法，指的是将兩個順序序列合并成一個順序序列的方法。

歸并排序圖解

【思考】為什麼要把一個數組先分成一半，然後再進行歸并呢？

對于我們的例子，有8個元素，一共可以分成3級，到第3級的時候，每一部分隻剩下一個元素了

3？ log2(8) = 3 如果有n個元素，就一共有log2(n)級(向上取整)

這樣，我們每一層要處理的個數是一樣的，雖然我們把它分成了不同的部分，如果整個歸并過程，我們可以用O(n)的時間複雜度來解決的話，那我們就設計出了一個nlogn級别的算法

那我們怎樣設計出時間複雜度為O(n)的歸并過程呢？

下面請看圖解

到此，原理講完了，廢話不多說，怎麼用代碼實作？

實作歸并操作，我得設定三個索引 i，j，k，第一排為歸并數組，第二排為設定的輔助數組

直接上代碼

//歸并排序
template<typename T>
static void mergeSort(T arr[], int n)
{
    __mergeSort(arr, 0, n - 1);
}
//依次劃分的過程，直到每一部分隻剩一個元素位置
template<typename T>
static void __mergeSort(T arr[], int l, int r)
{
    if(l >= r) //表示每部分隻有一個元素，到此劃分完畢
    {
        return;
    }
    int middle = (l + r) / 2;
    __mergeSort(arr, l, middle);
    __mergeSort(arr, middle + 1, r);
    //實作歸并
   if(arr[middle] > arr[middle + 1])
    {
        __merge(arr, l, middle, r);
    }
}
//實作歸并
template<typename T>
static void __merge(T arr[], int l, int m, int r)
{
    //先建立一個等大的臨時空間
    T temp[r - l + 1];
    //将歸并數組[l, r]複制到臨時數組中
    for(int i = l; i <= r; i++)
    {
        temp[i - l] = arr[i];
    }
    //定義三個輔助索引
    int i = l, j = m + 1;
    for(int k = l; k <= r; k++)
    {
        //判斷i是否越界
        if(i > m)
        {
            arr[k] = temp[j - l];
            j++;
        }
        else if(j > r)
        {
            arr[k] = temp[i - l];
            i++;
        }
        else if(temp[i - l] < temp[j - l])
        {
            arr[k] = temp[i - l];
            i++;
        }
        else
        {
             arr[k] = temp[j - l];
            j++;
        }
    }
}
           

然後測試了插入排序和歸并排序的性能（用了一個有50000個元素的數組），測試如下

你是不是會覺得歸并排序比插入排序性能好太多了，接下來，讓我們生成一個擁有50000個元素幾乎有序的數組測試兩種排序算法的性能

此時，你是不是有很多問号？怎麼一個nlogn級别的比n^2的還要慢，不科學？

【解答】那是因為在數組幾乎有序時，插入排序的性能接近于O(n)，是以才可能比歸并排序優越那麼一丢丢

此時，歸并排序不服氣了，我要優化

【下面進入歸并排序的優化環節】

• 當mid索引處的值小于mid+1索引處的值時，就不用進行歸并排序，直接已經是排好序的了，是以我們在進行歸并排序時添加了一個if語句的判斷

  

//實作歸并
if(arr[middle] > arr[middle + 1])
{
	__merge(arr, l, middle, r);
}
           

• 我們還可以對遞歸退出條件進行優化

  當每一部分的元素小于某一個值時，每一部分幾乎有序，我們可以轉而采取插入排序

//這裡我們把那個值設為15，就是每個部分有15個元素時，就不向下劃分，直接采用插入排序系那個每部分排好序，然後直接向上歸并
 if(r - l <= 15)
 {
     InsertionSort3(arr, l, r);
     return ;
 }
 //插入排序
template<typename T>
void InsertionSort3(T arr[], int l, int r)
{
    for(int i = l+1; i <= r; i++)
    {
        T temp = arr[i];
        int j;
        for(j = i; j > 0; j--)
        {
            if(arr[j] > temp)
            {
                arr[j] = arr[j - 1];
            }
            else
            {
                break;
            }
        }
        arr[j] = temp;
    }
}
           

【這是我測試的擁有100000個元素的幾乎有序的數組，歸并排序笑了】

…………

今天就先寫到這裡，下一篇還會對歸并算法進行進一步優化哦~