排序-归并

 1 void merge(vector<int>& init, int start, int mid, int end) {
 2     // 两个有序数组的合并，一个数组一个指针
 3     vector<int> tmp;   // 临时数组记录两个数组的排序结果
 4     int i = start, j = mid + 1;
 5     while (i <= mid && j <= end) {  // 任意一个数组遍历完成就不用再遍历了
 6         if (init[i] < init[j]) {
 7             tmp.push_back(init[i]); ++i;   // 把最小值插入向量，再继续比较得到最小值
 8         }
 9         else {
10             tmp.push_back(init[j]); ++j;
11         }
12     }
13     // 如果还有一个没遍历完成，不管是谁的，肯定都是最大的元素了，直接移动到tmp就ok
14     while (i <= mid) { tmp.push_back(init[i]); ++i; }
15     while (j <= end) { tmp.push_back(init[j]); ++j; }
16     // 将tmp数组放入原来的数组
17     for (int i = start; i <= end; ++i) {
18         init[i] = tmp[i - start];
19     }
20 }
21 
22 // 归并 分（二分）而治（合并排序）之
23 // 参数列表里可以不写临时数组吗
24 void sort(vector<int>& init, int start, int end) {
25     if (start >= end) return;
26     int mid = (start + end) / 2;
27     sort(init, start, mid);
28     sort(init, mid + 1, end);
29     merge(init, start, mid, end);
30 }
31 
32 int main() {
33     vector<int> init = { 3,2,6,7,1,3,5,100,38,101,0 };
34     // merge(init, 0, 0, 1);
35     sort(init,0,init.size()-1);
36     for (int i = 0; i < init.size(); ++i) {
37         cout << init[i]<< " ";
38     }
39     return 0;
40 }