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

糖逗

#include <vector>
#include<iostream>
using namespace std;
void merge(vector<int>& input, int left, int middle, int middle_, int right){
        int temp1 = left, temp2 = middle_;
        int* res = new int[right - left + 1];
        int r = 0;
        while(temp1 <= middle && temp2 <= right){
                if(input[temp1] <= input[temp2]){
                        res[r++] = input[temp1++];
                }
                else{
                        res[r++] = input[temp2++];
                }        
        }
        while(temp1 <= middle){
                res[r++] = input[temp1++];
        }
        while(temp2 <= right){
                res[r++] = input[temp2++];
        }
        for(int i = 0; i < right - left + 1; i++){
                input[i + left] = res[i];
        }
        delete[]res;
}

void solution(vector<int>& input, int left, int right){
        if(left >= right) return;
        int middle = left + (right - left) / 2;

        solution(input, left, middle);
        solution(input, middle + 1, right);
        merge(input, left, middle, middle + 1, right);
                
        
}



int main(void){
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        solution(input, 0, input.size()-1);
        for(int i = 0; i < input.size(); i++){
                cout << input[i] << " ";
        }
        cout << endl;
        return 0;
}

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

糖逗

int temp1 = left, temp2 = middle_;

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

糖逗