Упражнения на Java: алгоритм сортировки кучи

Алгоритм сортировки Java: упражнение 5 с решением

Напишите программу Java для сортировки массива заданных целых чисел с использованием алгоритма сортировки кучи.

На компьютере наука, heapsort (изобретенный Дж. Уильямсом Вильямсом в 1964 г.) — это алгоритм сортировки, основанный на сравнении. Кучную сортировку можно рассматривать как улучшенную сортировку выбора: как и этот алгоритм, он делит входные данные на отсортированную и несортированную область и интерактивно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не поиска в линейном времени для поиска максимума. Хотя на практике на большинстве машин она несколько медленнее, чем хорошо реализованная быстрая сортировка, она имеет преимущество в виде более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort — это алгоритм на месте, но это не стабильная сортировка.

Запуск алгоритма heapsort, сортирующего массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой вкратце для иллюстрации показана древовидная структура кучи.

Авторы анимации: RolandH

Псевдокод:

 //Ссылка: https://bit.ly/2DBQsFIfunction heapSort  (a, count) вводится: неупорядоченный массив a длины count (первое место a в порядке max-heap) heapify (a, count) end: = count - 1, а end> ​​0 do (поменять местами корень (максимальное значение)  кучи с последним элементом кучи) swap (a [end], a [0]) (уменьшить размер кучи, чтобы предыдущее максимальное значение оставалось на своем месте) end: = end - 1 (  поместите кучу обратно в порядке максимальной кучи) siftDown (a, 0, end)  
  функция heapify (a, count) is (start присваивается индекс  в a последнего родительского узла) start: = (count - 2)/2 while start ≥ 0 do (просеять узел в начале индекса в нужное место, чтобы все узлы ниже начального индекса располагались в порядке кучи) siftDown (  а, старт, счет-1) старт:  = start - 1 (после просеивания корня все узлы/элементы находятся в порядке кучи) function siftDown (a, start, end) is (end представляет предел того, насколько далеко от кучи нужно просеивать) root: = start while root *  2 + 1 ≤ end do (пока у корня есть хотя бы один дочерний элемент) child: = root * 2 + 1 (root * 2 + 1 указывает на левого дочернего элемента) (Если у дочернего элемента есть брат или сестра, а значение дочернего элемента меньше, чем  его родного брата ...) if child + 1 ≤ end и [child]  

Пример решения:

Код Java:

  открытый класс HeapSort {public static void heapSort (int [] a) {int count = a. length;//сначала разместите a в порядке max-heapheapify (a, count); int end = count - 1; while (end> 0) {//меняем местами корень (максимальное значение) кучи с//последним элементом  of the heapint tmp = a [end]; a [end] = a [0]; a [0] = tmp;//помещаем кучу обратно в max-heap ordersiftDown (a, 0, end - 1);// уменьшить размер кучи, чтобы предыдущее//максимальное значение оставалось на своем местеend -;}} public static void heapify (int [] a, int count) {//start присваивается индекс в a из  последний родительский узел int start = (count - 2)/2; //двоичная куча пока (start> = 0) {//отсеиваем узел в начале индекса в нужное место//так, чтобы все узлы ниже начального индекса были в куче//ordersiftDown (a, start, count - 1);  start -;}//после просеивания корня все узлы/элементы находятся в порядке кучи} public static void siftDown (int [] a, int start, int end) {//end представляет предел того, насколько далеко в куче  to siftint root = start; while ((root * 2 + 1)  

Пример вывода:

 Сортированный массив: -5 0 1 2 3 7  45 

Блок-схема:

Редактор кода Java:

Назад: Напишите программу на Java для сортировки массива заданных целых чисел с использованием алгоритма сортировки слиянием.
Далее: Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма сортировки выбора.

Оцените статью
nanomode.ru
Добавить комментарий