- #include
- #include
- #include
- #include using namespace std;
- voidMergeSort(vector<int> &data, vector<int> &cdata,intp,int r);
- voidMerge(vector<int> &data, vector<int> &cdata,intp,intq,int r);
- voidMergeSort(vector<int> &data)
- {
- vector<int> cdata(data.size());
- MergeSort(data, cdata, 0, data.size() -1);
- }
- voidMergeSort(vector<int> &data, vector<int> &cdata,intp,int r)
- {
- if(p < r) {
- intq = (p + r) /2;
- MergeSort(data, cdata, p, q);
- MergeSort(data, cdata, q +1, r);
- Merge(data, cdata, p, q, r);
- }
- }
- voidMerge(vector<int> &data, vector<int> &cdata,intp,intq,int r)
- {
- for(inti = p; i <= r; ++i)
- cdata[i] = data[i];
- inti = p, j = q +1, k = p;
- while(i <= q && j <= r) {
- if(cdata[i] <= cdata[j])
- data[k++] = cdata[i++];
- else
- data[k++] = cdata[j++];
- }
- while(i <= q)
- data[k++] = cdata[i++];
- while(j <= r)
- data[k++] = cdata[j++];
- }
- intmain(intargc,char*argv[])
- {
- vector<int> data1 = {10,9,8,7,6,5,4,3,2,1 };
- vector<int> data2;
- default_random_engine dre(7);
- uniform_int_distribution<int> di(-100,100);
- for(inti =0; i <50; ++i)
- data2.push_back(di(dre));
- MergeSort(data1);
- for (auto i : data1)
- cout << i <<" ";
- cout << endl;
- MergeSort(data2);
- for (auto i : data2)
- cout << i <<" ";
- cout << endl;
- return 0;
- }
来源: