java - 应用归并排序逻辑

Question

我正在尝试解决一个问题，我将使用合并排序来获得以下情况:在 n 个元素的数组中

获取数组中的最小数字，然后获取最大的数字，因此它们相减(或这些数字之间的差异最大)

例如:n = 8arr {7,8,10,20,4,19,50,70}我想得到 4 和 70，因为它们相差 66如果我得到最小和最大的数字真的不重要，我只关心它们减法的最大差异。此外，第一个数字必须小于第二个数字，不允许使用 70 和 4。

因为这道题需要我修改归并排序代码，所以我在想:1)把所有的数分成1的数组，2)比较数组中的第i个数和第i+1个数，如果第i个数最低然后得到他们的差异并继续移动数组中的所有位置。

你怎么看？我在设置基本情况时也遇到了问题:请帮忙!

Answer 1

合并排序的理念是将较小部分的结果合并成较大部分。

在合并排序中，首先将 2 个元素(1 个元素的 2 个数组)合并为 2 个元素的排序数组，然后将 2 个 2 个元素的排序数组合并为 4 个元素的排序数组(因为 2 个数组是排序后，只需要遍历比较，两个数组中较小的元素始终排在第一位)，然后将 2 个 4 个元素的排序数组合并为一个 8 个元素的排序数组。

|   |   |   |   |   |   |   |   ||sorted |       |       |       ||sorted         |               ||sorted                         |

现在，你只需要找到最大和最小的，因此，你只需要找到2个元素中的最大和最小。比较 2 个包含 2 个元素的数组中的 2 个最大元素并找到较大的元素，然后比较来自 2 个包含 4 个元素的数组中的 2 个最大元素并找到较大的元素，依此类推。 (小边也一样。)

|   |   |   |   |   |   |   |   ||S     L|       |       |       ||Smllst    Lrgst|               ||only need to care about S & L  |

换句话说，你不再对整个数组进行排序，而是找出最大和最小的结果并合并得到最终答案。

_{顺便说一句，我认为这有点像快速选择快速排序。}