当前位置:首页 > 数码 > 针对有序数组的策略-优化跳过合并操作 (针对有序数组的方法)

针对有序数组的策略-优化跳过合并操作 (针对有序数组的方法)

admin5个月前 (05-03)数码15

归并排序是一种经典的排序算法,它通过分治的思想将待排序的数组划分为较小的子数组,然后递归地对这些子数组进行排序,最后将它们合并起来得到最终的有序数组。

在标准的归并排序算法中,合并操作是必不可少的,因为它负责将两个已排序的子数组合并成一个有序的数组。当我们面对一个已经有序的数组时,合并操作实际上是多余的。因为已经有序的数组不需要再进行合并,它们已经满足了排序的要求。

优化跳过合并操作

优化策略

因此,我们可以通过判断数组是否有序来跳过合并操作,从而提高算法的效率。在归并排序算法中,我们可以通过增加一个判断条件来实现这个优化。当我们在递归地对子数组进行排序时,我们可以在每次递归调用 merge() 方法之前,先检查子数组是否已经有序。如果是的话,我们可以直接返回,不再执行合并操作。这样一来,我们就可以避免不必要的合并操作,从而提高算法的性能。

实现

```java public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr, 0, mid); int[] right = Arrays.copyOfRange(arr, mid, arr.length); mergeSort(left); mergeSort(right); // 检查子数组是否已经有序 if (left[left.length - 1] <= right[0]) { System.arraycopy(left, 0, arr,

阿包说算法之《排序》

排序的方法有很多,本文主要介绍三种:冒泡排序,快速排序,归并排序。 在很多算法中,都会用到递归算法,因此递归不再单独讲。 算法思路 冒泡排序的思想是最符合常人思维的,比如一个数组:3,6,8,2,1。 首先选择第一个数3,然后从后面的数开始遍历,如果比数组 第一个数 小,就交换位置,否则继续: 比如,第一次比较3和6,3小,继续,3和8比,继续,3和2比,2小,就交换3和2的位置,数组变成2,6,8,3,1,这时数组 第一个数 是2,2和1比,1小,交换2和1的位置,变成1,6,8,3,2,此时第一轮遍历结束,可以看到一轮遍历可以把最小的数选出。 第二次从第2个数开始遍历,与后面的数比较,就是6依次和8,3比,跟3换位置,然后3和2比,又换位置,次轮结束后1,2,8,6,3。 继续下一轮,直到遍历结束。 可见第一次把最小的数放到第一位,第二次把第二小的数放到第二位,第N次把第N小的数放到第N位。 最终输出 说明:冒泡排序的时间复杂度为O(N^2),冒泡排序写法可能不一定是跟上面的一样,但是思想是一致的 算法思路 快速排序法的思想是把数组的第一个数取出来作为分界点,让数组中小于他的数放在他左边,大于他的数放在他右边,比如 这组数字,选5为分界点,然后让34在5左边,97在5右边,变成 然后,对左右两部分34和97,分别继续重复上面的步骤,直到有序。 这里可以看出应该用到 递归 。 步骤如下,有一串数字3,6,8,2,7,首先把第一个数3取出来作为分界点,然后从最右边开始找小于3的数,7大于3跳过,继续看2,2小于3,就把2放到3的位置,2的位置空出来【2,6,8,,7】,再从左边开始,6大于3,就把6放到原来2的位置,6的位置空出来【2,,8,6,7】,再从右边8开始,8大于3跳过,下一个,是空了,则此轮结束,把3放到空位【2,3,8,6,7】。 然后对3左右两边的2和8,6,7分别按上面的步骤进行排序,就变成【2,3,6,7,8】 最终输出 说明:这种排序的方式是一种 分治 的思想,把大问题拆分成多个解法一样的小问题,这里是把大数组拆成前后2个解法一样的小数组,分成两部分的分治法又叫二分法,但是跟下面的二分法排序又不一样。 另外,快速排序代码会有多种不同的写法,但是思想是一致的,快速排序中有2个while,在极端情况下(比如数组是有序的,会遍历整个数组)的算法复杂度是O(N^2),一般情况下是O(NlogN),但实际上乱序的情况下,很快就能跳出while,所以被称为快速排序,此排序最实用,请读者牢记。 算法思路 归并排序思路是:将数组一分为二,再对分出来的2个子数组继续拆分,2分,拆分直到子数组只有一个数字,然后把所有的数字两两组合成有序小数组,最后合成一个完整数组,是典型的二分法,所以又叫做二分法排序 这里的思想是拆分后就变成有序数组(一个数字肯定有序),然后就是对有序数组的合并操作。 比如,拆分成836,52,继续拆分成8,3,6,5,2。 然后8和3组合成38, 38和6组合成368, 52组合成25,。 最后把368和25组合成。 最终输出 说明:归并排序用的是二分法,把数组分成2个子数组分别排序,实际上可以用三分法四分法,把数组分成3个子数组,4个子数组等都可以,读者可以自行思考如何使用三分法归并排序。 归并排序的时间复杂度是O(NlogN)

LeetCode题解:合并两个有序数组

给你两个按非递减排序的整数数组nums1和nums2,另外有两个整数m和n,分别表示nums1和nums2中的元素数目。 请你合并nums1和nums2,使合并后的数组同样按非递减顺序排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1的初始长度为m+n,其中前m个元素表示应合并的元素,后n个元素为0,应忽略,num2的长度为n。

输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] 解释: 需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。

复杂度分析

比较两个数组的元素大小,每次将比较的较大值放置到当前的最大索引的位置。如果一方提前放置完毕,那么剩下的都放置另一方的元素。

复杂度分析

免责声明:本文转载或采集自网络,版权归原作者所有。本网站刊发此文旨在传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及版权、内容等问题,请联系本网,我们将在第一时间删除。同时,本网站不对所刊发内容的准确性、真实性、完整性、及时性、原创性等进行保证,请读者仅作参考,并请自行核实相关内容。对于因使用或依赖本文内容所产生的任何直接或间接损失,本网站不承担任何责任。

标签: 数组