Алгоритм сортировки слиянием на Java

Описание алгоритма:

Сортируемый массив разбивается на две части примерно одинакового размера.
Каждая из получившихся частей сортируется отдельно.
Два получившихся упорядоченных массива соединяются в один. При этом наименьший из первых элементов двух массивов записывается в результирующий массив, и эта операция повторяется, пока не закончатся элементы в этих двух массивах.

Реализуем этот алгоритм на Java.

Внимание! Не следует писать алгоритмы сортировки самостоятельно для реальных приложений. Нужно использовать готовые алгоритмы для коллекций и методы из java.util.Arrays.

Итак, моя реализация сортировки слиянием на Java:

import java.util.Arrays;

/**
 * Реализация сортировки слиянием на Java
 * @see https://urvanov.ru
 *
 */
public class Main {
    public static void main(String[] args) {
        int[] array1 = { 8, 0, -3, 5, 6, 9, 8, -4, 2, -99, 43 };
        int[] result = mergesort(array1);
        System.out.println(Arrays.toString(result));
    }

    public static int[] mergesort(int[] array1) {
        int[] buffer1 = Arrays.copyOf(array1, array1.length);
        int[] buffer2 = new int[array1.length];
        int[] result = mergesortInner(buffer1, buffer2, 0, array1.length);
        return result;
    }

    /**
     * 
     * @param buffer1 Массив для сортировки.
     * @param buffer2 Буфер. Размер должен быть равен размеру buffer1.
     * @param startIndex Начальный индекс в buffer1 для сортировки.
     * @param endIndex Конечный индекс в buffer1 для сортировки.
     * @return
     */
    public static int[] mergesortInner(int[] buffer1, int[] buffer2,
            int startIndex, int endIndex) {
        if (startIndex >= endIndex - 1) {
            return buffer1;
        }
        
        // уже отсортирован.
        int middle = startIndex + (endIndex - startIndex) / 2;
        int[] sorted1 = mergesortInner(buffer1, buffer2, startIndex, middle);
        int[] sorted2 = mergesortInner(buffer1, buffer2, middle, endIndex);
        
        // Слияние
        int index1 = startIndex;
        int index2 = middle;
        int destIndex = startIndex;
        int[] result = sorted1 == buffer1 ? buffer2 : buffer1;
        while (index1 < middle && index2 < endIndex) {
            result[destIndex++] = sorted1[index1] < sorted2[index2]
                    ? sorted1[index1++] : sorted2[index2++];
        }
        while (index1 < middle) {
            result[destIndex++] = sorted1[index1++];
        }
        while (index2 < endIndex) {
            result[destIndex++] = sorted2[index2++];
        }
        return result;
    }
}

import java.util.Arrays;

/**

* Реализация сортировки слиянием на Java

* @see https://urvanov.ru

public class Main {

public static void main(String[] args) {

int[] array1 = { 8, 0, -3, 5, 6, 9, 8, -4, 2, -99, 43 };

int[] result = mergesort(array1);

System.out.println(Arrays.toString(result));

}

public static int[] mergesort(int[] array1) {

int[] buffer1 = Arrays.copyOf(array1, array1.length);

int[] buffer2 = new int[array1.length];

int[] result = mergesortInner(buffer1, buffer2, 0, array1.length);

return result;

}

/**

* @param buffer1 Массив для сортировки.

* @param buffer2 Буфер. Размер должен быть равен размеру buffer1.

* @param startIndex Начальный индекс в buffer1 для сортировки.

* @param endIndex Конечный индекс в buffer1 для сортировки.

* @return

public static int[] mergesortInner(int[] buffer1, int[] buffer2,

int startIndex, int endIndex) {

if (startIndex >= endIndex - 1) {

return buffer1;

}

// уже отсортирован.

int middle = startIndex + (endIndex - startIndex) / 2;

int[] sorted1 = mergesortInner(buffer1, buffer2, startIndex, middle);

int[] sorted2 = mergesortInner(buffer1, buffer2, middle, endIndex);

// Слияние

int index1 = startIndex;

int index2 = middle;

int destIndex = startIndex;

int[] result = sorted1 == buffer1 ? buffer2 : buffer1;

while (index1 < middle && index2 < endIndex) {

result[destIndex++] = sorted1[index1] < sorted2[index2]

? sorted1[index1++] : sorted2[index2++];

}

while (index1 < middle) {

result[destIndex++] = sorted1[index1++];

}

while (index2 < endIndex) {

result[destIndex++] = sorted2[index2++];

}

return result;

}

Достоинства:

Быстрый. Примерно O(n log n) операций.
Можно использовать на связанных списках.
Можно сделать реализацию, использующую параллельные потоки.
Сохраняет порядок равных элементов (устойчивая)

Недостатки:

На почти отсортированных массивах работает также, как и на неотсортированных.
Нужна дополнительная память для буфера.

Вам также может быть интересна быстрая сортировка и сортировка вставками.

Пн	Вт	Ср	Чт	Пт	Сб	Вс
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Алгоритм сортировки слиянием на Java

Алгоритм сортировки слиянием на Java: 2 комментария

Добавить комментарий Отменить ответ