Алгоритм поиска и сортировки JavaScript: упражнение 3 с решением
Напишите программу JavaScript для сортировки списка элементов с помощью сортировки кучи.
На компьютере наука, heapsort (изобретен Дж. Уильямсом Вильямсом в 1964 г.) — это алгоритм сортировки, основанный на сравнении. Heapsort можно рассматривать как улучшенную сортировку выбора: как и этот алгоритм, он делит входные данные на отсортированную и несортированную области и интерактивно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не поиска в линейном времени для поиска максимума. Хотя на практике на большинстве машин она несколько медленнее, чем хорошо реализованная быстрая сортировка, она имеет преимущество в виде более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort — это алгоритм на месте, но это не стабильная сортировка.
Запуск алгоритма heapsort, сортирующего массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой для иллюстрации кратко показана древовидная структура кучи.
Авторские права на анимацию: RolandH
Пример решения: —
HTML-код:
Программа JavaScript для сортировки кучи Код JavaScript:
var array_length;/* для создания массива MAX */function heap_root (input, i) {var left = 2 * i + 1; var right = 2 * я + 2; var max = i; если (левый ввод [макс]) {макс = левый; } если (правый ввод [макс]) {макс = право; } если (макс! = я) {своп (вход, я, макс); heap_root (ввод, макс); }} функция подкачки (ввод, индекс_A, индекс_B) {var temp = input [index_A]; ввод [index_A] = ввод [index_B]; input [index_B] = temp;} функция heapSort (input) {array_length = input.length; for (var i = Math.floor (array_length/2); i> = 0; i - = 1) {heap_root (вход, я); } for (i = input.length - 1; i> 0; i--) {swap (input, 0, i); array_length--; heap_root (ввод, 0); }} var arr = [3, 0, 2, 5, -1, 4, 1]; heapSort (arr); console.log (arr);
Пример вывода:
[- 1,0,1,2,3,4,5]
Блок-схема:
Живая демонстрация:
См. Упражнение 3 для алгоритма поиска и сортировки пера от w3resource (@ w3resource) на CodePen.
Назад: Написать программа на JavaScript для сортировки списка элементов с помощью сортировки слиянием.
Далее: Напишите программу на JavaScript для сортировки списка элементов с помощью сортировки вставкой.
