写在前面

本来是想做一个多线程排序的练习，对比一下单线程排序和多线程排序的差异，顺便练个手，于是便转而研究起了常用排序算法，闷头学习了两三天，自己梳理了一下常用排序算法的原理，并把每个都写了下，最初想要做的多线程排序反倒不了了之了。最后其实有尝试过多线程快排，不过因为不熟悉，导致效果不太理想，这就暂且不表了。我收回上次对CSDN编辑器的吐槽，这周发现，MarkDown才是写文档的正确方式，只不过每个行内公式最后都会出现一个竖线，是什么情况，百度了也不是我一个人的问题，而且还没发解决，有点影响美观。

插入排序（insertion sort)

复杂度：$O\left(N^2\right)$
- 特点：无须额外空间，对于有序数组，只要N-1次比较，0次交换
- 改进：shell sort

template <typename T>
void CInsertSort<T>::mysort(function<bool(T, T)> compare)
{
    for(int i(1);i<len;++i)
    {
        for (int j = i; j > 0 && compare(datas[j],datas[j-1]); --j)
        {
            swap(datas[j],datas[j-1]);
        }
    }
}

选择排序(select sort)

复杂度：$O(N^2)$,$\dfrac{N^2}{2}$次比较，$N$次交换
特点：复杂度与数组特性无关，数据移动最小
改进：每遍历一次同时选出最大与最小的

template <typename T>
void CSelectSort<T>::mysort(function<bool(T, T)> compare)
{
    for(int i(0);i<len;++i)
    {
        int id(i);
        for (int j = i+1; j < len; ++j)
        {
            id = compare(datas[id], datas[j]) ? id : j ;
        }
        swap(datas[i], datas[id]);
    }
}

希尔排序（shell sort)

复杂度：复杂度和增量选择有关，所以无法给出，大约和$O(N^\tfrac{5}{4})$成正比，具体视选取的增量而定，暂无数学推导过程
特点：插排的改进，比插入排序的效率更高
改进：shell path的选取，一般3的倍数的情况下，效果较好

void CShellSort<T>::mysort(function<bool(T, T)> compare)
{
    int h(1);
    while (h < len / 3)
        h = 3 * h + 1;
    while(h>=1)
    {
        for (int i = h; i < len; i++)
        {
            for (int j = i; j >= h && compare(datas[j],datas[j-h]) ; j-=h)
            {
                swap(datas[j], datas[j - h]);
            }
        }
        h /= 3;
    }
}

归并排序（merge sort）

complex : 正比于$N\log{N}$,缺点在于需要额外的内存空间
trait : 将两组原本有序的数组合并为一个数组，实现起来有自上而下和自下而上两种；
自上而下的，可以用递归的方式完成，在单个数组单元里元素个数小到一定程度时可以使用插入排序优化；
自下而上的方式适合链表结构的数据组，不需要创建新的节点。
improvement : 将子数组规模比较小的时候选择插入排序

void CMergeSort<T>::mysort(function<bool(T, T)> compare)
{
    for(int i(0),j(0);i<datas1.size() || j<datas2.size();)
    {
        if (i >= datas1.size())
            res.emplace_back(datas2[j++]);
        else if (j >= datas2.size())
            res.emplace_back(datas1[i++]);
        else
        {
            if (compare(datas1[i], datas2[j]))
                res.emplace_back(datas1[i++]);
            else
                res.emplace_back(datas2[j++]);
        }
    }
}

快排(quick sort)

complex : 复杂度为$O(N\log N)$
trait : 相比插入排序以及希尔排序的优势在于交换的次数少，小规模时，速度比希尔排序慢，大规模更快。
improvement :

小规模的时候切换到插入排序或者希尔排序
使用三取样切分（中位数组）
熵最优的切分

template <typename T>
void CQuickSort<T>::qksort(iter beg, int len, function<bool(T, T)>& compare)
{
    if (len <= 1) return;
    int pos = partial(beg, len, 0, compare);
    qksort(beg, pos, compare);
    qksort(beg + pos + 1, len - pos -1, compare);
}

template <typename T>
int CQuickSort<T>::partial(iter beg, int len, int pos, function<bool(T, T)>& compare)
{
    if (len <= 1) return 0;
    swap(*beg, *(beg + pos));
    int i(0), j(len);
    while(true)
    {
        while (compare(*(beg + ++i), *beg))
            if(i >= len-1) break;
        while (compare(*beg, *(beg + --j)))
            if(j <= 0) break;
        if (i >= j) break;
        swap(*(beg + i), *(beg + j));
    }
    swap(*beg, *(beg + j));
    return j;
}

总结

Reference

这里主要参考了《算法》4th.

浏览量: 2,113

排序算法整理