Java 中的归并排序

每个程序员都必须首先思考未来工作的方案/计划/架构，否则一切都会一团糟，完全无政府状态。与任何帖子一样，您最初需要一个计划，让我们开始吧。

• 1）让我们以初学者的归并排序为主题。
• 2）我们将为进一步的工作创建一个架构和计划。
• 3) 我们将研究并描述计划的所有部分。
• 4）让我们检查一下性能和质量。

• 2.1）什么是归并排序。
• 2.2) 可能签名的描述。
• 2.3）举个例子。
• 2.4) 使用示例描述 Java 中的实现。
• 2.5）任何额外的东西。

合并——Java中的合并排序

隐含着“分而治之”的原则。这个想法和意义是什么？

1. 排序。

   我们将数组分成几部分，直到它等于 1 个元素。每 1 个元素都已排序。

2. 合并。

   合并已排序的元素。
   基于两副牌的原理。我们将 2 副牌放在桌子上，牌值朝上，最低的牌放在第三堆牌中。最终，如果我们用完某一副牌中的牌，我们会将它们一张一张地移动到最终的牌组中。结果将是两个已排序数组的合并，一个新的已排序数组。

花费的时间是O(n log2 n)。排序被认为是相当快的。 简单说一下算法复杂度，如果有人需要的话， 你经常可以看到这样的函数：

Sort(A, p, q);
Merge(A, p, q, r);

这是同样的事情，只是与索引相关。其中的变量有：

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

如果不描述这些变量，那么要求自己制作这样一个函数的人就不知道自己想要什么。你必须在谷歌上搜索才能找到它是什么，也许你会找到它。让我们举一个排序的例子。有一个数组{6, 1, 3, 5, 2, 4, 7, 8}，如果它的长度大于1，那么我们将它分成两部分，得到左部分{6, 1, 3, 5}和右部分{2, 4, 7, 8}。我们继续进行分成2部分的动作，直到其长度大于1。这样，我们就得到了一堆长度为1个元素的数组，即：{6} {1} {3} {5} {2} {4} {7} {8}。Java 中的实现是这样的：

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

接下来，您需要将这些数组合并为 1。这是如何完成的？为了避免多次遍历每个数组，让我们输入每个数组的位置索引。然后我们将循环一次，循环的长度等于这两个数组之和的长度。取第一个数组和第二个数组，并取第一个元素，比较第一个数组中的元素号 1和第二个数组中的元素号 1？较小的一个放入结果数组中。这里重要的是，如果我们从第一个数组中取出一个元素，那么当循环通过时，它应该引用第一个数组的第二个元素和第二个数组的第一个元素。为此，您需要将第二个数组的索引增加 +1，并在检查时从循环数中减去它，与第一个数组类似。清楚为什么要这样做吗？或者根本就什么都不清楚？:-) 例如，有 2 个数组： {1}{4}{8}and{3}{6}{7} 并且有一个循环：

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

在循环的第一遍中，事实证明arrayC[1] = {1}：我们从第一个数组中获取了这个元素。然后，当进行第二个循环时，我们必须已经比较元素{4}和{3}，但为了做到这一点，我们需要考虑两个数组的位置索引和偏移量，为此我们输入它们。

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

但这还不是全部，您需要考虑到某些数组可能会提前结束。例如，有3个数组： {1}{3}{5}并且{6}{7}{9} 第一个数组将在第二个数组到达之前结束，为此您需要输入检查，原则上合并功能已准备就绪。

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

这种排序最难的就是递归过渡的原理。那些。我们把左边扔进递归，直到它能被2整除，然后再把它展开回来，用文字来说，这是非常复杂和混乱的，但是当你尝试想象时，如果还不清楚，那就一团糟了。让我们看一下数组：{2}{1}{4}{3}。第一次排序递归会将其分成两部分，然后对元素2-1再次运行该函数，然后再次对元素2和1运行该函数，依次返回它们，因此它们将首先进入合并函数，然后1-2会出现out ，然后递归将返回并将4-3放入合并中，然后是4和3，之后合并将返回3-4，只有这样递归才会再次展开，并且1-2和3-4将是包含在合并中，排序后的数组将返回1-2-3-4。好了，就是这样，排序由两个函数组成。

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

如果你写下某种 main，你会得到类似的东西：

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

对我来说，这次排序完全失败了，有一百万个问题，但没有答案，我翻遍了整个互联网，重新阅读，观看了一堆视频，但一如既往，我只能自己找到答案。只有当我开始编写一个与到处闪烁的解决方案完全不同的解决方案时）但最终结果与所有其他解决方案相似）））排序实际上是最简单的，主要是在操作中以交互方式呈现它，并且如果你掌握了窍门，一切都会就位，我会制作一个视频））））到目前为止，这就是我已经受够了的：合并排序 合并排序 最重要的是始终制定计划开始。在开始做任何事情之前最好先等一下并思考一下。这可能需要更多时间，但理解和解决方案将会出现，而不是必须重写几次并想出拐杖。感谢大家抽出宝贵的时间，祝你好运和好心情。）PS：非常欢迎批评，好的和坏的，以及问题。）））