template<typename T> voidmerge_sort(T arr[], int len){ //使用指针来交换的方式 /* * 这道题超级考验数组传参时指针的知识 * */ T *a = arr; T *b = new T[len]; for (int seg = 1; seg < len; seg += seg) { //第一个循环，让最初始的一个容器开始进行融合，然后容器内容从1到2到4 for (int start = 0; start < len; start += seg + seg) { //第二个循环，让每次相邻的两个容器进行排序 int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len); // 比较的容器：第一个容器是从low到mid，第二个容器是从mid到high，然后循环的时候会一直增加两个容器的内容，也就是seg //low ，mid，high都是每次比较容器的下标，所以要跟长度相比取最小， // 有可能最后一次容器比较的时候，只有一个容器了，且容器的大小不足所以mid最后取到len，也可能第二容器不够seg了，只能取到len了
int k = low; //将本次比较的两个容器的起始头拿出来，在这里一个个赋值 int start1 = low, end1 = mid; //将两个容器的起始头拿出来 int start2 = mid, end2 = high; //这个三个while循环会把两个容器里在的值都拿出来 while (start1 < end1 && start2 < end2) //这个while循环会把两个容器里在的值都拿出来，直到其中一个容器都没有了 b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) //当第一个的循环已经做完之后，肯定有一个容器都没有了，但是判断是不是第一个容器还有东西，如果有东西就全部取出来 b[k++] = a[start1++]; while (start2 < end2) //当第一个的循环已经做完之后，肯定有一个容器都没有了，但是判断是不是第二个容器还有东西，如果有东西就全部取出来 b[k++] = a[start2++]; } /* * 下面三句是数组作为传参的精髓，数组作为传参进来的时候，是变成数组第一位的指针arr，指针传进来后可以对指针所指向的内容进行修改，但是怎么改都不会影响到外面arr的地址 * 所以一定每次处理的时候，都是要在arr地址上进行处理的，否则没有意义。【这是先验知识】 * 然后函数一开始就new了个b，这个b的地址是跟arr的地址不一样的 * 当b已经处理完后，要把b的东西给a，不能直接给，因为直接赋给a就是把b的地址给a，那么后续的处理时，arr的地址里内容还是没有变化呀 * 所以需要把a的地址暂时存放起来，此时一开始a的地址也是arr的地址，将其存放起来，再把b的地址给a，也就是把b里面的内容给了啊，因为，后续要拿a里的内容进行处理呀 * 此时做完第二句之后呢，a的地址和b的地址是一样的，再下一次for循环的时候，你不可以在同个地址上的内容上进行移动数值吧，那就出错了呀 * 类似【2,1】,处理后得到结果肯定变成【1,1】了 * 刚好又有个temp的地址可以使用，那就直接将temp的地址给b了，然后最后一次for循环处理后，b的地址还是在arr的地址之上 * */ T *temp = a; a = b; b = temp; }
/* * 虽然下面的if语句注释了，也可以正常得到结果，但是按照逻辑来说的话，上面的最后一次循环之后，a拿到的是b的地址，所以拿到的是b里面的内容，所以要进行 * 一次判断，看a是不是的地址是不是还在arr的地址上，如果不是的话，但是此时b的地址肯定是在arr的地址上的（因为是temp一直在保存着arr的地址），所以只要把 * a的内容给b，b的地址又是arr的地址，所以处理完成后，arr的地址上指的内容肯定就被修改好了 * */ if (a != arr) { for (int i = 0; i < len; i++) b[i] = a[i]; b = a; }
