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;
}
