归并排序 基本思想 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。
思路
分阶段可以理解为就是递归拆分子序列的过程。
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤:
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package com.nanzx.sort;import java.util.Arrays;public class MergeSort { public static void main (String[] args) { int [] arr = { 8 , 4 , 5 , 7 , 1 , 3 , 6 , 2 }; mergeSort(arr, 0 , arr.length-1 ); System.out.println("归并排序后=" + Arrays.toString(arr)); } public static void mergeSort (int [] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2 ; mergeSort(arr, left, mid); mergeSort(arr, mid + 1 , right); merge(arr, left, mid, right); } } public static void merge (int [] arr, int left, int mid, int right) { int i = left; int j = mid + 1 ; int [] temp = new int [right - left + 1 ]; int t = 0 ; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } while (i <= mid) { temp[t++] = arr[i++]; } while (j <= right) { temp[t++] = arr[j++]; } System.out.println("left: " + left + " right:" + right + " t:" + t); for (int k = 0 ; k < t; k++) { arr[left++] = temp[k]; } } }
运行结果 left: 0 right:1 t:2 left: 2 right:3 t:2 left: 0 right:3 t:4 left: 4 right:5 t:2 left: 6 right:7 t:2 left: 4 right:7 t:4 left: 0 right:7 t:8 归并排序后=[1, 2, 3, 4, 5, 6, 7, 8]
对于代码中mergeSort方法的理解 1 2 3 4 5 6 7 8 9 10 11 12 public static void mergeSort (int [] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2 ; mergeSort(arr, left, mid); mergeSort(arr, mid + 1 , right); merge(arr, left, mid, right); } }
这个方法其实就是先一直分割左子列,分割到如图的第三列的 84 时,就不会再继续向左分割,不满足向左递归进行分解的条件,接着向右递归进行分解,发现条件也不满足,所以没有分割到如图的第四列(两条虚线紧夹着的位置),最后执行按序合并4和8的操作。回溯到8457,执行向右递归进行分解,分成57后也是不能在分解了,按序合并57。回溯到8457执行按序合并。
测试归并排序的速度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 package com.nanzx.sort;import java.text.SimpleDateFormat;import java.util.Date;public class MergeSort { public static void main (String[] args) { int [] arr = new int [8000000 ]; for (int i = 0 ; i < 8000000 ; i++) { arr[i] = (int ) (Math.random() * 8000000 ); } Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss" ); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); mergeSort(arr, 0 , arr.length - 1 ); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序后的时间是=" + date2Str); } public static void mergeSort (int [] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2 ; mergeSort(arr, left, mid); mergeSort(arr, mid + 1 , right); merge(arr, left, mid, right); } } public static void merge (int [] arr, int left, int mid, int right) { int i = left; int j = mid + 1 ; int [] temp = new int [right - left + 1 ]; int t = 0 ; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } while (i <= mid) { temp[t++] = arr[i++]; } while (j <= right) { temp[t++] = arr[j++]; } for (int k = 0 ; k < t; k++) { arr[left++] = temp[k]; } } }
排序前的时间是=2020-08-03 15:07:12
排序后的时间是=2020-08-03 15:07:14