algorithm
Куча сортировки
Поиск…
Heap Sort Базовая информация
Heap sort - это метод сортировки, основанный на сравнении, в структуре данных двоичной кучи. Он похож на сортировку выбора, в которой мы сначала находим максимальный элемент и помещаем его в конец структуры данных. Затем повторите тот же процесс для остальных предметов.
Псевдокод для кучи Сортировать:
function heapsort(input, count)
heapify(a,count)
end <- count - 1
while end -> 0 do
swap(a[end],a[0])
end<-end-1
restore(a, 0, end)
function heapify(a, count)
start <- parent(count - 1)
while start >= 0 do
restore(a, start, count - 1)
start <- start - 1
Пример сортировки кучи:
Вспомогательное пространство: O(1)
Сложность времени: O(nlogn)
Реализация C #
public class HeapSort
{
public static void Heapify(int[] input, int n, int i)
{
int largest = i;
int l = i + 1;
int r = i + 2;
if (l < n && input[l] > input[largest])
largest = l;
if (r < n && input[r] > input[largest])
largest = r;
if (largest != i)
{
var temp = input[i];
input[i] = input[largest];
input[largest] = temp;
Heapify(input, n, largest);
}
}
public static void SortHeap(int[] input, int n)
{
for (var i = n - 1; i >= 0; i--)
{
Heapify(input, n, i);
}
for (int j = n - 1; j >= 0; j--)
{
var temp = input[0];
input[0] = input[j];
input[j] = temp;
Heapify(input, j, 0);
}
}
public static int[] Main(int[] input)
{
SortHeap(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow