算法之归并排序(mergesort)

情况一、 两个有序（升序）的数组归并为一个有序数组

时间复杂度O(N)

原理

通过指针法：先比较两数组的初始位置的数据大小，比较小的数据放入一个最终的数组中，并且此数组向后移位，较小数据的数组也向后移动。

#include <vector>
#include <iostream>
#include <iterator>
using namespace std;

class Solution{
public:
    const vector<int> mergesort(vector<int>& nums , vector<int>& vect){
        vector<int> ans;
        auto nums_it = nums.begin();
        auto vect_it = vect.begin();
        while(nums_it != nums.end() && vect_it != vect.end()){
            if(*nums_it > *vect_it){
                ans.push_back(*vect_it);
                vect_it++;
            }
            else {
                ans.push_back(*nums_it);
                nums_it++;
            }
        }
        if(nums_it == nums.end()){
            for(; vect_it != vect.end(); vect_it++){
                ans.push_back(*vect_it);
            }
        }
        else {
            for(; nums_it != nums.end(); nums_it++){
                ans.push_back(*nums_it);
            }
        }
        return ans;
    }
};

int main(){
    Solution sl;
    vector<int> nums{4,5,6,11,32,55,77,88};
    vector<int> vect{6,9,44,222,434,555};
    nums = sl.mergesort(nums,vect);
    for(auto i : nums)
        cout << i <<" ";
    cout << endl;
}

情况二、 将一个无序数组归并为一个有序数组

时间复杂度O(N)

原理

利用递归的方法，采用分治的思想进行排序，每一次划分一半，到最后调用两个有序数组的归并，先归并3 和 1，

#include <vector>
#include <iostream>
#include <iterator>
using namespace std;

class Solution{
public:
    void mergesort(vector<int>& nums , vector<int>& temp, int left , int mid , int right){
    //[left,mid) -- 一个有序数组
    //[mid , right]	-- 一个有序数组
        int index = 0;
        vector<int> comp1;
        vector<int> comp2;
        index = left;
        for(int i = left; i < mid; i++)
            comp1.push_back(nums[i]);
        for(int i = mid; i <= right; i++)
            comp2.push_back(nums[i]);
        auto comp1_it = comp1.begin();
        auto comp2_it = comp2.begin();
        while(comp1_it != comp1.end() && comp2_it != comp2.end()){
            if(*comp1_it > *comp2_it){
                temp[index++]= *comp2_it;
                comp2_it++;
            }
            else {
                temp[index++]= *comp1_it;
                comp1_it++;
            }
        }
        if(comp1_it == comp1.end()){
            for(; comp2_it != comp2.end(); comp2_it++){
                temp[index++]= *comp2_it;
            }
        }
        else {
            for(; comp1_it != comp1.end(); comp1_it++){
                temp[index++]= *comp1_it;
            }
        }
        // 将temp 拷到 nums 对应位置
        for(int i = left ; i <= right ; i++){
            nums[i] = temp[i];
        }
    }

    void Msort(vector<int>& nums , vector<int> temp , int left , int right){
        //递归结束条件
        if(left >= right)
            return;
        int mid = (left + right) >> 1;
        Msort(nums, temp, left,mid);		// 分治左半边数组
        Msort(nums, temp, mid+1, right);	// 分治右半边数组
        mergesort(nums,temp,left,mid+1,right);	// 归并左右两边数组
    }


};

int main(){
    Solution sl;
    vector<int> nums{5,2,6,88,32,14,65,77,3,1,4,7,8,99,90};
    vector<int> temp = nums;
    int left = 0;
    int right = nums.size() - 1 ;
    sl.Msort(nums,temp,left,right);
    for(auto i : nums)
        cout << i <<" ";
    cout << endl;
}