MergeSort 归并排序

ClassicalCode: mergeSort.cpp
直接分析大佬简洁的源码。

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

void merge(vector<int>& nums, int lo, int mid, int hi){
    vector<int> B(nums.begin() + lo, nums.begin()  + mid);//注意此处对vector初始化，vector大小为mid-lo
    int i = 0, j = mid;//i为B内的指针位置
    int k = lo;  //k为nums内的指针位置
    while(i < B.size() && j < hi){      //区间左闭右开  j < hi
        if(B[i] < nums[j]) nums[k++] = B[i++];
        else nums[k++] = nums[j++];
    }
    while(i < B.size()) nums[k++] = B[i++];
    //else 后半部分还有,但是已经就地了,无需处理，省去了赋值的操作
    return;
}


void mergeSort(vector<int> &nums, int lo, int hi){
    if(hi < lo + 2) return;
    int mid = lo + ((hi - lo) >> 1);  //大佬的除法必须用位运算
    mergeSort(nums, lo, mid);
    mergeSort(nums, mid, hi);  //注意，这区间也是左闭右开
    merge(nums, lo, mid, hi);
}


int main(){
    vector<int> nums{16,4,10,14,7,9,3,2,8,1};
    mergeSort(nums, 0, nums.size());

    for(int i = 0; i < nums.size(); i++){
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}