归并排序算法

发表于 | 分类于

归并排序

思路和代码实现如下：

不断对半拆分序列，直到序列只有一个数（即为有序），再自下而上合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <vector>
#include <iostream>
using namespace std;

template <typename T> void Merge(vector<T>& elem, int lo, int mid, int hi)
{
    // cout << "lo: " << lo << " mid: " << mid << " hi: " << hi << endl;
    if (mid - lo < 1 || hi - mid < 1) {
        return;
    }
    int lb = mid - lo;
    T* B = new T[lb];
    for (int i = 0, j = lo; i < lb; B[i++] = elem[j++]);
    for (int i = lo, j = 0, k = mid; (j < lb) || (k < hi);) {
        if ((j < lb) && ((k >= hi) || (B[j] <= elem[k]))) elem[i++] = B[j++];
        if ((k < hi) && ((j >= lb) || (elem[k] < B[j]))) elem[i++] = elem[k++];
    }
    delete [] B;
}

template <typename T> void MergeSort(vector<T>& elem, int lo, int hi)
{
    if (hi - lo < 2) return;
    int mid = lo + (hi - lo) / 2;
    MergeSort(elem, lo, mid);
    MergeSort(elem, mid, hi);
    Merge(elem, lo, mid, hi);
}

int main()
{
    vector<int> elem = {3, 8, 5, 99, 100, 77, 88, 6, 8, 9, 9, 9};
    MergeSort(elem, 0, elem.size());
    for (auto item : elem) {
        cout << item << " ";
    }
}

运行结果：

1
3 5 6 8 8 9 9 9 77 88 99 100

总结：归并排序思想很巧妙（巧妙在拆分到只有一个数即为有序序列，自下而上合并两个有序序列）

​ 时间复杂度：O(nlogn)