C++实现归并排序（分治算法）

糖逗

1. #include <vector>
   
2. #include<iostream>
   
3. using namespace std;
   
4. void merge(vector<int>& input, int left, int middle, int middle_, int right){
   
5.         int temp1 = left, temp2 = middle_;
   
6.         int* res = new int[right - left + 1];
   
7.         int r = 0;
   
8.         while(temp1 <= middle && temp2 <= right){
   
9.                 if(input[temp1] <= input[temp2]){
   
10.                         res[r++] = input[temp1++];
    
11.                 }
    
12.                 else{
    
13.                         res[r++] = input[temp2++];
    
14.                 }       
    
15.         }
    
16.         while(temp1 <= middle){
    
17.                 res[r++] = input[temp1++];
    
18.         }
    
19.         while(temp2 <= right){
    
20.                 res[r++] = input[temp2++];
    
21.         }
    
22.         for(int i = 0; i < right - left + 1; i++){
    
23.                 input[i + left] = res[i];
    
24.         }
    
25.         delete[]res;
    
26. }
    
27. 
    
28. void solution(vector<int>& input, int left, int right){
    
29.         if(left >= right) return;
    
30.         int middle = left + (right - left) / 2;
    
31. 
    
32.         solution(input, left, middle);
    
33.         solution(input, middle + 1, right);
    
34.         merge(input, left, middle, middle + 1, right);
    
35.                
    
36.        
    
37. }
    
38. 
    
39. 
    
40. 
    
41. int main(void){
    
42.         vector<int> input;
    
43.         int number;
    
44.         while(cin >> number){
    
45.                 input.push_back(number);
    
46.         }
    
47.         solution(input, 0, input.size()-1);
    
48.         for(int i = 0; i < input.size(); i++){
    
49.                 cout << input[i] << " ";
    
50.         }
    
51.         cout << endl;
    
52.         return 0;
    
53. }

复制代码

参考链接：https://blog.csdn.net/zheng_ze_qi/article/details/79810916

糖逗

1. int temp1 = left, temp2 = middle_;

复制代码

这一行必须要单独赋值，因为后续left 和middle_在solution函数中要进行递归会改变值。

糖逗