归并排序-递归

pwnmelife

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. void merge_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, vector<int> &vec) {
   
6.         int i = 0;
   
7.         int j = 0;
   
8.         while (i < sub_vec1.size() && j < sub_vec2.size()) {
   
9.                 if (sub_vec1[i] <= sub_vec2[j]) {
   
10.                         vec.push_back(sub_vec1[i]);
    
11.                         i++;
    
12.                 }
    
13.                 else {
    
14.                         vec.push_back(sub_vec2[j]);
    
15.                         j++;
    
16.                 }
    
17.         }
    
18.         for (; i < sub_vec1.size(); i++) {
    
19.                 vec.push_back(sub_vec1[i]);
    
20.         }
    
21.         for (; j < sub_vec2.size(); j++) {
    
22.                 vec.push_back(sub_vec2[j]);
    
23.         }
    
24. }
    
25. 
    
26. void merge_sort(vector<int> &vec) {
    
27.         if (vec.size() < 2) {
    
28.                 return;
    
29.         }
    
30.         vector<int> sub_vec1;
    
31.         vector<int> sub_vec2;
    
32.         int mid = vec.size() / 2;
    
33.         int i = 0;
    
34.         for (i = 0; i < mid; i++) {
    
35.                 sub_vec1.push_back(vec[i]);
    
36.         }
    
37.         for (i = mid; i < vec.size(); i++) {
    
38.                 sub_vec2.push_back(vec[i]);
    
39.         }
    
40.         merge_sort(sub_vec1);
    
41.         merge_sort(sub_vec2);
    
42.         vec.clear();
    
43.         merge_vec(sub_vec1, sub_vec2, vec);
    
44. }
    
45. 
    
46. 
    
47. 
    
48. int main() {
    
49.         vector<int> test = { 5,-7,9,8,1,4,-3,10,2,0 };
    
50.         merge_sort(test);
    
51.         for (auto val : test) {
    
52.                 cout << val << " ";
    
53.         }
    
54.         cout << endl;
    
55. }

复制代码