归并排序的理解和实现

原理

1. 将整个序列看成是 n 个长度为1的有序子序列
2. 然后两两归并，得到 n/2 个长度为2的有序子序列
3. 继续按照该策略归并，直到得到 1 个长度为n的有序子序列

上述过程即一次反向递归，也是归并排序的基本思想

可视化归并排序

代码实现

C++代码实现

迭代版本

迭代版本的理解需要一定的时间

// 迭代法
void merge_sort_iteration(vector<int> &v){
    int n = v.size();
    vector<int> *seq = &v;
    vector<int> result(n,0);
    vector<int> *res = &result;     //通过交换指针完成迭代
    for(int step = 1; step < n;step*=2){    //元素间距(递归层次)
        for(int beg = 0;beg < n;beg += 2*step){ //子序列区间
            int left = beg;
            int mid = min(beg + step,n); //考虑最后的子区间长度不够的情况
            int right = min(beg+ 2*step,n);
            int k = left;
            int beg_1 = left,end_1 = mid;
            int beg_2 = mid,end_2 = right;
            while(beg_1 < end_1 && beg_2 < end_2){  //择小存入res
                (*res)[k++] = (*seq)[beg_1] < (*seq)[beg_2] ? (*seq)[beg_1++] : (*seq)[beg_2++];
            }
            while(beg_1 < end_1){
                (*res)[k++] = (*seq)[beg_1++];
            }
            while (beg_2 < end_2){
                (*res)[k++] = (*seq)[beg_2++];
            }
        }
        // 交换指针变量（迭代）
        vector<int> *T = seq;
        seq = res;
        res = T;
    }
    if (seq != &v) {
        for (int i = 0; i < n; i++)
            res[i] = seq[i];
        res = seq;
    }
}

递归版本

#include <iostream>
#include <vector>
using namespace std;
// 递归法
vector<int> merge_recursion(vector<int> left,vector<int> right){
    vector<int> res;
    int beg_1 = 0,beg_2 = 0;
    while(beg_1 < left.size() && beg_2 < right.size()){
        res.push_back(left[beg_1] < right[beg_2] ? left[beg_1++] : right[beg_2++]);
    }
    while(beg_1 < left.size()){
        res.push_back(left[beg_1++]);
    }
    while(beg_2 < right.size()){
        res.push_back(right[beg_2++]);
    }
    return res;
}
vector<int> merge_sort_recursion(vector<int> v){
    if(v.size() < 2) return v;
    else{
        int mid = v.size()/2;
        vector<int> left(v.begin(),v.begin()+mid);
        vector<int> right(v.begin()+mid,v.end());
        return merge_recursion(merge_sort_recursion(left),merge_sort_recursion(right));
    }
}
int main()
{
    vector<int> v;
    v.push_back(9);
    v.push_back(-1);
    v.push_back(7);
    v.push_back(5); 
    //merge_sort_iteration(v);
    v = merge_sort_recursion(v);
    for(int i = 0;i < 4;i++) cout << v[i] << " ";
    cout << endl;
    return 0;
}

Python代码实现

def merge_method(left,right):
    result = [] # 临时列表，保存排序后的序列
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while(left):
        result.append(left.pop(0))
    while(right):
        result.append(right.pop(0))
    return result

def merge_sort(seq):
    if(len(seq) < 2):
        return seq
    else:
        mid = len(seq)//2
        left,right = seq[0:mid],seq[mid:]
        return merge_method(merge_sort(left),merge_sort(right))

# 排序测试
if __name__ == '__main__':
    seq = [3,-4,22,-8,47,15,36,26,27,50]
    seq = merge_sort(seq)
    print(seq)