Triển khai Heap Sort bằng JavaScript thuần túy

Heap Sort về cơ bản là một thuật toán sắp xếp dựa trên so sánh. Nó có thể được coi như một selection sort cải tiến – giống như thuật toán đó, nó chia đầu vào thành một vùng đã sắp xếp và một vùng chưa sắp xếp, và nó tương tác thu hẹp vùng chưa sắp xếp bằng cách trích xuất phần tử mục tiêu (lớn nhất hoặc nhỏ nhất) và di chuyển nó đến vùng đã sắp xếp.

Ví dụ

Mã thực hiện:

const constructHeap = (arr, ind) => {
  let left = 2 * ind + 1;
  let right = 2 * ind + 2;
  let max = ind;
  if (left < len && arr[left] > arr[max]) { max = left; }
  if (right < len && arr[right] > arr[max]) { max = right; }
  if (max != ind) {
    swap(arr, ind, max);
    constructHeap(arr, max);
  }
}
function swap(arr, index_A, index_B) {
  let temp = arr[index_A];
  arr[index_A] = arr[index_B];
  arr[index_B] = temp;
}
function heapSort(arr) {
  len = arr.length;
  for (let ind = Math.floor(len / 2); ind >= 0; ind -= 1) {
    constructHeap(arr, ind);
  }
  for (ind = arr.length - 1; ind > 0; ind--) {
    swap(arr, 0, ind);
    len--;
    constructHeap(arr, 0);
  }
}
const arr = [3, 0, 2, 5, -1, 4, 1];
heapSort(arr);
console.log(arr);
var len;

Kết quả

Kết quả trong console:

[ -1, 0, 1, 2, 3, 4, 5 ]