37 lines
801 B
C++
37 lines
801 B
C++
#include <vector>
|
|
#include <queue>
|
|
#include <iostream>
|
|
#include <tuple>
|
|
using namespace std;
|
|
|
|
void merge(vector<int>& nums, int l, int r){
|
|
int mid = (l + r) / 2;
|
|
int i = l, j = mid + 1;
|
|
vector<int> tmp;
|
|
while(i <= mid && j <= r){
|
|
if(nums[i] <= nums[j]) tmp.push_back(nums[i++]);
|
|
else tmp.push_back(nums[j++]);
|
|
}
|
|
while(i <= mid) tmp.push_back(nums[i++]);
|
|
while(j <= r) tmp.push_back(nums[j++]);
|
|
|
|
for(int x = l; x <= r; x++){
|
|
nums[x] = tmp[x - l];
|
|
}
|
|
}
|
|
|
|
void mergeSort(vector<int>& nums, int l, int r){
|
|
//回溯，后序
|
|
if(l >= r) return;
|
|
int mid = (l + r) / 2;
|
|
mergeSort(nums, l, mid);
|
|
mergeSort(nums, mid + 1, r);
|
|
//合并可以写在一起，但是分开清晰
|
|
merge(nums, l, r);
|
|
}
|
|
|
|
|
|
int main(){
|
|
|
|
return 0;
|
|
} |