Алгоритм поиска и сортировки JavaScript: сортировка кучи

Последнее обновление 9 февраля 2019 08:36:36 (UTC / GMT +8 часов)

script1adsense2code

script1adsense3code

Алгоритм поиска и сортировки JavaScript: упражнение-3 с решением

Напишите программу на JavaScript для сортировки списка элементов, используя сортировку Heap.

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

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

Анимационные кредиты: RolandH

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

HTML-код:

<!DOCTYPE html>
  <html>
  <head>
  <meta charset="utf-8">
  <title>JavaScript program of Heap sort</title>
  </head>
  <body></body>
</html>

Код JavaScript:


  var array_length;
/* to create MAX  array */  
function heap_root(input, i) {
    var left = 2 * i + 1;
    var right = 2 * i + 2;
    var max = i;
    if (left < array_length && input[left] > input[max]) {
        max = left;
    }
    if (right < array_length && input[right] > input[max])     {
        max = right;
    }
    if (max != i) {
        swap(input, i, max);
        heap_root(input, max);
    }
}
function swap(input, index_A, index_B) {
    var temp = input[index_A];
    input[index_A] = input[index_B];
    input[index_B] = temp;
}
function heapSort(input) {
    
    array_length = input.length;
    for (var i = Math.floor(array_length / 2); i >= 0; i -= 1)      {
        heap_root(input, i);
      }
    for (i = input.length - 1; i > 0; i--) {
        swap(input, 0, i);
        array_length--;
      
      
        heap_root(input, 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 .

Улучшите этот пример решения и опубликуйте свой код через Disqus

Предыдущая: Напишите программу на JavaScript для сортировки списка элементов с помощью сортировки слиянием.
Далее: Напишите программу на JavaScript для сортировки списка элементов с использованием сортировки вставками.