Обзор
Метод сортировки слияния состоит в том, чтобы объединить две (или более двух) упорядоченных таблиц в новую упорядоченную таблицу, то есть разделить последовательность, которая будет сортирована на несколько последствий, каждая подпоследовательность упорядочена. Затем упорядоченные последующие последствия объединяются в общую упорядоченную последовательность.
Сортировка слияния реализуется с использованием рекурсии, которая принадлежит «деляции и победите». Целевой массив разделен на два от середины, а затем два массива отсортированы отдельно. После завершения сортировки два массива «объединены» вместе. Самая важная вещь в сортировке слияния - это процесс «слияния». В процессе слияния требуется дополнительное пространство, которое соответствует двум массивам, которые необходимо объединить.
Изображение воспроизведения:
шаг
Примените пространство так, чтобы его размер была суммой двух отсортированных последовательностей. Это пространство используется для хранения объединенной последовательности для установки двух указателей. Начальная позиция представляет собой начальную позицию двух отсортированных последовательностей, сравнивайте элементы, на которые указывает двумя указателями, выберите относительно небольшие элементы и поместите их в объединенное пространство и перемещают указатель в следующую позицию. Повторите шаг 3, пока указатель не достигнет конца последовательности. Скопируйте все оставшиеся элементы другой последовательности непосредственно до конца объединенной последовательности.
Необработанные данные:
3 5 2 6 2
Предварительным условием для слияния является разделение массивов, разделить их на два, а затем разделить их на два, и их нельзя снова разделить и объединить их.
Первый раунд разделен, индекс 2 ((0+4)/2 = 2) является средним
[3 5 2] [6 2]
Второй раунд разделения, отдельный [3 5 2]
[3 5] [2] [6 2]
Третий раунд разделения, отдельный [3 5]
[3] [5] [2] [6 2]
Слияние [3] [5]
[3 5] [2] [6 2]
Слияние [3 5] [2]
[2 3 5] [6 2]
Четвертый раунд разделен, разделяется [6 2]
[2 3 5] [6] [2]
Merge [6] [2]
[2 3 5] [2 6]
Слияние [2 3 5] [2 6]
[2 2 3 5 6]
Реализация кода (Java)
пакет com.coder4j.main.arithmetic.sorting; открытый класс Merge {private Static int mark = 0; / ** * Merge Sort * * @param Array * @param low * @param high * @return * / private static int [] sort (int [] массив, int low, int high) {int mid = (low + high) / 2; if (low <High) {mark ++; System.out.println («Throth of Gogne» + Mark + »последующее разделение, Get»); System.out.println ("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]"); // левая сортировка (массив, низкий, середина); // сортировка правого массива (массив, середина + 1, высокий); // слияние левого и правого (массив, низкий, средний, высокий); } return Array; } / ** * Merge The Array * * @param Array * @param low * @param mid * @param high * / private static void merge (int [] array, int low, int mid, int high) {System.out.println ("Merge: [ + low +"-" + mid +"] и [" + (mid + 1) +"-" +"] "]") ")") ") int [] temp = new int [High - low + 1]; int i = low; // левый указатель int j = mid + 1; // правый указатель int k = 0; // перемещать меньшее число в новый массив сначала while (i <= mid && j <= high) {if (array [i] <array [j]) {temp [k ++] = массив [i ++]; } else {temp [k ++] = array [j ++]; }} // Могут быть оставшиеся элементы в одном из двух массивов // Перемещать оставшееся число слева в массив, в то время как (i <= mid) {temp [k ++] = массив [i ++]; } // переместить оставшееся число справа в массив, пока (j <= High) {temp [k ++] = массив [j ++]; } // Перезаписать числа в новом массиве массива для (int m = 0; m <temp.length; m ++) {массив [m+low] = temp [m]; }} / ** * Merge Sort * * @param Array * @return * / public static int [] sort (int [] array) {return sort (array, 0, array.length - 1); } public static void main (string [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sorted = sort (массив); System.out.println («Окончательный результат»); для (int i: sorted) {System.out.print (i + ""); }}}Результаты результатов вывода теста:
Первое разделение выполняется, и выполняется [0-2] [3-4], и выполняется второе разделение, и выполняется [0-1] [2-2], и выполняется третье разделение, и [0-0] [1-1] слияние: [0-0] и [1-1] слияние [0-1] и [2-2, и Четвертые, и Четвертые, и Четвертые, и Четвертые, и Четвертые, и Четвертые [3-3] [4-4] Merge: [3-3] и [4-4] Merge: [0-2] и [3-4] Окончательный результат 2 2 2 3 5 6
После тестирования это согласуется с результатами в примере.