归并排序是稳定的排序算法,也比较常用,下面介绍下排序算法的思路。

原始数据如下

5 1 6 7 2 8 4

归并排序的原理是找到数组的中间位置,将数组拆分为2,依次递归拆分,直到拆分到只有一个数为止。接下来进行数组合并,将左右两部分数组依次对比存入临时数组中,达到数组中部分有序,依次递归合并,最终实现归并排序。

下面图例演示数据变化过程

在归并排序中,一定要使用和nums等长的临时数组temps用来存储每次递归排序的数据,分段排序后复制给nums。

下面图例演示合并子序列

注:图片摘自网络

java归并排序代码如下:

public class MegerSort {

	public static void main(String[] args){
		int[] nums = {5,1,6,7,2,8,4};
		int[] temps = new int[nums.length];
		mergeSort(nums,0,nums.length-1,temps);
		System.out.println(Arrays.toString(nums));
	}
	
	/**
	 * 归并排序
	 * https://www.cnblogs.com/chengxiao/p/6194356.html
	 */
	public static void mergeSort(int[] nums,int left,int right,int[] temps){
		// 终止条件
		if(left>=right){
			return;
		}
		// 从从中间截断,分别排序左右两边的元素
		int mid = (right+left)/2;
		// 左边
		mergeSort(nums,left,mid,temps);
		// 右边
		mergeSort(nums,mid+1,right,temps);
		// 然后合并
		merge(nums,left,mid,right,temps);
	}
	/**
	 * 合并元素
	 * @param nums
	 * @param left
	 * @param mid
	 * @param right
	 * @param temps
	 */
	public static void merge(int[] nums,int left,int mid,int right,int[] temps){
		// 左边开始下标
		int l = left;
		// 右边开始下标
		int r = mid+1;
		// temps临时数组下班
		int index = 0;
		// 左右合并
		while(l<=mid &amp;&amp; r<=right){
			if(nums[l]<=nums[r]){
				// 左边小于等于右边,将nums中左边的数据放入temps临时数组
				temps[index++]= nums[l++];
			}else{
				// 左边大于右边,将nums中右边的数据放入temps临时数组
				temps[index++]= nums[r++];
			}
		}
		// 经过上面的while循环,左右两边一定有一方元素完全复制到了temps数组中
		// 剩下的一方中的元素一定是最大的元素,只需依次复制到temps中即可
		if(l<=mid){
			// 左边未复制完
			while(l<=mid){
				temps[index++] = nums[l++];
			}
		}
		if(r<=right){
			// 右边未复制完
			while(r<=right){
				temps[index++] = nums[r++];
			}
		}
		System.out.println(Arrays.toString(temps));
		// 将temps中的数据依次复制到nums中
		for(int i=0;left<=right;i++){
			nums[left++] = temps[i];
		}
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注