归并排序-非递归实现

本文主要是介绍归并排序-非递归实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

归并排序的非递归实现 

我们可以把 一个数组 先拆分成 最小单元，这是分，

拆分成最小单元之后，我们对每个最小单元进行一次合并，这是治

最小单元 合并一次之后，我们继续 在上一次合并的基础上拆分，并且合并这是 合 ，

直到 整个数组 只被拆成了两部分，在进行最终一次的和 

 我们画图举个例子

源代码如下，我们的merge的合并函数的参数是  原数组，左侧小数组索引位置开头，左侧小数组索引位置结束，右侧小数组索引位置开头，右侧小数组索引位置结束，要拷贝的数组

 public static void main(String[] args) {int []arr={9,3,8,7,4,6,1,2,5};sort(arr);System.out.println(Arrays.toString(arr));}// 1 2  3 4   5 6  7 8private static void sort(int[] arr) {int []arr1=new int[arr.length];for (int width = 1; width < arr.length; width *= 2) {for (int left = 0; left < arr.length; left+=2*width) {int right=Math.min(left+2*width-1, arr.length-1);//  0 1  2 3   4 5  6 7int m=Math.min(left+width-1, arr.length-1);merge(arr, left, m, m+1, right , arr1);}System.arraycopy(arr1,0,arr,0,arr.length);}}private static void merge(int[] arr, int left, int leftEnd, int right, int rightEnd,int[]arr2) {int k=left;while(left<=leftEnd&&right<=rightEnd){if(arr[left]<arr[right]){arr2[k++]=arr[left];left++;}else {arr2[k++]=arr[right];right++;}//        2} //    0  1  2 3// 将剩余的左侧元素复制到arr2中while (left <= leftEnd) {arr2[k++] = arr[left++];}// 将剩余的右侧元素复制到arr2中while (right <= rightEnd) {arr2[k++] = arr[right++];}}

 

这篇关于归并排序-非递归实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---