Алгоритм сортировки слиянием (с кодом на Python, Java, JavaScript, PHP, C++)

Введение

Merge sort - самый популярный алгоритм сортировки, основанный на принципе алгоритма "разделяй и властвуй".

Хотя существует множество алгоритмов сортировки, merge-sort доказал, что его временная сложность составляет O(аналог n). И в некоторых случаях он имеет лучшую временную сложность, чем его конкурент Quick sort.

Алгоритм сортировки слиянием использует технику "Разделяй и властвуй", чтобы сначала разделить массив на все его элементы и начать сравнивать два соседних массива и объединять их в один массив на основе порядка. Он следует той же схеме для следующих двух соседних элементов и так далее. Этот процесс продолжается до тех пор, пока не останется только один единственный массив, и это будет отсортированный массив.

Визуализацию сортировки слияния можно посмотреть ниже

Давайте посмотрим на реализацию кода

Merge Sort Python

def mergeSort(array):
    if len(array) <= 1: return
    mid = len(array)//2
    left = array[:mid]
    right = array[mid:]

    mergeSort(left)
    mergeSort(right)

    i = j = k = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
    
    while i < len(left):
        array[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        array[k] = right[j]
        j += 1
        k += 1

x = [8, 1, 5, 7, 9, 3, 2, 4, 6]

print(x)

mergeSort(x)

print(x)

Вы можете использовать этот онлайн-компилятор для выполнения этого кода.

Merge Sort JavaScript

function mergeSort(array){
    if (array.length <= 1) return;
    let mid = parseInt(array.length/2)
    let left = array.slice(0,mid)
    let right = array.slice(mid)

    mergeSort(left)
    mergeSort(right)

    let i = 0, j = 0,  k = 0;

    while (i < left.length && j < right.length){
        if (left[i] < right[j]){
            array[k] = left[i]
            i += 1
        }
        else{
            array[k] = right[j]
            j += 1
        }
        k += 1
    }
    
    while (i < left.length){
        array[k] = left[i]
        i += 1
        k += 1
    }
    while (j < right.length){
        array[k] = right[j]
        j += 1
        k += 1
    }
}

let x = [8, 1, 5, 7, 9, 3, 2, 4, 6]

console.info(x)

mergeSort(x)

console.info(x)

Вы можете использовать этот онлайн-компилятор для выполнения этого кода.

Merge Sort Java

class Sorting {
    public static void mergeSort(int[] arr) {
        if (arr.length > 1) {
            int mid = (int) arr.length / 2;
            int[] left = new int[mid];
            int[] right = new int[arr.length - mid];

            for (int i = 0; i < mid; i++) {
                left[i] = arr[i];
            }

            for (int i = 0; i < arr.length - mid; i++) {
                right[i] = arr[i + mid];
            }

            mergeSort(left);
            mergeSort(right);

            int i = 0, j = 0, k = 0;

            while (i < left.length && j < right.length) {
                if (left[i] < right[j]) {
                    arr[k] = left[i];
                    i++;
                } else {
                    arr[k] = right[j];
                    j++;
                }
                k++;
            }

            while (i < left.length) {
                arr[k] = left[i];
                k++;
                i++;
            }
            while (j < right.length) {
                arr[k] = right[j];
                k++;
                j++;
            }
        }
    }

    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i == arr.length - 1)
                System.out.println(arr[i] + "]");
            else
                System.out.print(arr[i] + ", ");
        }
    }

    public static void main(String[] args) {
        int[] x = { 8, 1, 5, 7, 9, 3, 2, 4, 6 };
        printArray(x);
        mergeSort(x);
        printArray(x);
    }
}

Вы можете использовать этот онлайн-компилятор для выполнения этого кода.

Сортировка слиянием C++

#include <iostream>

void mergeSort(int arr[], int size) {
    if (size > 1) {
        int middle = (int) size / 2;
        int left[middle];
        int right[size - middle];

        for (int i = 0; i < middle; i++) {
            left[i] = arr[i];
        }

        for (int i = 0; i < size - middle; i++) {
            right[i] = arr[i + middle];
        }

        mergeSort(left, middle);
        mergeSort(right, size - middle);

        int i = 0, j = 0, k = 0;

        while (i < middle && j < size - middle) {
            if (left[i] < right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < middle) {
            arr[k] = left[i];
            k++;
            i++;
        }
        while (j < size - middle) {
            arr[k] = right[j];
            k++;
            j++;
        }
    }
}

void printArray(int arr[], int size) {
    std::cout << "[";
    for (int i = 0; i < size; i++) {
        if (i == size - 1)
            std::cout << arr[i] << "]" << std::endl;
        else
            std::cout << arr[i] << ", ";
    }
}

int main() {
    int x[] = { 8, 1, 5, 7, 9, 3, 2, 4, 6 };
    int size = sizeof(x) / sizeof(x[0]);
    printArray(x, size);
    mergeSort(x, size);
    printArray(x, size);
    return 0;
}

Вы можете использовать этот онлайн-компилятор для выполнения этого кода.

Merge Sort PHP

<?php
function mergeSort(&$array)
{
    if (count($array) <= 1) return;
    $mid = (int) (count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);

    mergeSort($left);
    mergeSort($right);

    $i = 0;
    $j = 0;
    $k = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $array[$k] = $left[$i];
            $i += 1;
        } else {
            $array[$k] = $right[$j];
            $j += 1;
        }
        $k += 1;
    }

    while ($i < count($left)) {
        $array[$k] = $left[$i];
        $i += 1;
        $k += 1;
    }
    while ($j < count($right)) {
        $array[$k] = $right[$j];
        $j += 1;
        $k += 1;
    }
}

$x = array(8, 1, 5, 7, 9, 3, 2, 4, 6);
echo json_encode($x) . "\n";
mergeSort($x);
echo json_encode($x);
?>

Вы можете использовать этот онлайн-компилятор для выполнения этого кода.

Преимущества

• Merge sort имеет временную сложность O(n log n), что означает, что он относительно эффективен для сортировки больших наборов данных.
• Merge sort - это стабильная сортировка, что означает, что порядок элементов с одинаковыми значениями сохраняется во время сортировки.
• Она проста в реализации, что делает ее хорошим выбором для многих приложений

Недостатки

• Медленнее по сравнению с другими алгоритмами сортировки для небольших задач. Хотя он эффективен для больших массивов данных, это не лучший выбор для малых массивов данных.
• Он проходит весь процесс, даже если массив отсортирован.

Конец статьи. Спасибо за прочтение!

Загляните на мой сайт, чтобы прочитать больше подобных статей!