实现各种排序算法
本文最后更新于 595 天前,其中的信息可能已经有所发展或是发生改变。

题图 https://www.pixiv.net/artworks/78572402

排序算法

其实这些东西之前就写了,不过最近刚看了一点《++标准模板库编程实战》,里面写了一个通过迭代器实现排序的例子,就想着把我之前写的排序算法也都改为使用迭代器。不过修改的过程中也碰到了一些问题,比如怎么通过std::iterator_traits来提取变量类型(不过这应该是Cpp primer的内容,还是看得少了Orz)

测试用例

void unit_test()
{
    auto restore = [&](int *x) {
        x[0] = 12;
        x[1] = 2;
        x[2] = 16;
        x[3] = 30;
        x[4] = 8;
        x[5] = 28;
        x[6] = 4;
        x[7] = 10;
        x[8] = 20;
        x[9] = 6;
        x[10] = 18;
    };

    int array[11];

    restore(array);
    bubbleSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nBubble sort finished without error\n";

    restore(array);
    selectSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nSelect sort finished without error\n";

    restore(array);
    insertSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nInsertion sort finished without error\n";

    restore(array);
    shellSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nShell sort finished without error\n";

    restore(array);
    heapSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nHeap sort finished without error\n";

    restore(array);
    mergeSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nMerge sort finished without error\n";

    restore(array);
    quickSort(array, array + 11);
    std::copy(array, array + 11, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nQuick sort finished without error\n";
}

冒泡排序

template <typename RandomIter>
void bubbleSort(RandomIter start, RandomIter end)
{
    bool sorted{false};
    for (auto first = end; first > start; --first)
    {
        for (auto second = start + 1; second < first; ++second)
        {
            if (*second < *(second - 1))
            {
                std::swap(*(second - 1), *second);
                sorted = true;
            }
        }
        if (!sorted)
        {
            return;
        }
    }
}

选择排序

template <typename RandomIter>
void selectSort(RandomIter start, RandomIter end)
{
    for (auto first = start; first < end; ++first)
    {
        auto minPos = first;
        for (auto second = first + 1; second < end; ++second)
        {
            if (*second < *minPos)
            {
                minPos = second;
            }
        }
        std::swap(*first, *minPos);
    }
}

插入排序

template <typename RandomIter>
void insertSort(RandomIter start, RandomIter end)
{
    typename std::iterator_traits<RandomIter>::value_type insertion;

    for (auto first = start + 1; first < end; ++first)
    {
        insertion = *first;
        auto second = first;
        for (; second > start; --second)
        {
            if (*(second - 1) > insertion)
            {
                *second = *(second - 1);
            }
            // 没有交换就说明已经插入到了指定的位置
            else
            {
                break;
            }
        }
        *second = insertion;
    }
}

希尔排序

template <typename RandomIter>
void _ShellSort(RandomIter start, RandomIter end, 
typename std::iterator_traits<RandomIter>::difference_type stride)
{
    typename std::iterator_traits<RandomIter>::value_type insertion;

    for (auto first = start + stride; first < end; first += stride)
    {
        insertion = *first;
        auto second = first;
        for (; second > start; second -= stride)
        {
            // 元素后移一位
            if (*(second - stride) > insertion)
            {
                *second = *(second - stride);
            }
            // 没有交换就说明已经找到了指定的位置
            else
            {
                break;
            }
        }
        // 空出来的位置给插入的元素
        *second = insertion;
    }
}

template <typename RandomIter>
void shellSort(RandomIter start, RandomIter end)
{
    typename std::iterator_traits<RandomIter>::difference_type stride = (end - start) / 2;
    while (stride)
    {
        _ShellSort(start, end, stride);
        stride /= 2;
    }
}

堆排序

template <typename RandomIter>
void _DownToMaxHeap(RandomIter start, RandomIter end, RandomIter pos)
{
    auto parent = pos;
    auto child = start + (parent - start) * 2 + 1;

    /*调整begin位置的非叶子结点 --整个堆排序的核心代码块*/
    while (child < end)
    {
        if (end - child > 1 && *child < *(child + 1))
        {
            ++child;//右孩子节点
        }
        if (*child > *parent)
        {
            std::swap(*child, *parent);
        }
        else
        {
            break;
        }
        parent = child;
        child = start + (parent - start) * 2 + 1;
    }
}

template <typename RandomIter>
void _BuildMaxHeap(RandomIter start, RandomIter end)
{
    if (end - start < 2)
    {
        return;
    }

    auto parent = start + (end - start) / 2 + 1;
    while (parent >= start)
    {
        _DownToMaxHeap(start, end, parent);
        --parent;
    }
}

template <typename RandomIter>
void heapSort(RandomIter start, RandomIter end)
{
    //构造最大堆
    _BuildMaxHeap(start, end);

    while (end > start)
    {
        std::swap(*start, *(--end));
        _DownToMaxHeap(start, end, start);
    }
}

归并排序

template <typename RandomIter>
void _MergeSort(RandomIter start, RandomIter mid, RandomIter end)
{
    typedef typename std::iterator_traits<RandomIter>::value_type value_type;
    int length = static_cast<int>(end - start);
    value_type *buffer = new value_type[length];

    int ptr = 0;
    auto lptr = start;
    auto rptr = mid;

    while (lptr < mid && rptr < end)
    {
        buffer[ptr++] = (*lptr < *rptr) ? *(lptr++): *(rptr++);
    }

    while (lptr < mid)
    {
        buffer[ptr++] = *(lptr++);
    }

    while (rptr < end)
    {
        buffer[ptr++] = *(rptr++);
    }

    for (int i = 0; i < length; ++i)
    {
        *(start++) = buffer[i];
    }

    delete buffer;
}

template <typename RandomIter>
void mergeSort(RandomIter start, RandomIter end)
{
    //数组arr空or仅有一个元素则退出
    if (end - start < 2)
    {
        return;
    }

    auto mid = start + (end - start) / 2;
    mergeSort(start, mid);
    mergeSort(mid, end);
    _MergeSort(start, mid, end);
}

快速排序

template <typename RandomIter>
RandomIter _getIndex(RandomIter start, RandomIter end)
{
    auto pivotValue = *start;
    while (start < end)
    {
        while  (start < end && *(--end) > pivotValue);
        *start = *end;
        while (start < end && *(++start) < pivotValue);
        *end = *start;
    }
    *start = pivotValue;
    return start;
}

template <typename RandomIter>
void quickSort(RandomIter start, RandomIter end)
{
    if (start < end)
    {
        auto pivot = _getIndex(start, end);
        quickSort(start, pivot);
        quickSort(pivot + 1, end);
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇