# C++中的合并排序代码实现

``````#include <iostream>
#include <vector>
#include <algorithm>

void mergesort(std::vector<int>& A, int l, int r);

void merge(std::vector<int>& A, int l, int m, int r);

void mergesort(std::vector<int>& A, int l, int r) {

if(l < r) {

int m = l + (r - l) / 2;

mergesort(A, l, m);

mergesort(A, m + 1, r);

merge(A, l, m, r);

}
}

void merge(std::vector<int>& A, int l, int m, int r) {

std::vector<int> L(A.begin() + l, A.begin() + (m - 1));
std::vector<int> R(A.begin() + m, A.begin() + r);

std::vector<int>::iterator i = L.begin();
std::vector<int>::iterator j = R.begin();
std::vector<int>::iterator k = A.begin() + l;

while(i != L.end() && j != R.end()) {
if(*i <= *j) {
*k = *i;
i++;
}
else {
*k = *j;
j++;
}
k++;
}

while(i != L.end()) {
*k = *i;
i++;
k++;
}

while(j != R.end()) {
*k = *j;
j++;
k++;
}
}

void print_vector(std::vector<int> A) {

std::vector<int>::iterator it;

for(it = A.begin(); it != A.end(); ++it) {
std::cout << *it << " ";
}
}

int main() {
std::vector<int> A = {178, 1156, 136, 5, 6, 7};
mergesort(A, 0, A.size() - 1);

print_vector(A);
}
``````

``````if(l < r) {
int m = l + (r - l) / 2;
mergesort(A, l, m);
mergesort(A, m + 1, r);
merge(A, l, m, r);

}
``````

`````` std::vector<int> L(A.begin() + l, A.begin() + (m - 1));
``````

0 条评论