smooth sort与weakheap sort实现

本篇补充smooth sort和weakheap sort，不打算做太多介绍，因为自己太菜不会讲，只作为笔记来记录一下实现代码。smooth sort在接近排序完成的情况下的动态图

smooth sort

// http://www.keithschwarz.com/smoothsort/
static const unsigned int leonardo[] =
{
   1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973,
   3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785,
   392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773,
   18454929, 29860703, 48315633, 78176337, 126491971, 204668309, 331160281,
   535828591, 866988873, 1402817465, 2269806339u, 3672623805u,
};

template<typename RandomAccessIterator, class Comp>
void smooth_sort_fix(RandomAccessIterator arr, size_t current_heap, int level_index, int levels[], Comp compare)
{
    while (level_index > 0)
    {
        size_t prev_heap = current_heap - leonardo[levels[level_index]];
        if (compare(arr[current_heap], arr[prev_heap]))
        {
            if (levels[level_index] > 1)
            {
                size_t child_heap2 = current_heap - 1;
                size_t child_heap1 = child_heap2 - leonardo[levels[level_index] - 2];
                if (compare(arr[prev_heap], arr[child_heap1])
                    || compare(arr[prev_heap], arr[child_heap2]))
                    break;
            }
            std::swap(arr[current_heap], arr[prev_heap]);
            current_heap = prev_heap;
            level_index -= 1;
        }
        else
            break;
    }

    int current_level = levels[level_index];
    while (current_level > 1)
    {
        size_t max_child = current_heap;
        size_t child_heap2 = current_heap - 1;
        size_t child_heap1 = child_heap2 - leonardo[current_level - 2];

        if (compare(arr[max_child], arr[child_heap1])) max_child = child_heap1;
        if (compare(arr[max_child], arr[child_heap2])) max_child = child_heap2;
        if (max_child == child_heap1)
        {
            std::swap(arr[current_heap], arr[child_heap1]);
            current_heap = child_heap1;
            current_level -= 1;
        }
        else if (max_child == child_heap2)
        {
            std::swap(arr[current_heap], arr[child_heap2]);
            current_heap = child_heap2;
            current_level -= 2;
        }
        else break;
    }
}

template<typename RandomAccessIterator, class Comp>
void smooth_sort(RandomAccessIterator arr, size_t size, Comp compare)
{
    int levels[64] = { 1 };
    int toplevel = 0;

    for (size_t i = 1; i < size; ++i)
    {
        if (toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1)
        {
            toplevel -= 1;
            levels[toplevel] += 1;
        }
        else if (levels[toplevel] != 1)
        {
            toplevel += 1;
            levels[toplevel] = 1;
        }
        else
        {
            toplevel += 1;
            levels[toplevel] = 0;
        }
        smooth_sort_fix(arr, i, toplevel, levels, compare);
    }

    for (size_t i = size - 2; i > 0; --i)
    {
        if (levels[toplevel] <= 1)
        {
            toplevel -= 1;
        }
        else
        {
            levels[toplevel] -= 1;
            levels[toplevel + 1] = levels[toplevel] - 1;
            toplevel += 1;

            smooth_sort_fix(arr, i - leonardo[levels[toplevel]], toplevel - 1, levels, compare);
            smooth_sort_fix(arr, i, toplevel, levels, compare);
        }
    }
}

template<typename RandomAccessIterator, class Comp>
void smooth_sort(RandomAccessIterator beg, RandomAccessIterator end, Comp compare)
{
    if (end - beg > 1)
    {
        smooth_sort(&*beg, (size_t)(end - beg), compare);
    }
}

template<typename RandomAccessIterator>
void smooth_sort(RandomAccessIterator beg, RandomAccessIterator end)
{
    smooth_sort(beg, end, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

weakheap sort

unsigned char weakheap_getflag(unsigned char *r, size_t index)
{
    return (r[index >> 3] >> (index & 7)) & 1;
}

template<typename RandomAccessIterator, class Comp>
void weakheap_merge(unsigned char flags[], RandomAccessIterator beg, RandomAccessIterator i, RandomAccessIterator j, Comp compare)
{
    if (compare(*i, *j))
    {
        flags[(j - beg) >> 3] ^= 1 << ((j - beg) & 7);
        std::swap(*i, *j);
    }
}

template<typename RandomAccessIterator, class Comp>
void weakheap_sort(RandomAccessIterator beg, RandomAccessIterator end, Comp compare)
{
    if (end - beg > 1)
    {
        size_t n = (size_t)(end - beg);
        unsigned char * flags = new unsigned char[(n + 7) / 8];
        for (size_t i = 0; i < n / 8; ++i)
            flags[i] = 0;
        for (size_t i = n - 1; i > 0; --i)
        {
            size_t j = i;
            while ((j & 1) == weakheap_getflag(flags, j >> 1))
                j >>= 1;
            weakheap_merge(flags, beg, beg + (j >> 1), beg + i, compare);
        }
        for (size_t i = n - 1; i > 1; --i)
        {
            std::swap(*beg, *(beg + i));
            size_t j = 1, k;
            while ((k = 2 * j + weakheap_getflag(flags, j)) < i)
                j = k;
            while (j > 0)
            {
                weakheap_merge(flags, beg, beg, beg + j, compare);
                j >>= 1;
            }
        }
        std::swap(*beg, *(beg + 1));
        delete[] flags;
    }
}

template<typename RandomAccessIterator>
void weakheap_sort(RandomAccessIterator beg, RandomAccessIterator end)
{
    weakheap_sort(beg, end, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}