[数据结构与算法]数据结构与算法-十大经典排序算法

先讲主要结论，
O(n^2)级别的算法，百万数据想都别想跑。
O(nlogn)，花几秒。
计数等一系列排序，就零点几秒。
不实际自己写写是很难体会O(n)级别的快速的！！！

1. 参考自菜鸟教程

2. 详细代码

注意，如要引用，请注意头文件路径的问题。
注意，是基础实现，未加优化，可能有效率问题。
注意，实现思路不止一种，注意模板的选择问题。

1. 容器类

1. TArray

#pragma once
#include <iostream>
#include <vector>

template <typename T>
class TArray : public std::vector<T>
{
public:
    //默认构造函数
    TArray()
        : std::vector<T>()
    { };

    //右值构造函数
    TArray(TArray<T>&& Other) 
        : std::vector<T>(std::move(Other))
    { };

    //拷贝构造函数
    TArray(const TArray<T>& Other)
        : std::vector<T>(Other)
    { };

    //聚合体构造函数
    TArray(std::initializer_list<T> L)
        : std::vector<T>(L)
    { };

    //迭代器构造函数
    template <typename Iter>
    TArray(Iter t1, Iter t2)
        : std::vector<T>(t1, t2)
    { };

    //重载=
    TArray<T>& operator=(TArray<T>&& Other)
    {
        std::vector<T>::operator=(std::move(Other));
        return *this;
    }

    //重载=
    TArray<T>& operator=(const TArray<T>& Other)
    {
        std::vector<T>::operator=(Other);
        return *this;
    }

    //重载[]
    T& operator[](int Index)
    {
        return std::vector<T>::operator[](Index);
    }

    //设置数量
    void SetNum(const int Size)
    {
        std::vector<T>::resize(Size);
    }

    //获取数量
    int GetNum() const
    {
        return static_cast<int>(std::vector<T>::size());
    }

    //添加元素
    void Add(const T& Element)
    {
        std::vector<T>::push_back(Element);
    }
};

2. TQueue

#pragma once
#include <queue>
template <typename T>
class TQueue:public std::queue<T>
{
};

2. 工具类

1. FFunctionLibrary

1. FFunctionLibrary.h

#pragma once
#include <iostream>
#include "../T/TArray.h"
#include <string>
class FFunctionLibrary {
public:
    // IntArray 转 String
    static std::string IntArrayToString(const TArray<int>& Array);
    //打印IntArray
    static void PrintIntArray(const TArray<int>& Array);
};

2. FFunctionLibrary.cpp

#include "FFunctionLibrary.h"

std::string FFunctionLibrary::IntArrayToString(const TArray<int>& Array)
{
    std::string Message = "[";
    for (std::vector<int>::const_iterator i = Array.cbegin(); i != Array.cend(); ++i) {
        Message.append(std::to_string(*i));
        Message.append(",");
    }
    Message[Message.length() - 1] = ']';
    return Message;
}

void FFunctionLibrary::PrintIntArray(const TArray<int>& Array)
{
    std::cout << IntArrayToString(Array) << "\n";
}

2. FTimer

1. FTimer.h

#pragma once
#include <ctime>
class FTimer {
protected:
    clock_t StartTime = 0;
    clock_t EndTime = 0;
    double ResultTime = 0.0f;

public:
    void SetTimer();
    void StopTimer();
    void ShowTime() const;
};

2. FTimer.cpp

#include "FTimer.h"

#include <iostream>
#include <iomanip>

void FTimer::SetTimer()
{
    StartTime = clock();
}

void FTimer::StopTimer()
{
    EndTime = clock();
    ResultTime = ((EndTime - StartTime) * 1.0) / CLOCKS_PER_SEC;
    ShowTime();
}

void FTimer::ShowTime() const
{
    std::cout << "Total: " <<std::fixed<<std::setprecision(3)<<ResultTime << "s\n";
}

3. 算法类

1. FSort

#pragma once
#include "../T/TArray.h"
#include "../T/TQueue.h"

class FSort
{
public:
    /*
     *  冒泡排序
     *  时间O(n^2)
     *  空间O(1)
     *  稳定(逐个交换位置)
     */
    template <typename ElementType>
    static void BubbleSort(TArray<ElementType>& Array);

    /*
     *  选择排序
     *  时间O(n^2)
     *  空间O(1)
     *  不稳定(跳着交换位置:2 2 1 3)
     */
    template <typename ElementType>
    static void SelectionSort(TArray<ElementType>& Array);

    /*
     *  插入排序
     *  时间O(n^2)
     *  空间O(1)
     *  稳定
     */
    template <typename ElementType>
    static void InsertionSort(TArray<ElementType>& Array);

    /*
     *  希尔排序
     *  时间O(nlogn)
     *  空间O(1)
     *  不稳定
     */
    template <typename ElementType>
    static void ShellSort(TArray<ElementType>& Array);

public:
    /*
     *  归并排序
     *  时间O(nlogn)
     *  空间O(n)
     *  稳定
     */
    template <typename ElementType>
    static void MergeSort(TArray<ElementType>& Array);
private:
    template <typename ElementType>
    static void MergeSortUsingRecursion(TArray<ElementType>& Array, int Left, int Right);
    template <typename ElementType>
    static void MergeSortUsingIteration(TArray<ElementType>& Array);

public:
    /*
     *  快速排序
     *  时间O(nlogn)
     *  空间O(logn)
     *  不稳定
     */
    template <typename ElementType>
    static void QuickSort(TArray<ElementType>& Array);
private:
    template <typename ElementType>
    static void QuickSortUsingRecursion(TArray<ElementType>& Array, int Left, int Right);
    template <typename ElementType>
    static void QuickSortUsingIteration(TArray<ElementType>& Array);

public:
    /*
     *  堆排序
     *  时间O(nlogn)
     *  空间O(1)
     *  不稳定
     */
    template <typename ElementType>
    static void HeapSort(TArray<ElementType>& Array);
private:
    template <typename ElementType>
    static void Heapfiy(TArray<ElementType>& Array, int Start, int End);

public:
    /*
     *  计数排序
     *  时间O(n+k)
     *  空间O(k)
     *  稳定
     */
    static void CountSort(TArray<int>& Array);

    /*
     *  桶排序
     *  时间O(n+k)
     *  空间O(n+k)
     *  稳定?(根据内在使用的排序所定)
     */
    static void BucketSort(TArray<int>& Array);

    /*
     *  基数排序
     *  时间O(n*k)
     *  空间O(n+k)
     *  稳定
     */
    static void RadixSort(TArray<int>& Array);
};

template <typename ElementType>
inline void FSort::BubbleSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    for (int i = 0; i < (Length - 1); ++i)
    {
        for (int j = i + 1; j < Length; ++j)
        {
            if (Array[i] > Array[j])
            {
                std::swap(Array[i], Array[j]);
            }
        }
    }
}

template <typename ElementType>
inline void FSort::SelectionSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    for (int i = 0; i < (Length - 1); ++i)
    {
        int min = i;
        for (int j = i + 1; j < Length; ++j)
        {
            if (Array[j] < Array[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            std::swap(Array[i], Array[min]);
        }
    }
}

template <typename ElementType>
inline void FSort::InsertionSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    for (int i = 1; i < Length; ++i)
    {
        ElementType Value = Array[i];
        int j = i - 1;
        while (j >= 0 && Array[j] > Value)
        {
            Array[j + 1] = Array[j];
            --j;
        }
        //多减了一次j
        Array[j + 1] = Value;
    }
}

template <typename ElementType>
inline void FSort::ShellSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    for (int Gap = Length / 2; Gap >= 1; Gap = Gap / 2)
    {
        for (int i = Gap; i < Length; ++i)
        {
            ElementType Value = Array[i];
            int j = i - Gap;
            //合适则把元素往后面挪
            while (j >= 0 && Array[j] > Value)
            {
                Array[j + Gap] = Array[j];
                j -= Gap;
            }
            Array[j + Gap] = Value;
        }
    }
}

template <typename ElementType>
inline void FSort::MergeSortUsingRecursion(TArray<ElementType>& Array, int Left, int Right)
{
    if (Left >= Right)
    {
        return;
    }
    int Mid = (Left + Right) / 2;
    //分治，先分在治
    MergeSortUsingRecursion(Array, Left, Mid);
    MergeSortUsingRecursion(Array, Mid + 1, Right);
    TArray<ElementType> LeftArray(Array.begin() + Left, Array.begin() + Mid + 1);
    TArray<ElementType> RightArray(Array.begin() + Mid + 1, Array.begin() + Right + 1);
    int K = Left;
    int Start1 = 0, End1 = Mid - Left + 1;
    int Start2 = 0, End2 = Right - Mid;
    while (Start1 < End1 && Start2 < End2)
    {
        Array[K++] = LeftArray[Start1] < RightArray[Start2] ? LeftArray[Start1++] : RightArray[Start2++];
    }
    while (Start1 < End1)
    {
        Array[K++] = LeftArray[Start1++];
    }
    while (Start2 < End2)
    {
        Array[K++] = RightArray[Start2++];
    }
}

template <typename ElementType>
inline void FSort::MergeSortUsingIteration(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    TArray<ElementType>* OriginArray = &Array;
    TArray<ElementType>* Temp = new TArray<ElementType>();
    Temp->SetNum(Length);
    //迭代就从【分的不能分的地方】开始向上操作
    for (int Gap = 1; Gap < Length; Gap *= 2)
    {
        for (int Index = 0; Index < Length; Index += Gap * 2)
        {
            int Left = Index;
            int Mid = std::min(Index + Gap, Length);
            int Right = std::min(Index + Gap * 2, Length);
            int K = Left;
            int Start1 = Left, End1 = Mid;
            int Start2 = Mid, End2 = Right;
            while (Start1 < End1 && Start2 < End2)
            {
                (*Temp)[K++] = (*OriginArray)[Start1] < (*OriginArray)[Start2]
                                   ? (*OriginArray)[Start1++]
                                   : (*OriginArray)[Start2++];
            }
            while (Start1 < End1)
            {
                (*Temp)[K++] = (*OriginArray)[Start1++];
            }
            while (Start2 < End2)
            {
                (*Temp)[K++] = (*OriginArray)[Start2++];
            }
        }
        std::swap(Temp, OriginArray);
    }
    delete Temp;
}

template <typename ElementType>
inline void FSort::MergeSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    if (Length < (1 << 12))
    {
        MergeSortUsingRecursion(Array, 0, Length - 1);
    }
    else
    {
        MergeSortUsingIteration(Array);
    }
}

template <typename ElementType>
inline void FSort::QuickSortUsingRecursion(TArray<ElementType>& Array, int Left, int Right)
{
    if (Left >= Right)
    {
        return;
    }
    int Low = Left, High = Right;
    ElementType Value = Array[(Left + Right) / 2];
    while (Low < High)
    {
        while (Array[Low] < Value)
        {
            ++Low;
        };
        while (Array[High] > Value)
        {
            --High;
        };
        /*错误写法，这样无论条件是否成立，其值都会增加
        while (Array[Low++] < Value) {};
        while (Array[High--] > Value) {};
        */
        if (Low <= High)
        {
            std::swap(Array[Low], Array[High]);
            ++Low, --High;
        }
    }
    QuickSortUsingRecursion(Array, Left, High);
    QuickSortUsingRecursion(Array, Low, Right);
}

template <typename ElementType>
inline void FSort::QuickSortUsingIteration(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    struct Node
    {
        int Left;
        int Right;
    };
    //用队列维护要操作的区间
    TQueue<Node> NodeArray;
    NodeArray.push({0, Length - 1});
    while (!NodeArray.empty())
    {
        Node Temp = NodeArray.front();
        NodeArray.pop();
        int Left = Temp.Left;
        int Right = Temp.Right;
        if (Left < Right)
        {
            int Low = Left, High = Right;
            ElementType Value = Array[(Left + Right) / 2];
            while (Low < High)
            {
                while (Array[Low] < Value)
                {
                    ++Low;
                };
                while (Array[High] > Value)
                {
                    --High;
                };
                if (Low <= High)
                {
                    std::swap(Array[Low], Array[High]);
                    ++Low, --High;
                }
            }
            NodeArray.push({Left, High});
            NodeArray.push({Low, Right});
        }
    }
}

template <typename ElementType>
inline void FSort::QuickSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    if (Length < (1 << 12))
    {
        QuickSortUsingRecursion(Array, 0, Length - 1);
    }
    else
    {
        QuickSortUsingIteration(Array);
    }
}

template <typename ElementType>
inline void FSort::Heapfiy(TArray<ElementType>& Array, int Start, int End)
{
    int Dad = Start;
    int Son = Dad * 2 + 1;
    while (Son <= End)
    {
        //左右孩子的比较
        if ((Son + 1) <= End && Array[Son] < Array[Son + 1])
        {
            ++Son;
        }
        //维护大根堆
        if (Array[Dad] > Array[Son])
        {
            return;
        }
        else
        {
            std::swap(Array[Dad], Array[Son]);
            Dad = Son;
            Son = Dad * 2 + 1;
        }
    }
}

template <typename ElementType>
inline void FSort::HeapSort(TArray<ElementType>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    for (int i = Length / 2 - 1; i >= 0; --i)
    {
        Heapfiy(Array, i, Length - 1);
    }
    for (int i = Length - 1; i > 0; --i)
    {
        //将找到的最大值放到数组最后
        std::swap(Array[0], Array[i]);
        Heapfiy(Array, 0, i - 1);
    }
}

inline void FSort::CountSort(TArray<int>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    TArray<int>* Temp = new TArray<int>();
    int MinValue = Array[0], MaxValue = Array[0];
    for (int i = 0; i < Length; ++i)
    {
        MinValue = std::min(MinValue, Array[i]);
        MaxValue = std::max(MaxValue, Array[i]);
    }
    
    //处理负数
    const int Gap = MinValue * (-1) + 1;
    const int RealMaxValue = MaxValue + Gap;
    Temp->SetNum(RealMaxValue + 1);
    
    for (int i = 0; i < Length; ++i)
    {
        ++((*Temp)[Array[i] + Gap]);
    }
    //确定元素放回位置
    for (int i = 1; i <= RealMaxValue; ++i)
    {
        (*Temp)[i] += (*Temp)[i - 1];
    }
    //放回原数组
    TArray<int> Copy = Array;
    for (int i = Length - 1; i >= 0; --i)
    {
        Array[--((*Temp)[Copy[i] + Gap])] = Copy[i];
    }

    delete Temp;
}

inline void FSort::BucketSort(TArray<int>& Array)
{
    const int Length = Array.GetNum();
    if (Length==0)
    {
        return;
    }
    int MinValue = Array[0];
    int MaxValue = Array[0];
    for (int i = 0; i < Length; ++i)
    {
        MinValue = std::min(MinValue, Array[i]);
        MaxValue = std::max(MaxValue, Array[i]);
    }

    //将均摊的极差作为桶数
    const int BucketNum = (MaxValue - MinValue) / Length + 1;
    TArray<TArray<int>>* BucketArray=new TArray<TArray<int>>();
    BucketArray->SetNum(BucketNum);

    for (int i = 0; i < Length; ++i)
    {
        const int Index=(Array[i]-MinValue)/Length;
        (*BucketArray)[Index].Add(Array[i]);
    }

    //内部排序
    for (auto&  i:(*BucketArray))
    {
        CountSort(i);
    }

    //依次放回原数组
    int Index=0;
    for (auto& i:*BucketArray)
    {
        for (auto& j:i)
        {
            Array[Index++]=j;
        }
    }
    delete BucketArray;
}

inline void FSort::RadixSort(TArray<int>& Array)
{
    const int Length=Array.GetNum();
    if (Length==0)
    {
        return;
    }
    //求最小值和最大值
    int MinValue = Array[0];
    int MaxValue = Array[0];
    for (int i = 0; i < Length; ++i)
    {
        MinValue = std::min(MinValue, Array[i]);
        MaxValue = std::max(MaxValue, Array[i]);
    }
    const int Gap = MinValue * (-1) + 1;
    const int RealMaxValue = MaxValue + Gap;
    for (int i = 0; i < Length; ++i)
    {
        Array[i]+=Gap;
    }
    //求最大值的位数
    int DigitNum=1;
    int TempValue=RealMaxValue;
    while((TempValue/10)>0)
    {
        TempValue/=10;
        ++DigitNum;
    }
    
    TArray<int>* Temp=new TArray<int>();
    TArray<int>* Count=new TArray<int>();
    Temp->SetNum(Length);
    Count->SetNum(10);
    int Radix=1;
    for (int i=1;i<=DigitNum;++i)
    {
        for (auto& j:(*Count))
        {
            j=0;
        }
        //顺序计数
        for (int j=0;j<Length;++j)
        {
            ++((*Count)[(Array[j]/Radix)%10]);
        }
        //确定位置
        for (int j=1;j<10;++j)
        {
            (*Count)[j]+=(*Count)[j-1];
        }
        //倒序放置(后计数的位置在上面)
        for (int j=Length-1;j>=0;--j)
        {
            const int Num=(Array[j]/Radix)%10;
            (*Temp)[(*Count)[Num]-1]=Array[j];
            --((*Count)[Num]);
        }
        for (int j=0;j<Length;++j)
        {
            Array[j]=(*Temp)[j];
        }
        Radix*=10;
    }
    for (int i=0;i<Length;++i)
    {
        Array[i]-=Gap;
    }
    delete Temp;
    delete Count;
}

4. 测试代码

#include "F/FSort.h"
#include "F/FTimer.h"
#include "T/TArray.h"
#include "F/FFunctionLibrary.h"

int main()
{
    TArray<int> CustomArray;
    for (int i = 0; i < 100; ++i)
    {
        CustomArray.Add(rand() % 100-50);
    }
    FTimer Timer;
    FFunctionLibrary::PrintIntArray(CustomArray);
    Timer.SetTimer();
    FSort::MergeSort(CustomArray);
    Timer.StopTimer();
    FFunctionLibrary::PrintIntArray(CustomArray);
    system("Pause");
}