登陆 注册

java算法实现之归并排序(两路归并)

守望者 2020-04-25 296人围观 ,发现0个评论 java

     所谓归并排序同快速排序一样(java算法实现之快速排序)是一种基于分治法(分而治之)的排序算法,归并排序又分为两路归并排序和多路归并排序,本文介绍两路归并排序。


两路归并算法思路:分而治之

         先将一个数组自上而下不断对等分成两个子数组(递归实现)直至子数组长度为一,

     然后自下而上依次将两个相邻子数组归并到一个新的子数组,同时完成新子数组的排序,

     经过多轮归并最终将所有子数组归并到一个新数组完成最终排序。


实现过程:

    举例:这有一个数组:9, 8, 7, 6, 5, 4, 3, 2, 10

先分:

   第一轮原数组分成两个子数组:{9, 8, 7, 6, 5},{4, 3, 2, 10}

   第二轮原子数组再细分成两个子数组得到四个子数组 {9, 8, 7},{6, 5},{4, 3,},{2, 10}

   第三轮原子数组再细分成两个子数组得到八个子数组 {9, 8}, {7},{6},{ 5},{4},{3,},{2},{10}

   第四轮原子数组再细分成两个子数组得到九个子数组 {9,},{8},{7},{6},{ 5},{4},{3,},{2},{10}


再归并:

      第一轮将原两个子数组归并到一个新子数组并排序得到五个新子数组:{8,9},{6,7},{4,5},{2,3},{10}

      第二轮将原两个子数组归并到一个新子数组并排序得到三个新子数组:{6,7,8,9},{2,3,4,5},{10}

      第三轮将原两个子数组归并到一个新子数组并排序得到两个新子数组:{2,3,4,5,6,7,8,9},{10}

      第四轮将原两个子数组归并到一个新子数组并排序得到一个新数组:    {2,3,4,5,6,7,8,9,10}


以上经过四轮“分”和四轮“归并”完成了真个数组的最终排序。    


最终排序结果如下:

QQ截图20200425100233.jpg


归并排序函数代码如下:

 public static int[] mergeSort(int[] arr, int l, int r) {
		 
	        if (l == r) {return new int[] { arr[l] };}
	         
//	        int mid = l + (r - l) / 2;
	        int mid = (r + l) / 2;
	        
	        int[] leftArr = mergeSort(arr, l, mid); //对等分左有序数组
	        int[] rightArr = mergeSort(arr, mid + 1, r); //对等分右有序数组
	        int[] newArr = new int[leftArr.length + rightArr.length]; //合并后的新有序数组
	         
	        int m = 0, i = 0, j = 0; 
	        while (i < leftArr.length && j < rightArr.length) {  // 排序并合并两个子有序数组
	        	newArr[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
	        }
	        while (i < leftArr.length)
	        	newArr[m++] = leftArr[i++];
	        while (j < rightArr.length)
	        	newArr[m++] = rightArr[j++];
	        
	        return newArr;
	    }


    转发请附上本文链接:https://tufeng.xyz/java/53.html,谢谢合作!

上一篇:友链申请 下一篇:java算法实现之堆排序
请发表您的评论
请关注微信公众号
微信二维码