Для сортировки на месте следует самый быстрый способ. Остерегайтесь ошибок в моем коде. Обратите внимание, что этот метод дает перевернутый отсортированный список, который необходимо изменить на последнем шаге. Если вы используете максимальную кучу, эта проблема исчезнет.
Общая идея ясна: поменяйте местами наименьший элемент (с индексом 0) с последним элементом в куче, разбейте этот элемент вниз, пока свойство кучи не восстановится, уменьшите размер кучи на единицу и повторите.
Это не самый быстрый способ сортировки не по месту, поскольку Дэвид Маккей демонстрирует здесь - вы можете добиться большего успеха, поместив элемент, который с наибольшей вероятностью окажется самым маленьким в верхней части кучи вместо одного из нижнего ряда.
Сложность по времени - T (n.log n), наихудший случай - n итераций с возможным log n (высотой кучи) проходит через цикл while.
for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
{
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
{
if (l[i] > l[left])
{
swapidx = left;
}
}
else
{
if (l[i] > l[right])
{
swapidx = right;
}
}
if (swapidx == i)
{
// Found right place in the heap, break.
break;
}
swap( l, i, swapidx );
i = swapidx;
}}
// Now reverse the list in linear time:
int s = 0;
int e = len(l)-1;
while (e > s)
{
swap( l, s, e );
s++; e--:
}