Это HeapSort или нет?

Изучаю алгоритмы по алгоритму: Сначала разбираюсь с идеей, потом реализую, затем ищу решения и сравниваю со своим кодом.

Реализовав рабочий HeapSort не могу найти что-то подобное в интернете, везде какие-то многострочные конструкции.

Вопрос: Ниже HeapSort или нет?

public static void HeapSort(int[] array)
{
    for (int i = array.Length - 1; i > 0; i--)
    {
        MakeHeap(array, i);
        Swap(ref array[0], ref array[i]);
    }
}

private static void MakeHeap(int[] array, int arrayLength)
{
    for (int i = arrayLength / 2; i >= 0; i--)
    {
        for (int childId = 1; childId < 3; childId++)
        {
            if (2 * i + childId <= arrayLength && array[i] < array[2 * i + childId])
            {
                Swap(ref array[i], ref array[2 * i + childId]);
            }
        }
    }
}

private static void Swap<T>(ref T value1, ref T value2)
    => (value1, value2) = (value2, value1);

Буду благодарен за конструктивную критику, полезные дополнения, источники и т.п.(с меня лайк, + в карму и галочка за лучший(субъективно) ответ)


Ответы (1 шт):

Автор решения: MBo

Эта реализация выглядит квадратичной, т.к. на каждом шаге выполняется построение частичной кучи.

Нормальная сортировка требует линейного времени на построение кучи и nlogn на перестроение в сортированный массив

→ Ссылка