Сортировка кучи разделена на два процесса:
1. Постройте кучу.
Куча представляет собой полностью двоичное дерево и должна соответствовать следующему: ключевые слова любого нелистного узла в дереве не больше (или не меньше, чем) ключевые слова ребенка (если есть) узел.
Куча разделена на: большую корневую кучу и небольшую корневую кучу. Восходящий порядок используется для сортировки большой корневой кучи, а нисходящий порядок используется для сортировки небольшой корневой кучи.
Если это большая корневая куча, узел с наибольшим значением регулируется на корень кучи путем настройки функции.
2. Сохраните корень кучи на хвосте и вызовите функцию регулировки для оставшейся последовательности. После завершения регулировки сохраните максимальный последователь на хвосте -1 (-1, -2, ..., -i), а затем отрегулируйте оставшуюся последовательность и повторите процесс до завершения сортировки.
Кода -копия выглядит следующим образом:
// Регулируйте функцию
функция Headadjust (элементы, POS, Len) {
// Сохранить текущее значение узла
var swap = elements [pos];
// Найти узел дочернего узела слева от текущего узла
var Child = pos * 2 + 1;
// рекурсивно, пока не появятся дети
while (ребенок <len) {
// Если в текущем узле есть узел дочернего узела справа, а правильный дочерний узел больше, используйте правильный дочерний узел
// Сравнение с текущим узлом
if (ребенок + 1 <len && elements [ребенок] <elements [Child + 1]) {
ребенок += 1;
}
// Сравните текущий узел с самым большим детьми узлом, если значение меньше, чем выполнить обмен значением и найти текущий узел после обмена
// на детском узле
if (elements [pos] <elements [ребенок]) {
Элементы [POS] = элементы [ребенок];
POS = ребенок;
Ребенок = POS * 2 + 1;
}
еще{
перерыв;
}
Элементы [POS] = SWAP;
}
}
// Построить кучу
функция BuildHeap (элементы) {
// Начнется с последнего узла с детским узлом, сравните узел с его дочерним узлом,
// После обмена наибольшим числом с этим узлом тот же процесс обмена выполняется в передний узел.
// до тех пор, пока не будет построена большая верхняя куча (порядок восхождения в большую верхнюю часть, нисходящий порядок маленький верх)
for (var i = elements.length/2; i> = 0; i-) {
Headadjust (Elements, i, elements.length);
}
}
сортировка функций (элементы) {
// Построить кучу
BuildHeap (элементы);
// Приспособитесь с конца последовательности
for (var i = elements.length-1; i> 0; i-) {
// Верхняя часть кучи всегда является самым большим элементом, поэтому верхняя часть кучи и хвостовой элемент будут обменены.
// Максимальный элемент сохраняется в конце и не участвует в последующих корректировках
var swap = elements [i];
элементы [i] = элементы [0];
элементы [0] = SWAP;
// внести коррективы, отрегулируйте максимальный элемент в верхнюю часть кучи
Headadjust (элементы, 0, i);
}
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('до:' + elements);
сортировка (элементы);
console.log ('After:' + elements);
эффективность:
Сложность времени: лучшее: O (nlog2n), худшее: o (nlog2n), среднее: o (nlog2n).
Сложность пространства: O (1).
Стабильность: нестабильная