C++歸并排序非遞歸

歸并排序非遞歸

1.算法思想

開始以間隔為1進行歸并，也就是說，第一個元素跟第二個元素進行歸并，第三個與第四個元素進行歸并；

然後，再以間隔為2進行歸并，第一個元素到第四個元素進行歸并，第五個元素到第八個元素進行歸并；

再以間隔2*2進行歸并，同理，直到2*k超過數組長度為止。

2.具體代碼

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int min(int x, int y){
    return (x < y) ? x : y;
}

vector<int> Merge(vector<int> &data, int begin, int mid, int end){    
    int n1 = mid - begin + 1;
    int n2 = end - mid;
    int left[n1], right[n2];
    for(int i = 0; i < n1; i++){
        left[i] = data[begin+i];
    }
    for(int i = 0; i < n2; i++){
        right[i] = data[mid + i + 1];
    }
    int i = 0, j = 0, k = begin;
    while(i < n1 && j < n2){
        if(left[i] <= right[j]){
            data[k++] = left[i++];
        }else{
            data[k++] = right[j++];
        }
    }
    while(i < n1){
        data[k++] = left[i++];
    }
    while(j < n2){
        data[k++] = right[j++];
    }
    return data;
}

vector<int> MergeSort(vector<int> data){
    vector<int> res;
    if(data.empty()){
        return res;
    }
    unsigned int i = 1;
    while(i < data.size()){
        for(unsigned int begin = 0; begin < data.size(); begin += 2*i){
            int mid = begin + i - 1;
            int end = min(begin + 2 * i -1, data.size()-1);
            res = Merge(data, begin, mid, end);
        }
        i = 2 * i;
    }
    return res;
}

void printVec(vector<int> &vec){
    if(vec.empty()){
        return ;
    }
    for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++){
        cout<< *it << " ";
    }
    cout << endl;
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    vector<int> vec(arr, arr + 6);
    vector<int> res;

    cout << "the origonal array:" << endl;
    printVec(vec);

    res = MergeSort(vec);
    cout << "the merge sort array:" << endl;
    printVec(res);

    return 0;
}