排序算法之归并排序(Merge Sort)

归并排序(Merge Sort)

描述

1. 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
2. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
3. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
4. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
5. 重复上一个步骤 直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾
6. 归并是一种稳定且高效的排序（Arrays.sort(),TimSort排序就是归并排序的优化版）

案例

当前有一个数组 { 5,6,1,3,8,4,6,9,0,2 } ，用 希尔排序 对其进行 升序 排序

代码

代码思路：

1. 主要采用分治和递归
2. 需要申请一个能够容纳合并排序后数列的集合空间
3. 将数组按照分治的策略进行分解成若干个小子序列做比较排序
4. 将两个分治后的数列从同一方向进行比较，将较小的元素放入合并的空间
5. 最后合并成一个排序好的数列

//为了流程看的清楚一些，打了很多日志

import java.util.Arrays;

public class Mergesort {
	

	public static void main(String[] args) {

		int[] a = {5,6,1,3,8,4,6,9,0,2};
		System.out.println("原始数组："+Arrays.toString(a));
		
		//归并排序采用了分治的思想
		sort(a);
		
		System.out.println("经过归并排序后："+Arrays.toString(a));
		
	}
	
	public static void sort(int[] a) {
		sort(a,0,a.length-1);//进入分治阶段
	}
	
	//1.二叉树
	//2.递归
	public static void sort(int[] a,int left , int right ) {
		System.out.println("[开始对数组进行排序][左开始位置："+left+"][右结束位置"+right+"]");
		//不强求元素个数的奇偶
		if(left < right){//左边指针必须小于右边的指针
			//找中间的位置，准备二分
			int mid = (left+right) /2;
			//分治
			//通过递归的方式，使左右归并的子树都有序

			//1.左边归并排序
			System.out.println("===========================开始左排序[左开始位置："+left+"][右结束位置"+mid+"]");
			sort(a,left,mid);//分
			
			//2.右边归并排序
			System.out.println("===========================开始右排序[左开始位置："+(mid+1)+"][右结束位置"+right+"]");
			sort(a,mid+1,right);//分

			System.out.println("***********************************开始合并[左开始位置："+left+"][右结束位置"+right+"]");
			//3.合并
			merge(a, left, mid, right);
			
		} else {
			System.out.println("左右下标相同，跳过");
		}
	}
	
	//合并排序
	public static void merge(int[] a,int left,int mid ,int right) {
		int startIndex = left;
		int endIndex = right;
		System.out.println("排序前[数组："+Arrays.toString(a)+"][左开始位置："+startIndex+"][右结束位置"+endIndex+"]");
		
		int[] temp = new int[a.length];

		int i = left;//左序列指针
		int j = mid + 1;//右序列
		int index = 0; //临时数组的指针
		while(i<=mid && j <=right) {
			if(a[i] > a[j]) {
				System.out.println("开始比较左右子序列,右序列取值更小");
				temp[index++] = a[j++];
			} else {
				temp[index++] = a[i++];
				System.out.println("开始比较左右子序列,左序列取值更小");

			}
		}
		
		//检查左右子序列是否存在剩余，将剩余依次放入数组中
		while(i <=mid ) {
			System.out.println("开始依次放入左子序列");
			temp[index++] = a[i++];
		}
		while(j <=right) {
			System.out.println("开始依次放入右子序列");

			temp[index++] = a[j++];
		}
		
		System.out.println("排序结束[子序列排序结果记入临时数组"+Arrays.toString(temp)+"]");


		index = 0;
		while(left <= right){//依次将临时数组的值放入原数组的子序列对应的位置
			a[left++] = temp[index++];
		}
		
		System.out.println("排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组："+Arrays.toString(a)+"][左开始位置："+startIndex+"][右结束位置"+endIndex+"]");


	}

}

控制台日志输出

原始数组：[5, 6, 1, 3, 8, 4, 6, 9, 0, 2]
[开始对数组进行排序][左开始位置：0][右结束位置9]
===========================开始左排序[左开始位置：0][右结束位置4]
[开始对数组进行排序][左开始位置：0][右结束位置4]
===========================开始左排序[左开始位置：0][右结束位置2]
[开始对数组进行排序][左开始位置：0][右结束位置2]
===========================开始左排序[左开始位置：0][右结束位置1]
[开始对数组进行排序][左开始位置：0][右结束位置1]
===========================开始左排序[左开始位置：0][右结束位置0]
[开始对数组进行排序][左开始位置：0][右结束位置0]
左右下标相同，跳过
===========================开始右排序[左开始位置：1][右结束位置1]
[开始对数组进行排序][左开始位置：1][右结束位置1]
左右下标相同，跳过
***********************************开始合并[左开始位置：0][右结束位置1]
排序前[数组：[5, 6, 1, 3, 8, 4, 6, 9, 0, 2]][左开始位置：0][右结束位置1]
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[5, 6, 0, 0, 0, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[5, 6, 1, 3, 8, 4, 6, 9, 0, 2]][左开始位置：0][右结束位置1]
===========================开始右排序[左开始位置：2][右结束位置2]
[开始对数组进行排序][左开始位置：2][右结束位置2]
左右下标相同，跳过
***********************************开始合并[左开始位置：0][右结束位置2]
排序前[数组：[5, 6, 1, 3, 8, 4, 6, 9, 0, 2]][左开始位置：0][右结束位置2]
开始比较左右子序列,右序列取值更小
开始依次放入左子序列
开始依次放入左子序列
排序结束[子序列排序结果记入临时数组[1, 5, 6, 0, 0, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 5, 6, 3, 8, 4, 6, 9, 0, 2]][左开始位置：0][右结束位置2]
===========================开始右排序[左开始位置：3][右结束位置4]
[开始对数组进行排序][左开始位置：3][右结束位置4]
===========================开始左排序[左开始位置：3][右结束位置3]
[开始对数组进行排序][左开始位置：3][右结束位置3]
左右下标相同，跳过
===========================开始右排序[左开始位置：4][右结束位置4]
[开始对数组进行排序][左开始位置：4][右结束位置4]
左右下标相同，跳过
***********************************开始合并[左开始位置：3][右结束位置4]
排序前[数组：[1, 5, 6, 3, 8, 4, 6, 9, 0, 2]][左开始位置：3][右结束位置4]
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[3, 8, 0, 0, 0, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 5, 6, 3, 8, 4, 6, 9, 0, 2]][左开始位置：3][右结束位置4]
***********************************开始合并[左开始位置：0][右结束位置4]
排序前[数组：[1, 5, 6, 3, 8, 4, 6, 9, 0, 2]][左开始位置：0][右结束位置4]
开始比较左右子序列,左序列取值更小
开始比较左右子序列,右序列取值更小
开始比较左右子序列,左序列取值更小
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[1, 3, 5, 6, 8, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：0][右结束位置4]
===========================开始右排序[左开始位置：5][右结束位置9]
[开始对数组进行排序][左开始位置：5][右结束位置9]
===========================开始左排序[左开始位置：5][右结束位置7]
[开始对数组进行排序][左开始位置：5][右结束位置7]
===========================开始左排序[左开始位置：5][右结束位置6]
[开始对数组进行排序][左开始位置：5][右结束位置6]
===========================开始左排序[左开始位置：5][右结束位置5]
[开始对数组进行排序][左开始位置：5][右结束位置5]
左右下标相同，跳过
===========================开始右排序[左开始位置：6][右结束位置6]
[开始对数组进行排序][左开始位置：6][右结束位置6]
左右下标相同，跳过
***********************************开始合并[左开始位置：5][右结束位置6]
排序前[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：5][右结束位置6]
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[4, 6, 0, 0, 0, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：5][右结束位置6]
===========================开始右排序[左开始位置：7][右结束位置7]
[开始对数组进行排序][左开始位置：7][右结束位置7]
左右下标相同，跳过
***********************************开始合并[左开始位置：5][右结束位置7]
排序前[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：5][右结束位置7]
开始比较左右子序列,左序列取值更小
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[4, 6, 9, 0, 0, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：5][右结束位置7]
===========================开始右排序[左开始位置：8][右结束位置9]
[开始对数组进行排序][左开始位置：8][右结束位置9]
===========================开始左排序[左开始位置：8][右结束位置8]
[开始对数组进行排序][左开始位置：8][右结束位置8]
左右下标相同，跳过
===========================开始右排序[左开始位置：9][右结束位置9]
[开始对数组进行排序][左开始位置：9][右结束位置9]
左右下标相同，跳过
***********************************开始合并[左开始位置：8][右结束位置9]
排序前[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：8][右结束位置9]
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[0, 2, 0, 0, 0, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：8][右结束位置9]
***********************************开始合并[左开始位置：5][右结束位置9]
排序前[数组：[1, 3, 5, 6, 8, 4, 6, 9, 0, 2]][左开始位置：5][右结束位置9]
开始比较左右子序列,右序列取值更小
开始比较左右子序列,右序列取值更小
开始依次放入左子序列
开始依次放入左子序列
开始依次放入左子序列
排序结束[子序列排序结果记入临时数组[0, 2, 4, 6, 9, 0, 0, 0, 0, 0]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[1, 3, 5, 6, 8, 0, 2, 4, 6, 9]][左开始位置：5][右结束位置9]
***********************************开始合并[左开始位置：0][右结束位置9]
排序前[数组：[1, 3, 5, 6, 8, 0, 2, 4, 6, 9]][左开始位置：0][右结束位置9]
开始比较左右子序列,右序列取值更小
开始比较左右子序列,左序列取值更小
开始比较左右子序列,右序列取值更小
开始比较左右子序列,左序列取值更小
开始比较左右子序列,右序列取值更小
开始比较左右子序列,左序列取值更小
开始比较左右子序列,左序列取值更小
开始比较左右子序列,右序列取值更小
开始比较左右子序列,左序列取值更小
开始依次放入右子序列
排序结束[子序列排序结果记入临时数组[0, 1, 2, 3, 4, 5, 6, 6, 8, 9]]
排序后[依次将临时数组的值放入原数组的子序列对应的位置[数组：[0, 1, 2, 3, 4, 5, 6, 6, 8, 9]][左开始位置：0][右结束位置9]
经过归并排序后：[0, 1, 2, 3, 4, 5, 6, 6, 8, 9]

注：
在此大概梳理一下在归并排序中的分治思想,先将原数列分成若干个子数列，在两两做合并比较（图画的有点丑~）