Рубрики

Java-программа для ShellSort

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

// Java-реализация ShellSort

class ShellSort {

    / * Утилита для печати массива размером 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();

    }

  

    / * функция для сортировки arr используя shellSort * /

    int sort(int arr[])

    {

        int n = arr.length;

  

        // Начинаем с большого разрыва, затем уменьшаем разрыв

        for (int gap = n / 2; gap > 0; gap /= 2) {

            // Делаем вставку с пробелом для этого размера зазора.

            // Первые элементы пробела a [0..gap-1] уже

            // в заданном порядке продолжаем добавлять еще один элемент

            // пока весь массив не отсортирован по пробелу

            for (int i = gap; i < n; i += 1) {

                // добавляем [i] к элементам, которые были пропущены

                // отсортировано, сохраните [i] в temp и сделайте дыру в

                // позиция i

                int temp = arr[i];

  

                // сдвигаем ранее отсортированные по гэпу элементы до

                // правильное местоположение для [i] найдено

                int j;

                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

                    arr[j] = arr[j - gap];

  

                // положить temp (оригинал a [i]) в правильное

                // место расположения

                arr[j] = temp;

            }

        }

        return 0;

    }

  

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

    public static void main(String args[])

    {

        int arr[] = { 12, 34, 54, 2, 3 };

        System.out.println("Array before sorting");

        printArray(arr);

  

        ShellSort ob = new ShellSort();

        ob.sort(arr);

  

        System.out.println("Array after sorting");

        printArray(arr);

    }

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

Выход:

Array before sorting
12 34 54 2 3 
Array after sorting
2 3 12 34 54

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

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

Java-программа для ShellSort

0.00 (0%) 0 votes