这两个问题不清楚，据说会“合并排序”？

今天分享的内容涉及以下两个问题：归并排序的迭代实现；就地归并排序（In-PlaceMergeSort）的实现；归并排序的迭代实现在正式看代码之前，希望大家了解清楚归并排序的递归实现不熟悉也没关系。阅读本文以说明“归并排序”算法（修订版）一文。迭代和递归（Iteration&Recursion）一直是相得益彰的。你有我，我有你。任何算法的递归实现都可以转化为迭代实现。只要成本足够小，收益（获得的空间和时间效率的提升）就可以足够高。归并排序也可以，但是归并排序的迭代实现比较特殊。与大多数递归和迭代变换不同，归并排序不需要程序中显式的栈辅助栈，但它也可以去除递归调用。迭代地实现归并排序。这张图一定很眼熟吧。这就是标准递归实现过程中的分而治之。使用迭代实现时，策略上有两个变化：除法采用循环（迭代）代替递归的方法；划分策略不同于递归的方法，仍然符合归并排序的思想；我们还是以下面这个数组为例（感觉这个数组无所不能，哈哈）：Step1:Merge5and1Step2:Merge4and2第三步:merge8and4;第四步：merge[1,5,2,4]第五步：merge[4,8]第六步：merge[1,2,4,5,4,8]看到这里，看不出来区别在合并排序迭代和递归之间。别担心：这次它会清晰可见。归并排序迭代实现中的归并顺序与递归明显不同，递归就是把原来长度为n的数组一分为二，然后把这两个（1/2）数组再一分为二，直到分成n个长度为1的元素。然后两两按照大小合并，依此类推，直到最终形成一个包含n个数的有序数组。迭代是不同的。默认情况下，数组中的元素被视为长度为1的n个元素；依次以2为一组进行合并，以4个元素为一组进行合并（小于4的，如[4,8]，小于4的按照剩余的个数2进行合并），....，最后与n/2个元素合并为一个组，得到我们的有序数组。在迭代实现中，只从图中看不出划分的过程，但实际上在合并之前就已经进行了划分，只不过这个划分和递归调用的划分不同，而是迭代用来。忽略合并的实现细节，我们只看迭代是如何实现的。staticvoidmergeSort(intarr[],intn){intcurr_size;//标识当前合并的子数组的大小，已知从1到n/2intleft_start;//标识当前要合并的子数组的起点for(curr_size=1;curr_size<=n-1;curr_size=2*curr_size){for(left_start=0;left_start2。此时不使用额外的空间实现合并操作，start2之前和start1之后的元素（包括start1)向后移动，将2复制到start1指向的位置，然后将start1、start2和mid向后移动Move：第三步：比较start1指向的元素4和start2指向的元素4，4=4，所以直接右移start1，即start1++。第四步：和第二步类似，比较start1指向的元素5和start2指向的元素4，5>4，向前移动4，向后移动5，再向后移动start1，start2和mid：Step5：比较start1指向的元素5和start2指向的元素8，**5<8**，直接右移start1，即start1++；此时start1>mid，说明合并完成。合并操作的实现代码，空间复杂度为：staticvoidmerge(intarr[],intstart1,intmid,intend){intstart2=mid+1;//如果mid小于等于mid+1的元素，表示数组已经有序，不需要Mergeif(arr[mid]<=arr[start2]){return;}while(start1<=mid&&start2<=end){if(arr[start1]<=arr[start2]){start1++;}else{intvalue=arr[start2];intindex=start2;//向后移动[start1,start2-1]中的元素while(index!=start1){arr[index]=arr[index-1];index--;}arr[start1]=value;start1++;mid++;start2++;}}}注意这个合并操作涉及两个嵌套的while循环，所以与标准实现相比空间复杂度为,和的时间复杂度，这种合并策略虽然将空间复杂度降到了最低，但是也牺牲了时间复杂度，你必须失去一个，这个世界上没有两全其美！转载本文请联系静语公众号。