编辑代码

#include <iostream>
#include <vector>
using namespace std;
void mergeSort(vector<int> &vec, int left, int right);
void merge(vector<int> &vec, int left, int mid, int right);
void printVec(vector<int> vec);
//test
int main(){
vector<int> test_vec = {11,9,3,20,56,32};
printVec(test_vec);
mergeSort(test_vec, 0, test_vec.size() - 1);
printVec(test_vec); 
system("pause");
return 0;
}
//归并排序，先分再合
void mergeSort(vector<int> &vec, int left, int right){
if (left >= right){
return;
}
//int mid = left + (right - left) / 2;
int mid = left + ((right - left) >> 1); 
mergeSort(vec, left, mid);
mergeSort(vec, mid + 1, right);
merge(vec, left, mid, right); //合并
}
//合并，双指针 + 临时数组
void merge(vector<int> &vec, int left, int mid, int right){
int n = right - left + 1;
vector<int> helper(n, 0); //临时数组
int i = 0;
int p1 = left; //第一个指针
int p2 = mid + 1; //第二个指针
//在两个指针都没有越过边界的情况下，将两个数组中较小的数放入临时数组，并将指针后移
while (p1 <= mid && p2 <= right){ 
helper[i++] = vec[p2] < vec[p1] ? vec[p2++] : vec[p1++];
}
//将未到达边界的数组的剩余元素拷贝到临时数组尾部
while (p1 <= mid){
helper[i++] = vec[p1++];
}
while (p2 <= right){
helper[i++] = vec[p2++];
}
//将临时数组的元素拷贝到原数组
for (int j = 0; j < n; j++){
vec[left + j] = helper[j];
}
}
//打印数组
void printVec(vector<int> vec){
for (auto c : vec){
cout << c << " ";
}
cout << endl;
}