Сложность Лучшее Среднее Худшее
Время O(n log n) O(n log n) O(n log n)
Память O(n)
Пирамидальная сортировка / Heap sort
Пирамидальная сортировка - это улучшенная сортировка выбором.
Для сортировки используется бинарное сортирующее дерево - дерево, у которого выполнены условия:
Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
Значение в любой вершине не меньше значения её потомков.
Общая идея алгоритма:
Выстраиваем массив в виде сортирующего дерева:
Array[i] >= Array[2i + 1]
Array[i] >= Array[2i + 2]
при 0 <= i < n/2
Обмениваем элементы Array[0] и Array[n-1] местами. Array[0] является корнем сортирующего дерева, т.е. самым большим значением массива.
Повторям шаги до тех пор, пока в сортирующем дереве не останется один элемент.
Пример реализации на Kotlin:
fun heapSort(a: IntArray) {
heapify(a)
var end = a.size - 1
while (end > 0) {
val temp = a[end]
a[end] = a[0]
a[0] = temp
end--
siftDown(a, 0, end)
}
}
fun heapify(a: IntArray) {
var start = (a.size - 2) / 2
while (start >= 0) {
siftDown(a, start, a.size - 1)
start--
}
}
fun siftDown(a: IntArray, start: Int, end: Int) {
var root = start
while (root * 2 + 1 <= end) {
var child = root * 2 + 1
if (child + 1 <= end && a[child] < a[child + 1]) child++
if (a[root] < a[child]) {
val temp = a[root]
a[root] = a[child]
a[child] = temp
root = child
}
else return
}
}
fun main(args: Array) {
val aa = arrayOf(
intArrayOf(100, 2, 56, 200, -52, 3, 99, 33, 177, -199),
intArrayOf(4, 65, 2, -31, 0, 99, 2, 83, 782, 1),
intArrayOf(12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8)
)
for (a in aa) {
heapSort(a)
println(a.joinToString(", "))
}
}
Достарыңызбен бөлісу: |
