西安网站优化,织梦网站栏目调用,做网站找那家公司好,wordpress 后台模板今天来学习归并排序算法。分而治之归并算法的核心思想是分而治之#xff0c;就是将大问题转化为小问题#xff0c;在解决小问题的基础上#xff0c;再去解决大问题。将这句话套用到排序中#xff0c;就是将一个大的待排序区间分为小的待排序区间#xff0c;对小的排序区间…今天来学习归并排序算法。分而治之归并算法的核心思想是分而治之就是将大问题转化为小问题在解决小问题的基础上再去解决大问题。将这句话套用到排序中就是将一个大的待排序区间分为小的待排序区间对小的排序区间进行排序然后再去解决大区间的排序而对小区间进行排序的时候可以继续使用该方法将小的待排序区间分为小小的待排序区间... ...依次往复。最终将排序区间分到只有一个元素这个时候因为一个元素已经就是排好序的无需继续切分了然后我们再依照此结果去解决大区间的排序。假设我们现在有[53, 89, 32, 45, 67, 2, 32, 89, 65, 54]这么一个数组我们要对它进行归并排序(从小到大排序此文中均为从小到大排序)整体的过程如下图所示归并排序算法完整过程整个算法分为两大阶段分割阶段和归并阶段。分割阶段1. [53, 89, 32, 45, 67, 2, 32, 89, 65, 54]分为[53, 89, 32, 45, 67]和[2, 32, 89, 65, 54]。2. [53, 89, 32, 45, 67]分为[53, 89]和[32, 45, 67] [2, 32, 89, 65, 54]分为[2, 32]和[89, 65, 54]。4. ... ...5. 数组分割完毕所有小数组依次为[53][89] [32] [45][67][2][32][89][65][54]。归并阶段1. [53][89]归并为[53, 89][32] [45]归并为[32, 45][2]和[32]归并为[2, 32][65]和[54]归并为[54, 65](这一步中[67]和[89]没有归并因为在最后一步分割过程中它们被单独分开了)。2. [32, 45]和[67]归并为[32, 45, 67][89]和[54, 65]归并为[54, 65, 89]。3. [53, 89]和[32, 45, 67]归并为[32, 45, 53, 67, 89][2, 32]和[54, 65, 89]归并为[2, 32, 54, 65, 89]。4. [32, 45, 53, 67, 89]和[2, 32, 54, 65, 89]归并为[2, 32, 32, 45, 53, 54, 65, 67, 89, 89](其中两个32和两个89在归并的过程中保留它们的原始顺序)。整个分而治之的过程我们已经清楚了可还有一个问题没有解决就是具体应该怎么去归并呢即如何将两个排序子数组(或子区间)合并为大的排序好的数组(或区间)呢我们可以先举个简单的例子现在有[2]和[1]两个数组我们如何把它们合并为[1, 2]整个数组呢很简单我们首先会把这两个元素取出来对比一下取出2和1我们一对比发现1小于2 所以我们在结果数组中先放入1然后再放入2。可以发现我们就是将两个子数组中的元素取出来比较了一下哪个小就把哪个先放入结果数组中。从上面的例子中我们可以得到大概的思路就是针对两个有序的子数组(或子区间)我们可以从头依次取两个子数组(或子区间)的首元素(因为从小到大排序后首元素肯定最小)然后作对比把小的元素放入结果数组中并且这个元素在下次选取的时候剔除下一个元素也应用同样的方法得到放入结果数组中依次进行直到两个数组的元素都取完为止如果发现其中一个子数组(或子区间)率先取完就直接将另外一个子数组(或子区间)中剩下的元素全部放入结果数组中即可。具体步骤描述如下1. 判断两个子数组(或子区间)是否含有剩余元素如果都有剩余元素进入第2步如果只有一个有剩余元素进入第5步如果没有则退出。2. 取出左子数组(或左子区间)的首个元素和右子数组(或右子区间)的首个元素。3. 两个元素对比将小的元素放入结果数组并且从对应数组中剔除该元素。4. 回到第1步(上一步选中的元素已被剔除)。5. 将剩余元素直接全部放入结果数组中退出(因为元素全部移动完毕)。其中剔除这一步在代码实现中可看成索引的移动。上述这个过程我们取[53, 89]和[32, 45, 67]这两个子数组的合并来描述一下如图所示归并1. 取出左子数组中的首个元素53和右子数组中的首个元素32两个作对比发现32 53所以我们将32放入结果数组2. 取出左子数组中的首个元素53和右子数组中的首个元素45两个作对比发现45 53所以我们将45放入结果数组3. 取出左子数组中的首个元素53和右子数组中的首个元素67两个作对比发现53 67所以我们将53放入结果数组4. 取出左子数组中的首个元素89和右子数组中的首个元素67两个作对比发现67 89所以我们将67放入结果数组5. 此时我们发现只有左子数组存在元素所以直接将左子数组的剩下所有元素此时只有89放入结果数组6. 至此所有元素移动完毕退出。通过以上分析我们可以知道整个归并排序算法总体上分为一个整体的大逻辑(分而治之)和一个局部的小逻辑(归并)在大逻辑(分而治之将整个数组切分并在确认子数组有序后归并)的基础上结合使用小逻辑(归并将两个有序子数组归并为一个大的有序数组)即可实现对整个数组的排序。最终代码实现如下/** * 数组的归并排序算法 * * param nums 数组 * param lo 区间的lo索引(包含) * param hi 区间的hi索引(不包含) */public static void mergeSort(int[] nums, int lo, int hi) { // 数组为null则直接返回 if (nums null) { return; } // 索引检查 if (lo 0 || nums.length lo) { throw new IllegalArgumentException(lo索引必须大于0并且小于数组长度数组长度 nums.length); } if (hi 0 || nums.length hi) { throw new IllegalArgumentException(hi索引必须大于0并且小于等于数组长度数组长度 nums.length); } if (hi lo) { // lo索引必须小于hi索引(等于也不行因为区间是左闭右开如果等于区间内元素数量就为0了) throw new IllegalArgumentException(lo索引必须小于hi索引); } if (lo 1 hi) { // 区间元素个数最多为1 // 无需排序 return; } int mid (lo hi) / 2; // 对左子区间排序 mergeSort(nums, lo, mid); // 对右子区间排序 mergeSort(nums, mid, hi); // 对两个排序好的子区间归并得到一个整体有序的区间 merge(nums, lo, mid, hi);}public static void merge(int[] nums, int lo, int mid, int hi) { // 这里不用检查索引调用方已经决定了索引是有效的 // 结果区间和右子区间使用原有数组 // 左子区间使用临时数组(因为结果区间可能会覆盖左子区间的元素所以需要开辟新数组保存) int leftLen mid - lo; int[] left new int[leftLen]; System.arraycopy(nums, lo, left, 0, leftLen); // 左子区间索引 int leftIdx 0; // 右子区间索引 int rightIdx mid; // 结果区间索引 int resultIdx lo; while (true) { if (leftIdx leftLen rightIdx hi) { // 两个子区间都存在元素 // 取两个子区间的有效首元素对比 if (left[leftIdx] nums[rightIdx]) { // 左子区间首元素小于右子区间首元素 // 将左子区间首元素放到结果位置同时更新索引位置 nums[resultIdx] left[leftIdx]; } else { // 右子区间首元素小于左子区间首元素 // 将右子区间首元素放到结果位置同时更新索引位置 nums[resultIdx] nums[rightIdx]; } } else { if (leftIdx leftLen) { // 左子区间还有剩余元素 // 直接将左区间所有元素一起移动到结果位置 System.arraycopy(left, leftIdx, nums, resultIdx, leftLen - leftIdx); } else { // 右子区间还有剩余元素 // 因为经过上一次判断左子区间和右子区间只会有一个存在剩余元素 // 直接将右区间所有元素一起移动到结果位置 System.arraycopy(nums, rightIdx, nums, resultIdx, hi - rightIdx); } // 全部元素移动完毕退出 break; } }}测试代码如下List numList IntStream.range(0, 10).boxed().collect(Collectors.toList());for (int i 1; i 5; i) { System.out.println(第 i 次); Collections.shuffle(numList); int[] nums new int[numList.size()]; for (int j 0; j nums.length; j) { nums[j] numList.get(j); } System.out.println(排序前 Arrays.toString(nums)); mergeSort(nums, 0, numList.size()); System.out.println(排序后 Arrays.toString(nums));}运行结果如下第1次排序前[8, 4, 1, 6, 7, 0, 5, 9, 2, 3]排序后[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]第2次排序前[2, 5, 6, 7, 9, 4, 3, 1, 0, 8]排序后[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]第3次排序前[2, 0, 5, 6, 7, 3, 4, 9, 8, 1]排序后[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]第4次排序前[4, 0, 3, 8, 1, 5, 9, 7, 2, 6]排序后[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]第5次排序前[7, 9, 8, 2, 0, 5, 6, 3, 4, 1]排序后[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]测试代码中5次随机将数组打乱然后运行我们的归并排序算法均得到有序结果符合我们的预期。
