Реализация алгоритма Heapsort на JavaScript

JavaScriptJavaScriptBeginner
Практиковаться сейчас

This tutorial is from open-source community. Access the source code

💡 Этот учебник переведен с английского с помощью ИИ. Чтобы просмотреть оригинал, вы можете перейти на английский оригинал

Введение

В этом лабе мы исследуем реализацию алгоритма heapsort на JavaScript. Heapsort - это алгоритм сортировки, основанный на сравнении, который работает путём разделения массива на отсортированную и неотсортированную области, и итеративного уменьшения неотсортированной области путём извлечения наибольшего элемента и перемещения его в отсортированную область. С помощью этого лабара вы получите более глубокое понимание того, как работает алгоритм heapsort и как реализовать его с использованием рекурсии и замыканий в JavaScript.


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("JavaScript")) -.-> javascript/BasicConceptsGroup(["Basic Concepts"]) javascript(("JavaScript")) -.-> javascript/AdvancedConceptsGroup(["Advanced Concepts"]) javascript/BasicConceptsGroup -.-> javascript/variables("Variables") javascript/BasicConceptsGroup -.-> javascript/data_types("Data Types") javascript/BasicConceptsGroup -.-> javascript/arith_ops("Arithmetic Operators") javascript/BasicConceptsGroup -.-> javascript/comp_ops("Comparison Operators") javascript/BasicConceptsGroup -.-> javascript/cond_stmts("Conditional Statements") javascript/BasicConceptsGroup -.-> javascript/loops("Loops") javascript/BasicConceptsGroup -.-> javascript/array_methods("Array Methods") javascript/AdvancedConceptsGroup -.-> javascript/spread_rest("Spread and Rest Operators") subgraph Lab Skills javascript/variables -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/data_types -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/arith_ops -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/comp_ops -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/cond_stmts -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/loops -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/array_methods -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} javascript/spread_rest -.-> lab-28374{{"Реализация алгоритма Heapsort на JavaScript"}} end

Алгоритм Heap Sort

Для практики программирования откройте Терминал/SSH и введите 'node'. Следующий алгоритм сортирует массив чисел с использованием алгоритма heapsort. Следуйте шагам:

  • Используйте рекурсию в функции.
  • Используйте оператор расширения (...) для клонирования исходного массива, arr.
  • Используйте замыкания для объявления переменной l и функции heapify.
  • Используйте цикл for и Math.floor() в сочетании с heapify, чтобы создать максимальную кучу из массива.
  • Используйте цикл for, чтобы последовательно сужать рассматриваемый диапазон, используя heapify и меняя значения при необходимости, чтобы отсортировать клонированный массив.
const heapsort = (arr) => {
  const a = [...arr];
  let l = a.length;
  const heapify = (a, i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let max = i;
    if (left < l && a[left] > a[max]) max = left;
    if (right < l && a[right] > a[max]) max = right;
    if (max !== i) {
      [a[max], a[i]] = [a[i], a[max]];
      heapify(a, max);
    }
  };
  for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i);
  for (let i = a.length - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    l--;
    heapify(a, 0);
  }
  return a;
};

Например:

heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]

Резюме

Поздравляем! Вы завершили лабу по Heap Sort. Вы можете практиковаться в более многих лабах в LabEx, чтобы улучшить свои навыки.