Введение в алгоритм сортировки слиянием

Сортировка слиянием - это алгоритм сортировки, основанный на технике «разделяй и властвуй». Это один из самых эффективных алгоритмов сортировки.

В этой статье вы узнаете о работе алгоритма сортировки слиянием, алгоритме сортировки слиянием, его временная и пространственная сложность, а также ее реализация на различных языках программирования, таких как C ++, Python и JavaScript.

Как работает алгоритм сортировки слиянием?

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

Более эффективно эту концепцию можно пояснить на примере. Рассмотрим несортированный массив со следующими элементами: {16, 12, 15, 13, 19, 17, 11, 18}.

Здесь алгоритм сортировки слиянием делит массив на две половины, вызывает себя для двух половин, а затем объединяет две отсортированные половины.

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

Ниже представлен алгоритм сортировки слиянием:

MergeSort (arr [], leftIndex, rightIndex)
если leftIndex> = rightIndex
возвращаться
еще
Найдите средний индекс, который делит массив на две половины: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Вызовите mergeSort () для первой половины: 
Вызов mergeSort (arr, leftIndex, middleIndex)
Вызовите mergeSort () для второй половины:
Вызов mergeSort (arr, middleIndex + 1, rightIndex)
Объедините две половинки, отсортированные на шагах 2 и 3:
Вызов слияния (arr, leftIndex, middleIndex, rightIndex)

Связанный: Что такое рекурсия и как ее использовать?

Временная и пространственная сложность алгоритма сортировки слиянием

Алгоритм сортировки слиянием можно выразить в виде следующего рекуррентного соотношения:

Т (п) = 2Т (п / 2) + О (п)

После решения этого рекуррентного отношения с помощью теоремы мастера или метода повторяющегося дерева вы получите решение как O (n logn). Таким образом, временная сложность алгоритма сортировки слиянием равна O (n logn).

Лучшая временная сложность сортировки слиянием: O (n logn)

Средняя временная сложность сортировки слиянием: O (n logn)

Наихудшая временная сложность сортировки слиянием: O (n logn)

Связанный: Что такое нотация Big-O?

Сложность вспомогательного пространства алгоритма сортировки слиянием На) в виде п вспомогательное пространство требуется в реализации сортировки слиянием.

Реализация алгоритма сортировки слиянием в C ++

Ниже представлена ​​реализация алгоритма сортировки слиянием на C ++:

// C ++ реализация
// алгоритм сортировки слиянием
#включать 
используя пространство имен std;
// Эта функция объединяет два подмассива arr []
// Левый подмассив: arr [leftIndex..middleIndex]
// Правый подмассив: arr [middleIndex + 1..rightIndex]
пустое слияние (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - средний индекс;
// Создаем временные массивы
int L [leftSubarraySize], R [rightSubarraySize];
// Копирование данных во временные массивы L [] и R []
для (int i = 0; я L [i] = arr [leftIndex + i];
для (int j = 0; j R [j] = arr [средний индекс + 1 + j];
// Объединение временных массивов обратно в arr [leftIndex..rightIndex]
// Начальный индекс левого подмассива
int я = 0;
// Начальный индекс правого подмассива
int j = 0;
// Начальный индекс объединенного подмассива
int k = leftIndex;
в то время как (я {
если (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
еще
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Если в L [] остались какие-то элементы
// Копируем в arr []
в то время как (я {
arr [k] = L [i];
i ++;
k ++;
}
// Если в R [] остались какие-то элементы
// Копируем в arr []
в то время как (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
если (leftIndex> = rightIndex)
{
возвращаться;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
слияние (arr, leftIndex, middleIndex, rightIndex);
}
// Функция для печати элементов
// массива
void printArray (int arr [], int size)
{
для (int i = 0; я {
cout << arr [i] << "";
}
cout << endl;
}
// Код драйвера
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Несортированный массив:" << endl;
printArray (обр., размер);
mergeSort (обр., 0, размер - 1);
cout << "Отсортированный массив:" << endl;
printArray (обр., размер);
возврат 0;
}

Выход:

Несортированный массив:
16 12 15 13 19 17 11 18 
Отсортированный массив:
11 12 13 15 16 17 18 19

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

Ниже представлена ​​реализация алгоритма сортировки слиянием в JavaScript:

// JavaScript-реализация
// алгоритм сортировки слиянием
// Эта функция объединяет два подмассива arr []
// Левый подмассив: arr [leftIndex..middleIndex]
// Правый подмассив: arr [middleIndex + 1..rightIndex]
function merge (arr, leftIndex, middleIndex, rightIndex) {
пусть leftSubarraySize = middleIndex - leftIndex + 1;
пусть rightSubarraySize = rightIndex - middleIndex;
// Создаем временные массивы
var L = новый массив (leftSubarraySize);
var R = новый массив (rightSubarraySize);
// Копирование данных во временные массивы L [] и R []
для (пусть i = 0; яL [i] = arr [leftIndex + i];
}
для (пусть j = 0; jR [j] = arr [средний индекс + 1 + j];
}
// Объединение временных массивов обратно в arr [leftIndex..rightIndex]
// Начальный индекс левого подмассива
var i = 0;
// Начальный индекс правого подмассива
var j = 0;
// Начальный индекс объединенного подмассива
var k = leftIndex;
в то время как (я {
если (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
еще
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Если в L [] остались какие-то элементы
// Копируем в arr []
в то время как (я {
arr [k] = L [i];
i ++;
k ++;
}
// Если в R [] остались какие-то элементы
// Копируем в arr []
в то время как (j {
arr [k] = R [j];
j ++;
k ++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
возвращаться
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
слияние (arr, leftIndex, middleIndex, rightIndex);
}
// Функция для печати элементов
// массива
function printArray (arr, size) {
для (пусть i = 0; яdocument.write (arr [i] + "");
}
document.write ("
");
}
// Код драйвера:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("Несортированный массив:
");
printArray (обр., размер);
mergeSort (обр., 0, размер - 1);
document.write ("Отсортированный массив:
");
printArray (обр., размер);

Выход:

Несортированный массив:
16 12 15 13 19 17 11 18
Отсортированный массив:
11 12 13 15 16 17 18 19

Связанный: Динамическое программирование: примеры, общие проблемы и решения

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

Ниже представлена ​​реализация алгоритма сортировки слиянием в Python:

# Реализация Python
# алгоритм сортировки слиянием
def mergeSort (обр.):
если len (arr)> 1:
# Нахождение среднего индекса массива
middleIndex = len (arr) // 2
# Левая половина массива
L = arr [: средний индекс]
# Правая половина массива
R = arr [средний индекс:]
# Сортировка первой половины массива
mergeSort (L)
# Сортировка второй половины массива
mergeSort (R)
# Начальный индекс левого подмассива
я = 0
# Начальный индекс правого подмассива
j = 0
# Начальный индекс объединенного подмассива
к = 0
# Копировать данные во временные массивы L [] и R []
в то время как i если L [i] arr [k] = L [i]
я = я + 1
еще:
arr [k] = R [j]
j = j + 1
к = к + 1
# Проверяем, остались ли какие-то элементы
пока я arr [k] = L [i]
я = я + 1
к = к + 1
пока j arr [k] = R [j]
j = j + 1
к = к + 1
# Функция для печати элементов
# массива
def printArray (arr, размер):
для i в диапазоне (размер):
print (arr [i], end = "")
Распечатать()
# Код драйвера
arr = [16, 12, 15, 13, 19, 17, 11, 18]
размер = длина (об)
print ("Несортированный массив:")
printArray (обр., размер)
mergeSort (обр.)
print ("Отсортированный массив:")
printArray (обр., размер)

Выход:

Несортированный массив:
16 12 15 13 19 17 11 18
Отсортированный массив:
11 12 13 15 16 17 18 19

Понимание других алгоритмов сортировки

Сортировка - один из наиболее часто используемых алгоритмов программирования. Вы можете сортировать элементы на разных языках программирования, используя различные алгоритмы сортировки, такие как быстрая сортировка, пузырьковая сортировка, сортировка слиянием, сортировка вставкой и т. Д.

Пузырьковая сортировка - лучший выбор, если вы хотите узнать о простейшем алгоритме сортировки.

Введение в алгоритм пузырьковой сортировки

Алгоритм пузырьковой сортировки: отличное введение в сортировку массивов.

Читать далее

Об авторе