2015-05-13
2709
Сортировка слиянием (англ. merge sort)[1] является простым, но эффективным алгоритмом сортировки, который также как и алгоритм быстрой сортировки построен по принципу «разделяй и властвуй», однако реализует его несколько по-другому. Массив делится пополам, левая и правая половина рекурсивно сортируется тем же методом слияния, затем отсортированные части объединяются в один отсортированный массив. В соответствии с алгоритмом деление продолжается до части массива, состоящего из одного элемента. Такой массив сразу является отсортированным, поэтому задача сводится к написанию метода, который выполняет слияния двух отсортированных частей массива в один.
Одним из способов слияния является выделение дополнительной памяти для вспомогательного буфера, равному по размеру общему количеств элементов в двух частях массива. Элементы последовательно перемещаются в этот буфер по одному за шаг. Причем на каждом шагу элементы двух частей сравниваются, и по результату сравнения в буфер помещается элемент либо с левого, либо с правого подмассива. Один из подмассивов во время слияния может закончиться раньше. В таком случае элементы другого подмассива, которые не были обработаны, дописываются в конец буфера, сохраняя имеющийся порядок. Результатом является упорядоченная последовательность, находящаяся в буфере.
|
|
|
Задача 6.7 Напишите рекурсивный метод сортировки слиянием целочисленного массива.
Объяснение: в программеиспользуются следующие методы:
mergeSort(int[] arr) – выполняет сортировку массива arr[], вызывая для этого метод mergeSort(int[] arr, int low, int high, int[] buff);
mergeSort(int[] arr, int low, int high, int[] buff) – выполняет сортировку массива arr[] от индекса low до индекса high. В качестве аргумента в метод передается вспомогательный буфер buff[]. Метод осуществляет рекурсивное деление массива пополам и вызов метода слияния merge().
merge(int[]arr, int low, int high, int mid, int[] buff) – метод выполняет слияние отсортированных частей массива: левой от идекса low до mid и правой от индекса mid+1 до индекса high.
Пример выполнения алгоритма сортировки слиянием массива {5, 0, -10, 9, 15, 100, -12, 3} иллюстрирует рис. 6.5.
public class MergeSort {
static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}
static void mergeSort(int[] arr, int low, int high, int[] buff){
//Выполняем разделение
if (low >= high) {
return;
}
int mid = (low + high)/2;
mergeSort(arr, low, mid, buff);
mergeSort(arr, mid+1, high, buff);
//Вызываем метод слияния
merge(arr,low, high, mid, buff);
}
static void merge(int[]arr, int low, int high, int mid, int[] buff)
{
int left = low, right = mid + 1;
//Выполняем слияние
for (int i = low; i <= high; i++) {
if (right>high||left<=mid && arr[left]<=arr[right])
{
buff[i] = arr[left++];
} else {
buff[i] = arr[right++];
}
}
//Копируем буфер в массив arr
for (int i = low; i <= high; i++) {
arr[i] = buff[i];
|
|
|
}
}
public static void main(String[]args) {
int[] a = {5,0,-10,9,15,100,-12,3};
mergeSort(a);
System.out.println(java.util.Arrays.toString(a));
}}
Результат:
|
[-12, -10, 0, 3, 5, 9, 15, 100]
Сортировка слиянием является одним из самых простых алгоритмов сортировки среди быстрых алгоритмов, который может быть эффективно использован для сортировки связанных списков. Недостаток алгоритма заключается в том, что он требует дополнительную память размером порядка n, и не гарантирует сохранение порядка элементов с одинаковыми значениями. Его временная сложность всегда пропорциональна 
.
Рис.6.6 – Демонстрация выполнения алгоритма сортировки слиянием
