【C++代码】归并排序（迭代与递归）

        二路归并思想：将两个已经有序和数组合并成一个有序的数组                

迭代方法：

        如图，先令子数组宽度为1，进行两两合并；第一轮之后，再令子数组宽度为2，进行两两合并；第二轮之后，再令子数组宽度为4，进行两两合并……直到子数组宽度为整个数组的大小为止。         由于数组的大小并不一定是2的某个次方，因此在合并时，会出现两个长度不一样的数组进行合并的情况，但没关系。

       

       

C++代码

//将vec[begin1, ... ,end1]和 vec[end1+1, ... ,end_2]合并后存放到temp中 void mergeTwo(vector<int> &vec, int begin1, int end1, int end2) { int i = begin1, j = end1+1, k = 0; vector<int> temp(end2 - begin1 + 1); // 临时数组，用于存放两段有序数组合并后的结果 while (i <= end1 && j <= end2) { if (vec[i] < vec[j]) { temp[k++] = vec[i++]; } else { temp[k++] = vec[j++]; } } while (i <= end1) { temp[k++] = vec[i++]; } while (j <= end2) { temp[k++] = vec[j++]; } // 用合并后的结果temp把vec[begin1,... ,end_2]覆盖掉 for (int i = 0; i < end2-begin1+1; ++i) { vec[begin1 + i] = temp[i]; } } // 归并排序，迭代实现。vec为输入的待排序数组 void mergeSort(vector<int>& vec) { const int siz = vec.size(); for (int width = 1; width < siz; width *= 2) { for (int i = 0; i < siz; i += 2 * width) { mergeTwo(vec, i,min( i + width - 1,siz-1), min(i + 2 * width - 1, siz - 1)); } } }

       

               

       

递归方法：

        先将数组分为两部分，再把每部分又分为两部分……直到分割到每部分长度都为1时，停止分割，开始两两合并。         递归和迭代的代码不同的就是mergeSort()函数，把两个有序数组合并成一个有序数组的mergeTwo()函数都是一样的。

       

       

C++代码

//将vec[begin1, ... ,end1]和 vec[end1+1, ... ,end2]合并后存放到temp中 void mergeTwo(vector<int> &vec, int begin1, int end1, int end2) { int i = begin1, j = end1+1, k = 0; vector<int> temp(end2 - begin1 + 1); // 临时数组，用于存放两段有序数组合并后的结果 while (i <= end1 && j <= end2) { if (vec[i] < vec[j]) { temp[k++] = vec[i++]; } else { temp[k++] = vec[j++]; } } while (i <= end1) { temp[k++] = vec[i++]; } while (j <= end2) { temp[k++] = vec[j++]; } // 用合并后的结果temp把vec[begin1,... ,end2]覆盖掉 for (int i = 0; i < temp.size(); ++i) { vec[begin1 + i] = temp[i]; } } void mergeSort(vector<int> &vec, int begin, int end) { if (begin < end) { int mid = (begin + end) / 2; // 分割成两部分 mergeSort(vec, begin, mid); // 递归地对左边进行分割 mergeSort(vec, mid + 1, end); // 递归地对右边进行分割 mergeTwo(vec, begin, mid, end); // 对分割出的两个数组进行合并 } }