java 归并排序
最近看了个讲解归并排序的视频,是用C语言实现的。我想用java再实现一遍,加深印象,相当于做个笔记。
感觉这个系列的视频做得很好,讲得非常详细,有机会我会逐一实现视频中的代码。
参考:http://www.bilibili.com/video/av9982752/
一、实现过程
(1)使用分治的思想,把大的数组拆分成两个较小的数组
MergeSort.java
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 |
package com.test.Sort; public class MergeSort { public static void merge(int[] arr, int l, int m, int r) { int left_size = m - l; int right_size = r - m + 1; int[] left = new int[left_size]; int[] right = new int[right_size]; for (int i = l; i < m; i++) { left[i - l] = arr[i]; } for (int i = m; i <= r; i++) { right[i - m] = arr[i]; } for (int i = 0; i < left.length; i++) { System.out.print(left[i] + " "); } System.out.println(); for (int i = 0; i < right.length; i++) { System.out.print(right[i] + " "); } } public static void main(String[] args) { int[] arr = new int[] { 2, 8, 9, 10, 4, 5, 6, 7 }; int l = 0; int r = 7; int m = 4; merge(arr, l, m, r); } } |
运行结果为:
1 2 |
2 8 9 10 4 5 6 7 |
至此,可以根据l、m、r调整两个较小的数组。
通过两个较小的数组的相互比较,可以得到排序结果。
(2)两个数组中的元素相互比较,进行初步排序
MergeSort.java
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 75 76 |
package com.test.Sort; public class MergeSort { public static void merge(int[] arr, int l, int m, int r) { int left_size = m - l; int right_size = r - m + 1; int[] left = new int[left_size]; int[] right = new int[right_size]; for (int i = l; i < m; i++) { left[i - l] = arr[i]; } for (int i = m; i <= r; i++) { right[i - m] = arr[i]; } int i = 0, j = 0, k = l; while (i < left_size && j < right_size) { if (left[i] <= right[j]) { arr[k] = left[i]; i++; k++; } else { arr[k] = right[j]; j++; k++; } } while (i < left_size) { arr[k] = left[i]; i++; k++; } while (j < right_size) { arr[k] = right[j]; j++; k++; } } public static void main(String[] args) { int[] arr = new int[] { 2, 8, 9, 10, 4, 5, 6, 7 }; int l = 0; int r = 7; int m = 4; merge(arr, l, m, r); for (int i : arr) { System.out.print(i + " "); } } } |
运行结果为:
1 |
2 4 5 6 7 8 9 10 |
可喜可贺,归并排序已经搞定了!
有人会说:“你这完全就是诈和啊!你给的数组{ 2, 8, 9, 10, 4, 5, 6, 7 }是特殊情况,分成两个较小数组时,刚好就是有序的!”
没错,如果把数组改成乱序的,比如{ 5, 4, 8, 7, 9, 6, 2, 10 },结果就变成了:
1 |
5 4 8 7 9 6 2 10 |
这说明程序依然是不完整的。那么接下来怎么办?
(3)使用递归,改进排序
我的思路是这样的:
首先要知道,我们无法保证某个数组中的元素是有序的。所以我们把数组拆开,得到更小的数组,做归并排序。
拆开后的数组还是不能保证有序,那么我们就继续拆开,得到更小的数组,再做归并排序。
如果把原始数组不断的拆开,不断地做归并排序,最后可以得到很多非常小的数组。
当然,拆分是有极限的。拆分到最后,如果数组中只有一个元素,当然无法继续拆分下去,在此同时,我们也能保证此处的元素是有序的(容量为2的数组拆分成两个容量为1的小数组,两个数组中唯一的元素进行大小比较,结果绝对是有序的)。
所以,我们要做的就是写个递归,不断地拆分数组,做归并排序,直到所有元素都有序为止。
那么问题来了,既然要递归,我们什么时候停下来?
当一个数组不能再拆分了,就可以停下来了(只有一个元素,无法做拆分比较)。
MergeSort.java
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
package com.test.Sort; public class MergeSort { public static void merge(int[] arr, int l, int m, int r) { int left_size = m - l; int right_size = r - m + 1; int[] left = new int[left_size]; int[] right = new int[right_size]; for (int i = l; i < m; i++) { left[i - l] = arr[i]; } for (int i = m; i <= r; i++) { right[i - m] = arr[i]; } int i = 0, j = 0, k = l; while (i < left_size && j < right_size) { if (left[i] <= right[j]) { arr[k] = left[i]; i++; k++; } else { arr[k] = right[j]; j++; k++; } } while (i < left_size) { arr[k] = left[i]; i++; k++; } while (j < right_size) { arr[k] = right[j]; j++; k++; } } public static void mergeSort(int[] arr, int l, int r) { if (l == r) { // 当l = r,数组无法再细分下去了,已经是有序的,直接退出 return; } else { int m = (l + r) / 2; mergeSort(arr, l, m); // 左半边递归 mergeSort(arr, m + 1, r); // 右半边递归 merge(arr, l, m + 1, r); // 做一次归并排序 } } public static void main(String[] args) { int[] arr = new int[] { 5, 4, 8, 7, 9, 6, 2, 10 }; int l = 0; int r = 7; mergeSort(arr, l, r); for (int i : arr) { System.out.print(i + " "); } } } |
结果为:
1 |
2 4 5 6 7 8 9 10 |
数次递归后,可以保证数据是有序的。
二、总结
从宏观上看不一定好理解,所以我推荐去看视频,讲得很清楚。