有数组[2, 1, -3, -15, 25, 16, 0, 8]如下:
现对该数组进行排序,使用归并排序算法。
先来讲解一下归并排序的思路,大概分为如下几个步骤:
OK,思路了解了,下面就用图示来演示一下各个步骤是怎么做的。
我们先把上面的数组进行第一次拆分:
拆分成了两部分,分别为[2, 1, -3, -15]和[25, 16, 0, 8]
这样的拆分不够小,我们继续进行拆分:
排序后的四个子数组为:
子数组排序后,就该进行最后一步了。
先将第一个子数组和第二个子数组进行归并,归并的步骤其实也很简单,就是将两个子数组的元素从左到右依次进行比较,按顺序进行存放即可。
这时候需要创建一个空数组,对结果集进行一个存放。首先对比1和-15,1比-15要大,所以先把-15放到结果数组中:
然后对比1和-3,1依然是大于-3,所以把-3放到结果数组中:
这样就归并成了两个子数组,然后再对这两个子数组进行进一步的归并操作,操作依然跟上面是一样的,一个一个对比,最终就归并成了如下结果:
下面来用代码实现一下归并排序:
@Test public void sortTest() { int[] nums = new int[]{2, 1, -3, -15, 25, 16, 0, 8}; int[] sortedArray = mergeSort(nums); System.out.println(Arrays.toString(sortedArray)); } private int[] mergeSort(int[] nums) { // 数组大小小于2,直接返回 if (nums.length < 2) { return nums; } // 数组大小等于2,排序并返回 if (nums.length == 2) { if (nums[0] > nums[1]) { swap(nums, 0, 1); } return nums; } // 数组拆分 int[] left = Arrays.copyOfRange(nums, 0, nums.length / 2); int[] right = Arrays.copyOfRange(nums, nums.length / 2, nums.length); // 递归归并 return merge(mergeSort(left), mergeSort(right)); } private int[] merge(int[] left, int[] right) { // 声明结果数组 int[] result = new int[left.length + right.length]; // 开始遍历,每次放入结果数组一个元素 for (int index = 0, i = 0, j = 0; index < result.length; index++) { // 如果左子数组已经归并完,直接放入右子数组 if (i >= left.length) { result[index] = right[j++]; // 如果右子数组已经归并完,直接放入左子数组 } else if (j >= right.length) { result[index] = left[i++]; // 如果两个子数组都没有归并完,比较大小并放入结果数组 } else if (left[i] < right[j]) { result[index] = left[i++]; }else{ result[index] = right[j++]; } } return result; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
这样就实现了一个简单的归并排序,看下执行结果:
其实这叫二路归并,另外还有多路归并,其实知道原理了,也不难实现,比如三路归并:
@Test public void sortTest() { int[] nums = new int[]{2, 1, -3, -15, 25, 16, 0, 8}; int[] sortedArray = mergeSort(nums); System.out.println(Arrays.toString(sortedArray)); } private int[] mergeSort(int[] nums) { // 数组大小小于2,直接返回 if (nums.length < 2) { return nums; } // 数组大小等于2,排序并返回 if (nums.length == 2) { if (nums[0] > nums[1]) { swap(nums, 0, 1); } return nums; } // 数组拆分 int[] left = Arrays.copyOfRange(nums, 0, nums.length / 3); int[] mid = Arrays.copyOfRange(nums, nums.length / 3, nums.length / 3 * 2); int[] right = Arrays.copyOfRange(nums, nums.length / 3 * 2, nums.length); // 递归归并 return merge(mergeSort(left), mergeSort(mid), mergeSort(right)); } private int[] merge(int[] left, int[] mid, int[] right) { // 声明结果数组 int[] result = new int[left.length + mid.length + right.length]; // 开始遍历,每次放入结果数组一个元素 for (int index = 0, i = 0, j = 0, k = 0; index < result.length; index++) { if (i >= left.length) { if (j >= mid.length) { result[index] = right[k++]; } else { if (mid[j] < right[k]) { result[index] = mid[j++]; } else { result[index] = right[k++]; } } } else if (j >= mid.length) { if (k >= right.length) { result[index] = left[i++]; } else { if (left[i] < right[k]) { result[index] = left[i++]; } else { result[index] = right[k++]; } } } else if (k >= right.length) { if (left[i] < mid[j]) { result[index] = left[i++]; } else { result[index] = mid[j++]; } } else { if (left[i] < mid[j]) { if (left[i] < right[k]) { result[index] = left[i++]; } else { result[index] = right[k++]; } } else if (left[i] >= mid[j]) { if (mid[j] < right[k]) { result[index] = mid[j++]; } else { result[index] = right[k++]; } } } } return result; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
道理是一样的,执行结果也是一样的:
本文地址:https://www.r22.cn/hlwzxwz/462.html