Javascript - Thuật toán Heapsort
Thuật toán heapsort
Heap sort là kỹ thuật sắp xếp dựa trên so sánh dựa trên cấu trúc dữ liệu Binary Heap. Nó tương tự như sắp xếp lựa chọn, nơi đầu tiên chúng ta tìm phần tử lớn nhất và đặt phần tử lớn nhất ở cuối. Chúng ta lặp lại quá trình tương tự cho các phần tử còn lại.
Mã nguồn:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Sorts an array of numbers, using the mergesort algorithm.</title>
<script>
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);
document.write(arr);
</script>
</head>
<body>
</body>
</html>
Lưu đồ thuật toán:
