Рубрики

Java-программа для сортировки слиянием

Сортировка слиянием — это алгоритм « разделяй и властвуй» . Он разделяет входной массив на две половины, вызывает себя для двух половинок и затем объединяет две отсортированные половины. Функция merge () используется для объединения двух половинок. Слияние (arr, l, m, r) является ключевым процессом, который предполагает, что arr [l..m] и arr [m + 1..r] отсортированы и объединяет два отсортированных подмассива в один.

Джава

/ * Java-программа для сортировки слиянием * /

class MergeSort

{

    // Объединяет два подмассива arr [].

    // Первый подмассив - это arr [l..m]

    // Второй подмассив - это arr [m + 1..r]

    void merge(int arr[], int l, int m, int r)

    {

        // Находим размеры двух подмассивов для объединения

        int n1 = m - l + 1;

        int n2 = r - m;

  

        / * Создать временные массивы * /

        int L[] = new int [n1];

        int R[] = new int [n2];

  

        / * Копировать данные во временные массивы * /

        for (int i=0; i<n1; ++i)

            L[i] = arr[l + i];

        for (int j=0; j<n2; ++j)

            R[j] = arr[m + 1+ j];

  

  

        / * Объединить временные массивы * /

  

        // Начальные индексы первого и второго подмассивов

        int i = 0, j = 0;

  

        // Начальный индекс объединенного массива subarry

        int k = l;

        while (i < n1 && j < n2)

        {

            if (L[i] <= R[j])

            {

                arr[k] = L[i];

                i++;

            }

            else

            {

                arr[k] = R[j];

                j++;

            }

            k++;

        }

  

        / * Копировать оставшиеся элементы L [], если есть * /

        while (i < n1)

        {

            arr[k] = L[i];

            i++;

            k++;

        }

  

        / * Копировать оставшиеся элементы R [], если есть * /

        while (j < n2)

        {

            arr[k] = R[j];

            j++;

            k++;

        }

    }

  

    // Основная функция, которая сортирует arr [l..r] используя

    // merge ()

    void sort(int arr[], int l, int r)

    {

        if (l < r)

        {

            // Найти среднюю точку

            int m = (l+r)/2;

  

            // Сортировка первой и второй половин

            sort(arr, l, m);

            sort(arr , m+1, r);

  

            // Объединяем отсортированные половинки

            merge(arr, l, m, r);

        }

    }

  

    / * Утилита для печати массива размером n * /

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = {12, 11, 13, 5, 6, 7};

  

        System.out.println("Given Array");

        printArray(arr);

  

        MergeSort ob = new MergeSort();

        ob.sort(arr, 0, arr.length-1);

  

        System.out.println("\nSorted array");

        printArray(arr);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Пожалуйста, обратитесь к полной статье о сортировке слиянием для более подробной информации!

Рекомендуемые посты:

Java-программа для сортировки слиянием

0.00 (0%) 0 votes