归并排序

---

目录

归并排序

归并图解

代码实现

图解排序【超详细】

运行测试

---

 

归并图解

归并的第一步是将数组进行拆分

 

然后进行排序

然后将一步一步排序

 

代码实现

我们分为两个函数：

1.递归

/** * 归并排序 * @param array 数组 * @param start 起始点 * @param end 结束点 */ public static int[] sortArray(int[] array,int start,int end){ int middle = (start+end)/2; if (start<end){ sortArray(array,middle+1,end); sortArray(array,start,middle); //归并排序 gunBing(array,start,middle,end); } return array; }

2.排序

/** * 归并 * @param array 数组 * @param start 起始点 * @param middle 中间点 * @param end 终点 */ public static void gunBing(int[] array,int start,int middle,int end){ int[] temp = new int[end-start+1]; int i = start ; int j = middle+1; int k = 0; while(i<=middle&&j<=end){ if (array[i]<array[j]){ temp[k++] = array[i++]; }else{ temp[k++] = array[j++]; } } //如果是奇数长度的数组，左半边会比右半边的长度大一 while (i<=middle){ temp[k++] = array[i++]; } while(j<=end){ temp[k++] = array[j++]; } for (int x = 0;x<temp.length;x++){ array[x+start] = temp[x]; } }

图解排序【超详细】

运行测试

我们做一个测试：

public class ExecuteMain { public static void main(String[] args) { int[] array1 = new int[]{5,4,3,1,2,6,9,7}; int[] array2 = new int[]{5,4,3,1,2,6}; sortArray(array1,0,array1.length-1); sortArray(array2,0,array2.length-1); for (int num:array1){ System.out.print(num+"\t"); } System.out.println(); for (int num:array2){ System.out.print(num+"\t"); } } }

输出

1 2 3 4 5 6 7 9 1 2 3 4 5 6 Process finished with exit code 0

可以看到已经成功地排序成功了