【C++信息學(xué)奧賽培訓】數據排序之歸并排序(MergeSort)詳解以及實例解析

一、歸并排序算法介紹：

歸并排序（Merge sort）是建立在歸并操作上的一種(zhǒng)有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

作爲一種(zhǒng)典型的分而治之思想的算法應用，歸并排序的實現由兩(liǎng)種(zhǒng)方法：

1.自上而下的遞歸（所有遞歸的方法都(dōu)可以用叠代重寫，所以就(jiù)有了第 2 種(zhǒng)方法）；

2.自下而上的叠代；

和選擇排序一樣，歸并排序的性能(néng)不受輸入數據的影響，但表現比選擇排序好(hǎo)的多，因爲始終都(dōu)是 O(nlogn) 的時(shí)間複雜度。代價是需要額外的内存空間。

二、歸并排序算法步驟：

1.申請空間，使其大小爲兩(liǎng)個已經(jīng)排序序列之和，該空間用來存放合并後(hòu)的序列；

2.設定兩(liǎng)個指針，最初位置分别爲兩(liǎng)個已經(jīng)排序序列的起(qǐ)始位置；

3.比較兩(liǎng)個指針所指向(xiàng)的元素，選擇相對(duì)小的元素放入到合并空間，并移動指針到下一位置；

4.重複步驟 3 直到某一指針達到序列尾；

5.將(jiāng)另一序列剩下的所有元素直接複制到合并序列尾。

三、歸并排序算法可視化演示：

四、歸并排序算法實例解析（信息學(xué)奧賽一本通例題）