数据结构 - 归并排序

归并排序 - 算法思路

image.png

归并排序 - 动图演示

归并排序算法.gif

时间复杂度

• O(nlogn)

代码实现

• printVector: 打印数组，需自己实现；
• NOTE: vector没有分片初始化算法；

#include <iostream>
#include <vector>
#include "print.h"

using namespace std;

template <typename T>
vector<T> merge(vector<T> left, vector<T> right){
    vector<T> result;
    int i=0, j=0;

    while(i < left.size() && j < right.size()){
        if(left[i] < right[j]){
            result.push_back(left[i]);
            i ++;
        }else{
            result.push_back(right[j]);
            j ++;
        }
    }

    //剩余元素存入vector中
    while(i < left.size()){
        result.push_back(left[i]);
        i ++;
    }

    while(j < right.size()){
        result.push_back(right[j]);
        j ++;
    }
    return result;
}

/**
 * 归并排序
 * @tparam T
 * @param nums
 * @return
 */
template <typename T>
vector<T> mergeSort(vector<T> nums){

    if(nums.size() == 1)
        return nums;

    // 1. 每次二分数组
    int mid = nums.size()/2;
    vector<T> nums_left, nums_right;
    for(int i=0; i<nums.size(); i++){
        if(i < mid)
            nums_left.push_back(nums[i]);
        else
            nums_right.push_back(nums[i]);
    }

    // 2. 分别对左右两边进行排序
    vector<T> left = mergeSort(nums_left);
    vector<T> right = mergeSort(nums_right);
    
    // 3. 将排序好的数组left, right归并
    return merge(left, right);
}

int main(){

    vector<int> nums={1,4,5,3,2};

    printVector(nums);
    vector<int> nums_sorted = mergeSort(nums);
    printVector(nums_sorted);

    return 0;
}

参考资料

• 图解排序算法(四)之归并排序
• Python实现十大经典排序算法：https://www.jianshu.com/p/bbbab7fa77a2