我正在尝试解决一个问题,在这个问题中,我将使用merge sort获得以下情况:
在n个元素的数组中
在一个数组中取最小的数,然后取最大的数,这样它们的减法(或者这些数之间的差异最大)
例如:
n=8个
arr{7,8,10,20,4,19,50,70}
我想买4和70,因为它们的差别是66
如果我得到的是最小和最大的数字,那真的没关系,我只关心它们减法的最大差别另外,第一个数字必须比第二个数字低,不允许70和4。
因为这个问题需要我修改合并排序代码,所以我在想:1)把所有的数字分成1个数组,2)把数组中的I数字与I+1数字进行比较,如果I数字是最低的,那么得到它们的差异,并继续在数组中的所有位置移动。
你怎么认为?另外,我在设置基本情况时遇到问题:请帮助!

最佳答案

Merge-sort的理念是将较小部分的结果合并为较大部分的结果。
在合并排序中,首先将2个元素(1个元素的2个数组)合并为一个2个元素的排序数组,然后将2个2个元素的2个排序数组合并为一个4个元素的排序数组(因为2个数组是排序的,所以只需遍历和比较,较小的元素总是以升序排列在两个数组中的第一位),然后合并2个排序的元素将4个元素的数组转换为8个元素的排序数组。
|||||||||
|已排序||||
|排序||
|已排序|
现在,您只需要找到最大和最小的元素,因此,您只需要在两个元素中找到最大和最小的元素比较2个元素数组中的2个最大元素并找出较大的元素,然后比较4个元素数组中的2个最大元素并找出较大的元素,以此类推(小面也一样。)
|||||||||
|萨尔||||
| SMLLST公司||
|只需要关心S&L|
换句话说,您不再对整个数组进行排序,而是找到最大和最小的结果并合并以获得最终答案。
顺便说一下,我觉得这有点像快速选择到快速排序。

10-01 17:59
查看更多