【算法篇】*简单直观理解归并排序*（JAVA语言实现）

hello，大家好，我依旧是你们熟悉的槿凉。这几天跟C站的小伙伴们互动的那是一个热火朝天，然后我发的一个动态也是出现了热评，真的是非常感谢各路大佬给予我衷心的建议，有了大家的支持，对我自己的编程学习无疑是莫大的帮助哈！好了，废话不多说，今天我们就来说说这个归并排序算法！（先附上一张我的动态热评图叭 嘿嘿还是有点激动的）

定义：归并排序的基本思想是首先将a[0……n-1]看成n个长度为1的有序表，将相邻的k个有序子表成对归并，得到n/k个长度为k的有序子表，然后将这些有序子表继续归并，最后得到一个长度为n的有序表。

看完是不是有些懵啦! 好，没有关系，这里举个例子大家就看的比较清晰了。

 好了，这里了解到归并排序的用法我们来到程序中具体看一个例子：

这里我们定义一个数组arr[]，里面有八个元素：

package yinghang;

import java.util.Arrays;

public class margesort {

	public static void main(String[] args) {
	int arr[] = {1,2,3,4,5,6,7,8};

我们先设计一个合并的方法：（这里的temp数组相当于一个中转站，就是把排序好的数组元素放在里面 最后在赋值给原数组arr[]）

	//合并的方法
	public static void merge(int arr[],int left,int mid ,int right,int temp[]) {
		int i = left;//初始化i，左边有序序列的初始序列
		int j = mid+1;//初始化j，右边有序序列的初始序列
		int t = 0;//指向temp数组的当前序列
		

我们依次合并左右子表：

		//先把左边有序序列的数据按照规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完毕为止
		while(i<=mid && j<=right) {
			if(arr[i] <= arr[j]){
				temp[t]= arr[i];
				t++;
				i++;
			}else{
				temp[t] = arr[j];
				t++;
				j++;
			}

然后有的小伙伴就要问了，那如果数组里面的元素不是偶数的话，那多出来的元素怎么办？哎，这个问题问得好，那么我们继续还要设计一个方法来将剩余元素依次加到temp数组中：

//把有剩余数据的一边的数据依次全部填充到temp数组中
		while(i<=mid) {
			temp[t] = arr[i];
			t++;
			i++;
		}
		while(j<=right){
			temp[t] = arr[j];
			t++;
			j++;
		}

那么接下来就是分+合的方法，就是依次排序好左右子表 然后放到temp数组中去：

	//分+合的方法
	public static void mergesort(int arr[],int left,int right,int temp[]) {
		if(left

	int temp[] = new int[arr.length];//归并排序需要一个额外空间
	mergesort(arr,0,arr.length-1,temp);
	System.out.println("归并排序后="+Arrays.toString(arr));

import java.util.Arrays;

public class margesort {

	public static void main(String[] args) {
	int arr[] = {1,2,3,4,5,6,7,8};
	int temp[] = new int[arr.length];//归并排序需要一个额外空间
	mergesort(arr,0,arr.length-1,temp);
	System.out.println("归并排序后="+Arrays.toString(arr));
	}
	//分+合的方法
	public static void mergesort(int arr[],int left,int right,int temp[]) {
		if(left