(兔C残篇)归并排序的代码实现和简单讲解

本文主要是介绍(兔C残篇)归并排序的代码实现和简单讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原理：
假设初始序列有N个记录，则可看成是N个有序的子序列，每个子序列的长度为1，然后两两归并，得到N分之2个长度为2或1的有序子序列。再两两归并。。。如此重复，直至得到一个长度为N的有序序列为止，这种排序方法称为两路归并排序。

下面开始代码实现

import java.util.Arrays;
public class ArrayValueSort{// 这里我们先进行归并的操作，然后在进行拆分的操作，分为两个demo进行public static void main(String[] args){int arr[] ={1,10,60,6,30,3,20,5,80,2,8,50,90,30,7,8,70,40,9,4};//这个数组，我们用于最后的归并排序的结果测试。//下面在定义一个数组，用于测试归并，将其定义为满足归并条件的数组int array[] = {1,3,6,8,    2,4,5,7};//左边内容和右边内容，单独有序//调用归并方法consoliDate(array,0,array.length /2 -1,array.length-1);System.out.println(Arrays.toString(array));}//定义实现归并的方法public static void consoliDate(int arr[],int startIndex, int createIndex, int endIndex){//1.定义临时数组，用于接收排序后的元素int tempArr[] =new int[endIndex - startIndex +1];//定义左边数组的起始索引int i = startIndex;//定义右边数组的起始索引int j = createIndex+1;//定义临时数组的起始索引int index =0;//2.开始比较两个数组的元素大小，然后往临时数组中填放//循环的条件，要设置好左边数组的满足条件，也要设置好右边数组的满足条件while(i <=createIndex && j <= endIndex){//如果左边数组的下标小于等于右边数组的起始索引//就将左边遍历的当前元素放到临时数组中if(arr[i]<=arr[j]){tempArr[index] = arr[i];i++;}else{tempArr[index] = arr[j];j++;}index++;}//这里处理剩余的元素//处理左边数组的剩余元素while(i <=createIndex){tempArr[index] = arr[i];i++;index++;}//处理右边数组的剩余元素while(j <= endIndex){tempArr[index] = arr[j];j++;index++;}//那做完了这些事，我们最后在将临时数组的元素，放到原数组中。for(int k =0; k < tempArr.length; k++){arr[k +startIndex] = tempArr[k]; }}
}

执行结果

玩归并算法一定要理清楚条件的设置，不然很容易会出现ArrayIndexOutOfBoundsException

上述完成了归并但是并没有进行拆分，下面我们来进行拆分，归并的算法其实就是一个分而治之的过程，先进行拆分，然后在进行归并，我们先完成了归并，下面开始拆分：

import java.util.Arrays;
public class ArrayValueSort{public static void main(String[] args){int array[] ={1,10,60,6,30,3,20,5,80,2,8,50,90,30,7,8,70,40,9,4};splitMethod(array,0,array.length-1);consoliDate(array,0,array.length /2 -1,array.length-1);System.out.println(Arrays.toString(array));}private static void splitMethod(int[] array, int start, int end) {//不断从中间进行拆除//计算中间索引int createIndex = (start+end)/2;//拆除条件：开始索引和结束索引重合为止if (start < end){//递归调用拆分的方法splitMethod(array,start,createIndex);splitMethod(array,createIndex+1,end);//调用归并的方法consoliDate(array,start,createIndex,end);}}//定义实现归并的方法public static void consoliDate(int arr[],int startIndex, int createIndex, int endIndex){//1.定义临时数组，用于接收排序后的元素int tempArr[] =new int[endIndex - startIndex +1];//定义左边数组的起始索引int i = startIndex;//定义右边数组的起始索引int j = createIndex+1;//定义临时数组的起始索引int index =0;//2.开始比较两个数组的元素大小，然后往临时数组中填放//循环的条件，要设置好左边数组的满足条件，也要设置好右边数组的满足条件while(i <=createIndex && j <= endIndex){//如果左边数组的下标小于等于右边数组的起始索引//就将左边遍历的当前元素放到临时数组中if(arr[i]<=arr[j]){tempArr[index] = arr[i];i++;}else{tempArr[index] = arr[j];j++;}index++;}//这里处理剩余的元素//处理左边数组的剩余元素while(i <=createIndex){tempArr[index] = arr[i];i++;index++;}//处理右边数组的剩余元素while(j <= endIndex){tempArr[index] = arr[j];j++;index++;}//那做完了这些事，我们最后在将临时数组的元素，放到原数组中。for(int k =0; k < tempArr.length; k++){arr[k +startIndex] = tempArr[k]; }}
}