排序算法整理

排序算法整理

写在前面

本来是想做一个多线程排序的练习,对比一下单线程排序和多线程排序的差异,顺便练个手,于是便转而研究起了常用排序算法,闷头学习了两三天,自己梳理了一下常用排序算法的原理,并把每个都写了下,最初想要做的多线程排序反倒不了了之了。最后其实有尝试过多线程快排,不过因为不熟悉,导致效果不太理想,这就暂且不表了。我收回上次对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 :
  1. 小规模的时候切换到插入排序或者希尔排序
  2. 使用三取样切分(中位数组)
  3. 熵最优的切分
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.

Comments are closed.