堆排序 - 实现的复杂性 [英] heapsort - implementation's complexity

问题描述

我写了 heapsort (Cormen).算法排序正确，但复杂度高于预期.

I wrote heapsort (Cormen). Algorithm is sorting correctly but complexity is greater than expected.

void heap_sort(int tab[], int length)
{
    build_max_heap(tab, length);
    int heap_size = length;
    for (int i = length-1; i > 1; i--)
    {
        int tmp = tab[1];
        tab[1] = tab[i];
        tab[i] = tmp;
        heap_size--;
        max_heapify(tab, 1, heap_size);
    }
}

void max_heapify (int tab[], int i, int length)
{
    int largest;
    int l = i * 2;
    int r = i * 2 + 1;
    if (l < length and tab[l] > tab[i])
        largest = l;
    else
        largest = i;
    if (r < length and tab[r] > tab[largest])
        largest = r;
    if (largest != i)
    {
        int tmp = tab[i];
        tab[i] = tab[largest];
        tab[largest] = tmp;
        max_heapify(tab, largest, length);
    }
}

void build_max_heap(int tab[], int length)
{
    for (int i = length/2; i >= 1; i--)
        max_heapify(tab, i, length);
}

对于 rand() 生成的 15000000 个数字，它比在此实现中使用 Shell 排序持续时间更长:

For 15000000 numbers generated by rand() it lasted longer than sorting with Shell sort in this implementation:

void shell_sort (int tab[], int length)
{
    int x = 2;
    int q;
    do
    {
        x*=2;
        q=2*(length/x) + 1;
        for(int i = q, val, j; i < length; i++)
        {
            val = tab[i];
            for(j = i - q ; j >= 0 and tab[j] > val; j-=q)
            {
                tab[j + q] = tab[j];
            }
            tab[j + q] = val;
        }
    }while (q > 1);
}

测试:

HEAPSORT
Time for 1000000 elements: 0.336 s
Time for 2000000 elements: 0.732 s
Time for 3000000 elements: 1.142 s
Time for 4000000 elements: 1.595 s
Time for 5000000 elements: 2.034 s
Time for 6000000 elements: 2.513 s
Time for 7000000 elements: 3.023 s
Time for 8000000 elements: 3.51 s
Time for 9000000 elements: 4.02 s
Time for 10000000 elements: 4.558 s
Time for 11000000 elements: 5.095 s
Time for 12000000 elements: 5.595 s
Time for 13000000 elements: 6.183 s
Time for 14000000 elements: 6.7 s
Time for 15000000 elements: 7.367 s

SHELLSORT
Time for 1000000 elements: 0.343 s
Time for 2000000 elements: 0.779 s
Time for 3000000 elements: 1.182 s
Time for 4000000 elements: 1.654 s
Time for 5000000 elements: 2.218 s
Time for 6000000 elements: 2.672 s
Time for 7000000 elements: 3.34 s
Time for 8000000 elements: 3.778 s
Time for 9000000 elements: 4.297 s
Time for 10000000 elements: 4.903 s
Time for 11000000 elements: 4.872 s
Time for 12000000 elements: 5.514 s
Time for 13000000 elements: 6.29 s
Time for 14000000 elements: 6.994 s
Time for 15000000 elements: 7.121 s

我重复了多次测试.算法有什么问题?

I repeated the test many times. What's wrong with the algorythm?

推荐答案

首先要注意，big-O 和原始性能之间有着复杂的关系.在堆排序的情况下，糟糕的内存局部性会导致它在计算机上的扩展性比 big-O 建议的要差.相比之下，shell 排序只比 O(n log(n)) 稍微差一些，并且它的大部分传递都具有不错的内存局部性.

First note, big-O and raw performance have a complicated relationship. In the case of heapsort, poor memory locality will cause it to scale worse on computers than big-O would suggest. By contrast shell sort is only very slightly worse than O(n log(n)) and most of its passes have decent memory locality.

因此，我对它们具有可比性并不感到惊讶.

I'm therefore not surprised that they are comparable.

也就是说，您可以尝试将 max_heapify 从递归函数转换为循环.这可能会避免一定数量的堆栈操作.

That said, you could try turning max_heapify from a recursive function into a loop. That may avoid a certain amount of stack manipulation.

这篇关于堆排序 - 实现的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！