排序算法

插入排序

• 属于原址排序
• 复杂度为O(n²)
• 基本原理:在排序子数组A[0, i]后，将A[i]插入子数组的适当位置，产生排序好的子数组A[0, i + 1]
• 参考《算法导论》P9

//升序
template<typename T>
void InsertSort(T* pValue, const size_t nLenC)
{
    for (size_t i = 1; i < nLenC; ++i)
    {
        auto nTem = pValue[i];
        auto nId = i - 1;

        while (nId >= 0 && pValue[nId] > nTem)
        {
            pValue[nId + 1] = pValue[nId];
            --nId;
        }

        pValue[nId + 1] = nTem;
    }
}

分治排序

• 并非原址排序
• 算法复杂度为θ(n lgn)
• 基本原理:将待排序的元素均分为两部分，重复此步骤直至被划分的部分足够少，能够被排序，然后进行合并
• 参考《算法导论》P16

template<typename T>
void Merge(T* pLeft, const size_t nLeftSizeC, T* pRight, 
    const size_t nRightSizeC, T* pOut)
{
    size_t i = 0;       //左边buff的id
    size_t j = 0;       //右边buff的id
    size_t k = 0;       //输出buff的id

    while (i < nLeftSizeC || j < nRightSizeC)
    {
        if (i < nLeftSizeC && j < nRightSizeC)
        {
            if (pLeft[i] > pRight[j])
            {
                goto LeftBig;
            }
            else
            {
                goto RightBig;
            }
        }
        else if (i == nLeftSizeC)
        {
            goto LeftBig;
        }
        else
        {
            goto RightBig;
        }

    LeftBig:
        pOut[k++] = pRight[j++];
        continue;

    RightBig:
        pOut[k++] = pLeft[i++];
    }
}

template<typename T>
void MergeSort(T* pBuff, const size_t nSizeC)
{
    auto nLeft = nSizeC / 2;
    auto nRight = nSizeC - nLeft;

    if (nLeft > 1)
    {
        MergeSort(pBuff, nLeft);
    }

    if (nRight > 1)
    {
        MergeSort(pBuff + nLeft, nRight);
    }

    T* pOut = new T[nSizeC];
    Merge(pBuff, nLeft, pBuff + nLeft, nRight, pOut);
    memcpy(pBuff, pOut, sizeof(T) * nSizeC);
    delete[] pOut;
}

堆排序

• 属于原址排序
• 复杂度O(n lgn)
• 基本原理:将输入数组构造为一个最大堆，获取根节点，将剩余数据重新构造为最大堆，继续获取根节点，直至剩余数据个数为1
• 最大堆性质:除根节点外的某个节点的值至多与其父节点一样大
• 参考算法导论P84

//获取当前节点的左子节点
int GetLeft(const int nIdC)
{
    return 2 * (nIdC + 1) - 1;
}

//获取当前节点的右子节点
int GetRight(const int nIdC)
{
    return 2 * (nIdC + 1);
}

/*
假定Left(nIdC)和Right(nIdC)所构成的二叉树都是最大堆，则nIdC可能
不满足最大堆的性质，利用此函数，将nIdC所代表的元素下沉到合适位置，
则维护了最大堆的性质

此函数复杂度:O(lgn)
*/
template<typename T>
void MaxHeap(T* pBuff, const int nIdC, const int nSizeC)
{
    auto nLeft = GetLeft(nIdC);
    auto nRight = GetRight(nIdC);
    auto nBigId = nIdC;

    if (nLeft < nSizeC && pBuff[nLeft] > pBuff[nBigId])
    {
        nBigId = nLeft;
    }

    if (nRight < nSizeC && pBuff[nRight] > pBuff[nBigId])
    {
        nBigId = nRight;
    }

    if (nBigId != nIdC)
    {
        std::swap(pBuff[nIdC], pBuff[nBigId]);
        MaxHeap(pBuff, nBigId, nSizeC);
    }
}

/*
利用自底向上的方法，利用 MaxHeap 将输入数组构建为最大堆

此函数复杂度为O(n)，此处证明见算法导论
*/
template<typename T>
void BuildHeap(T* pBuff, const int nSizeC)
{
    for (int i = nSizeC / 2; i >= 0; --i)
    {
        MaxHeap(pBuff, i, nSizeC);
    }
}

/*
不断构建最大堆且取其根节点的过程
*/
template<typename T>
void HeapSort(T* pBuff, const int nSizeC)
{
    BuildHeap(pBuff, nSizeC);
    for (int i = nSizeC - 1; i >= 1; --i)
    {
        std::swap(pBuff[0], pBuff[i]);
        BuildHeap(pBuff, i);
    }
}

快排

• 属于原址排序
• 复杂度:期望复杂度为θ(n lgn)，且隐含的常数因子非常小，最坏情况的复杂度是θ(n²)
• 基本原理:从待排序的数组中选取一个值，以此值进行划分，则划分结束后此值的位置就是最后排序好的位置，对此值左边、右边进行递归重复此过程
• 快排的运行时间依赖于划分是否平衡
• 参考《算法导论》P96

template<typename T>
size_t Partition(T* pBuff, const size_t nSizeC)
{
    //增加算法的随机性
    srand(static_cast<unsigned int>(time(0)));
    std::swap(pBuff[nSizeC - 1], pBuff[rand() % nSizeC]);

    T nValue = pBuff[nSizeC - 1];
    size_t nPos = 0;

    for (size_t i = 0; i < nSizeC - 1; ++i)
    {
        if (pBuff[i] < nValue)
        {
            std::swap(pBuff[nPos], pBuff[i]);
            ++nPos;
        }
        /*
        说明:
        nPos以左的值均小于划分值，nPos以右且i以左均大于划分值
        i以右不做限制
        */
    }

    std::swap(pBuff[nPos], pBuff[nSizeC - 1]);

    return nPos;
}

template<typename T>
void QuickSort(T* pBuff, const size_t nSizeC)
{
    if (nSizeC > 1)
    {
        auto nId = Partition(pBuff, nSizeC);
        QuickSort(pBuff, nId);
        QuickSort(pBuff + nId, nSizeC - nId);
    }
}

线性时间排序

比较排序算法的下界

• 比较排序:在排序的最终结果中，各元素的次序依赖于它们之间的比较
• 任何比较排序在最坏情况下都要经过Ω(n lgn)次比较
• 比较排序可以被抽象为一颗决策树，决策树是一棵完全二叉树，可以表示给定的输入规模下，某一特定的排序算法对所有元素的比较操作。考虑一棵高度为h，具有x个可达叶节点的决策树，它对应一个对N个元素所做的比较排序，输入数据的n!种可能的排列都是叶节点，所以有n! ≤ x。由于在一棵高度为h的二叉树中，叶节点的数目不会多于2^h，所以有n! ≤ 2^h，则h ≥ lg(n!)，则h = Ω(n lgn)
• 参考《算法导论》P107

计数排序

• 计数排序假设n个输入元素中的每一个都是[0, k)内的一个整数，其中k为某个整数，当k = O(n)时，排序的运行时间为θ(n)
• 计数排序的基本思想:对每一个输入元素x，确定小于x的元素的个数，利用此信息，将x直接放入输出数组的位置上
• 计数排序是稳定排序:不会改变具有相同值元素在原输入中的相对位置
• 参考《算法导论》P108

template<typename T>
void CountSort(T* pArray, const int nLenC, const int nMaxValueC)
{
    //存放计数
    auto pCount = new T[nMaxValueC + 1]();
    
    //存放排序好的结果
    auto pOut = new T[nLenC]();

    for (int i = 0; i < nLenC; ++i)
    {
        //pCount[i]包含了pArray所有值为i的元素个数
        ++pCount[pArray[i]];
    }

    for (int i = 1; i < nMaxValueC + 1; ++i)
    {
        //pCount[i]中存储了pArray中所有小于等于i的值
        pCount[i] += pCount[i - 1];
    }

    for (int i = nLenC - 1; i >= 0; --i)
    {
        //根据pCount存储的值，就可以直接得到pArray[i]排序好后的位置
        pOut[pCount[pArray[i]] - 1] = pArray[i];
        --pCount[pArray[i]];
    }

    memcpy(pArray, pOut, sizeof(T) * nLenC);

    delete[] pCount;
    delete[] pOut;
}

基数排序

• 基数排序先按照最低有效位进行排序，然后对得到的结果的依次高位进行递归排序，上述过程进行的排序必须是稳定排序(比如采取计数排序)
• 参考《算法导论》P110

桶排序

• 桶排序假设输入数据服从均匀分布，平均情况下它的时间代价为Ω(n)。与计数排序类似，因为对输入元素做了某种假设，所以桶排序的速度也很快。
• 原理:桶排序将输入区间划分为n个相同大小的子区间，或称为桶。然后将n个输入数分别放入各个桶中，将每个桶中的数进行排序，然后遍历每个桶，按照次序将各个桶中的元素取中即为排序好的结果
• 参考《算法导论》P112