C++归并排序算法
*MERGE-SORT */ #include<cstdlib> #include<limits> #include<iostream> #include<vector> #include<iomanip> using namespace std; typedef vector<int>::iterator ivecIte; void merge(vector<int> &ivec, ivecIte iteB, ivecIte iteMark, ivecIte iteE) { vector<int> v1(iteB, iteMark), v2(iteMark, iteE); //哨兵!!! v1.push_back(numeric_limits<int>::max()); v2.push_back(numeric_limits<int>::max()); ivecIte ite1 = v1.begin(), ite2 = v2.begin(); for(ivecIte iteTurn = iteB; iteE != iteTurn; ++iteTurn){ if(*ite2 > *ite1) {*iteTurn = *ite1; ite1++;} else{*iteTurn = *ite2; ite2++;} } } void mergeSort(vector<int> &ivec, ivecIte iteB, ivecIte iteE) { size_t div = iteE - iteB; if(1 < div) { div /= 2; mergeSort(ivec, iteB, iteB + div); mergeSort(ivec, iteB + div, iteE); merge(ivec, iteB, iteB + div, iteE); } } int main() { vector<int> ivec; cout<<"input some integers with end-of-file!"<<endl; int inData; while(cin>>inData) ivec.push_back(inData); ivecIte iteS = ivec.begin(), iteE = ivec.end(); mergeSort(ivec, iteS, iteE); for(iteS = ivec.begin(); iteS != ivec.end(); ++iteS) cout<<setw(5)<<*iteS; cout<<endl; system("PAUSE"); return EXIT_SUCCESS; }