归并排序-递归
#include <iostream>#include <vector>
using namespace std;
void merge_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, vector<int> &vec) {
int i = 0;
int j = 0;
while (i < sub_vec1.size() && j < sub_vec2.size()) {
if (sub_vec1 <= sub_vec2) {
vec.push_back(sub_vec1);
i++;
}
else {
vec.push_back(sub_vec2);
j++;
}
}
for (; i < sub_vec1.size(); i++) {
vec.push_back(sub_vec1);
}
for (; j < sub_vec2.size(); j++) {
vec.push_back(sub_vec2);
}
}
void merge_sort(vector<int> &vec) {
if (vec.size() < 2) {
return;
}
vector<int> sub_vec1;
vector<int> sub_vec2;
int mid = vec.size() / 2;
int i = 0;
for (i = 0; i < mid; i++) {
sub_vec1.push_back(vec);
}
for (i = mid; i < vec.size(); i++) {
sub_vec2.push_back(vec);
}
merge_sort(sub_vec1);
merge_sort(sub_vec2);
vec.clear();
merge_vec(sub_vec1, sub_vec2, vec);
}
int main() {
vector<int> test = { 5,-7,9,8,1,4,-3,10,2,0 };
merge_sort(test);
for (auto val : test) {
cout << val << " ";
}
cout << endl;
}
页:
[1]