排序算法

排序稳定性

排序稳定性：排序前和排序后，相同元素的顺序是否能够保持。

排序算法验证

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
void printArray(const std::vector<int>& arr);
void yourSort(std::vector<int>& arr);
bool isSorted(const std::vector<int>& arr);
std::vector<int> generateRandomArray(int size, int min, int max);

void ShellSort(std::vector<int>& arr ,int gap)
{
    //排序算法
}

// 自定义排序算法
void yourSort(std::vector<int>& arr) {
    int gap = 5;
    ShellSort(arr, gap);//此处替换你的算法
    printArray(arr);
}

// 生成随机数组
std::vector<int> generateRandomArray(int size, int min, int max) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(min, max);

    std::vector<int> arr(size);
    for (int i = 0; i < size; ++i) {
        arr[i] = dis(gen);
    }
    printArray(arr);
    return arr;
}

// 打印数组元素
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 检查数组是否已排序
bool isSorted(const std::vector<int>& arr) {
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] < arr[i-1]) {
            return false;
        }
    }
    return true;
}

int main() {
    int size = 1000;  // 数组大小
    int min = 1;     // 最小值
    int max = 1000;  // 最大值

    // 生成随机数组
    std::vector<int> arr = generateRandomArray(size, min, max);

    // 复制数组，用于比较
    std::vector<int> arrCopy = arr;

    // 使用您的排序算法进行排序
    yourSort(arr);

    // 使用STL的std::sort进行排序
    std::sort(arrCopy.begin(), arrCopy.end());
    // 检查排序结果是否正确
    if (arr == arrCopy && isSorted(arr)) {
        std::cout << "您的排序算法是正确的！" << std::endl;
    } else {
        std::cout << "您的排序算法存在问题。" << std::endl;
    }
    return 0;
}

选择排序

最简单但是最没用的排序算法，有优化空间；

如何计算时间和空间复杂度；

算法的验证-随机数据生成器、对数器、写算法程序的哲学

算法思想：依次找到最小的数放在前面。

冒泡排序

初始值位置，依次向后比较，

void BubbleSort(std::vector<int>& arr)
{
    for(auto pArr = arr.begin();pArr != arr.end(); pArr++)
    {
        auto minArrPos = pArr;
        for (auto ppArr = pArr;ppArr != arr.end(); ppArr++)
        {
            if (*minArrPos > *ppArr)
            {
                minArrPos = ppArr;
            }
        }
        std::swap(*minArrPos,*pArr);
    }
}

插入排序

对基本有序和样本小的数组最好用、高效、稳定

void InsertionSort(std::vector<int>& arr)
{
    for(auto pArr = arr.begin();pArr != arr.end(); pArr++)
    {
        for (auto pData = pArr; pData > arr.begin(); pData --)
        {
            if (*pData < *(pData-1))
            {
                std::swap(*pData, *(pData-1));
            }
            else break;
        }
    }
}

希尔排序

是改进的插入排序

给定一个间隔；按照这个间隔分组、然后使用插入，

间隔缩小；然后分组依次排序

间隔再次缩小，直至间隔为1

void ShellSort(std::vector<int>& arr ,int gap)
{
    while (gap--)
    {
        for (auto iArr = arr.begin();iArr < arr.begin() + gap; iArr++)
        {
            for (auto piArr = iArr; piArr < arr.end(); piArr += gap)
            {
                for (auto  ipiArr = piArr ; ipiArr - gap >= arr.begin(); ipiArr -= gap)
                {
                    if (*ipiArr < *(ipiArr - gap)) //如果前面大于后面
                    {
                    std::swap(*ipiArr, *(ipiArr - gap));//交换元素
                    }
                    else {break;}
                }
            }
        }
    }
}

归并排序

使用递归算法进行分组，然后排序

对象排序一般要求稳定，

//已经拍好序的两半数据进行融合，以中心为界限
void MergeData(int* data ,int nsize)
{
    int * MidPos = data + nsize / 2;
    int * tempData(new int(nsize));//创建一组临时储存空间，以存放相关数据
    int * leftPos = data;
    int * rightPos = MidPos;
    for(int i = 0; i<nsize ; i++)
    {

        if (leftPos == MidPos && rightPos != data + nsize)//说明左面的数据走完了
        {//拷贝右侧的数据
            memcpy((void *)(tempData+i),(void *)rightPos,(data  + nsize - rightPos)*sizeof(int));
            break;
        }
        else if (leftPos != MidPos && rightPos == data + nsize)//说明右面的数据走完了
        {//拷贝左侧的数据
            memcpy((void *)(tempData+i),(void *)leftPos,(data  + nsize/2 - leftPos)*sizeof(int));
            break;
        }
        else if (leftPos != MidPos && rightPos != data + nsize)
        {
            if (*leftPos >= *rightPos)
            {
                *(tempData+i) = *rightPos;
                rightPos++;
            }
            else if (*leftPos < *rightPos)
            {
                *(tempData+i) = *leftPos;
                leftPos++;
            }
            else std::cerr << "err" <<std::endl;
        }
    }
    memcpy((void *)data,(void *)tempData, nsize*sizeof(int));
    delete tempData;
    tempData = nullptr;
    leftPos = nullptr;
    rightPos = nullptr;
}

void MergeSort(int* data ,int nsize)
{
    if (nsize <= 1){return;}
    int * mid = data + nsize / 2;
    MergeSort(mid, nsize - nsize/2);
    MergeSort(data, nsize/2);
    MergeData(data, nsize);
    /*printArray_(data, nsize);*/
}

// 自定义排序算法（替换为您的排序算法）
void yourSort(std::vector<int>& arr) {
    int* RawData(new int [arr.size()]);//创建一组临时储存空间，以存放相关数据
    int* pRawData = RawData;
    for (auto pos = arr.begin(); pos != arr.end();pos++, pRawData++)
    {
        *pRawData = *pos;
    }
    MergeSort(RawData, arr.size());//此处替换你的算法
    /*printArray_(RawData, arr.size());*/
    pRawData = RawData;
    for(auto pos = arr.begin(); pos != arr.end();pos++, pRawData++)
    {
        *pos = *pRawData;
    }
    printArray(arr);
    delete RawData;
    RawData = nullptr;
}

STL版本

void MergeData(std::vector<int>& RawData, int beginPos, int endPos){
        auto Apos = beginPos;
        auto midPos = ( beginPos + endPos ) / 2;
        auto Bpos = midPos;
        std::vector<int> Result;//最终结果
        while (1)
        {
            if (Apos == midPos) //说明前一组数据已经走完了
            {
                Result.insert(Result.end() ,RawData.begin() + Bpos, RawData.begin() + endPos);
                break;
            }
            else if (Bpos == endPos )
            {
                Result.insert(Result.end() ,RawData.begin() + Apos, RawData.begin() + midPos);
                break;
            }

            if (*(RawData.begin() + Apos) <= *(RawData.begin() + Bpos))
            {
                Result.push_back(*(RawData.begin() + Apos));
                Apos ++; 
            }
            else
            {
                Result.push_back(*(RawData.begin() + Bpos));
                Bpos ++; 
            }
        }//说明某一组数据已经走完了
               
        auto pTempDataPos = Result.begin();
        for (auto pData = beginPos; pData != endPos ; pData++)
        {
            *(RawData.begin() + pData) = *pTempDataPos;
            pTempDataPos++;
        }
    }

    void MergeSort(std::vector<int>& RawData, int beginPos, int endPos)//数据从0位置计算，左开右闭
    {
        if ( beginPos  + 1 >= endPos ) return; //小于一个数就不用排序了
        MergeSort(RawData, beginPos, (beginPos + endPos) / 2);
        MergeSort(RawData, (beginPos + endPos) / 2 , endPos);
        MergeData(RawData, beginPos, endPos);
    }

快速排序

快速排序

int* partition_Qs(int* pdataBegin ,int* pdataEnd)
{
    auto swap = [](int* pdata1 ,int * pdata2)
    {
        int temp = *pdata1;
        *pdata1 = *pdata2;
        *pdata2 = temp;
    };
    int * MidPos = pdataEnd;
    int * pDataLeft = pdataBegin;
    int * pDataRight = pdataEnd;
    while(pDataLeft < pDataRight)
    {
        while(pDataLeft < pDataRight && *pDataLeft <= *MidPos) pDataLeft++;
        while(pDataLeft < pDataRight && *pDataRight > *MidPos) pDataRight--;
        swap(pDataLeft, pDataRight);
    }
    swap(pDataLeft, MidPos);
    return pDataLeft;
}

void QuickSort(int* pdataBegin ,int* pdataEnd)
{
    if (pdataBegin == pdataEnd) return;
    int *pMid = partition_Qs(pdataBegin, pdataEnd);
    if (pdataBegin < pMid-1)
    {
        QuickSort(pdataBegin, pMid-1);
    }
    if (pMid + 1 < pdataEnd)
    {
        QuickSort(pMid + 1, pdataEnd);
    }
    //printArray_(pdataBegin, pdataEnd - pdataBegin + 1);
}

// 自定义排序算法（替换为您的排序算法）
void yourSort(std::vector<int>& arr) {
    int* RawData(new int [arr.size()]);//创建一组临时储存空间，以存放相关数据
    int* pRawData = RawData;
    for (auto pos = arr.begin(); pos != arr.end();pos++, pRawData++)
    {
        *pRawData = *pos;
    }
    QuickSort(RawData, RawData + arr.size() -1);//此处替换你的算法
    /*printArray_(RawData, arr.size());*/
    pRawData = RawData;
    for(auto pos = arr.begin(); pos != arr.end();pos++, pRawData++)
    {
        *pos = *pRawData;
    }
    printArray(arr);
    delete []RawData;
    RawData = nullptr;
}

使用deque容器的方法

struct DataFrame{
    int pos;
    int data;
    DataFrame(int _p, int _d){pos = _p; data = _d;}
};
int  partition_Qs(std::deque<DataFrame> & MyData, int begin, int end)
{
    auto comparePosData = [&](int pos1, int pos2)->int{
        return (MyData.begin() + pos1)->data - (MyData.begin() + pos2)->data;
    };
    auto swap = [&](int pos1, int pos2){
        int tempData = (MyData.begin() + pos1)->data;
        (MyData.begin() + pos1)->data = (MyData.begin() + pos2)->data;
        (MyData.begin() + pos2)->data = tempData;
    };
    int leftPos = begin;
    int rightPos = end;
    int midPos = end;
    while (leftPos < rightPos)
    {
        while(comparePosData(leftPos,midPos) <= 0 && leftPos < rightPos) leftPos++;//左侧找到大于mid的数据
        while(comparePosData(midPos,rightPos) < 0 && leftPos < rightPos) rightPos--;//右侧找到小于等于mid的数据
        swap(leftPos,rightPos);
    }
    swap(leftPos, midPos);
    return leftPos;
}

void QuickSortMyDataFrame(std::deque<DataFrame> & MyData, int begin, int end)
{
    if (begin == end) return;
    int Mid = partition_Qs(MyData, begin, end);
    if (begin < Mid-1)
    {
        QuickSortMyDataFrame(MyData , begin , Mid - 1);
    }
    if (Mid + 1 < end)
    {
        QuickSortMyDataFrame(MyData, Mid + 1, end);
    }
}

计数排序

是桶排序的一种

适用数据：量大但是范围小、例如年龄排序、

使用计数数组进行统计元素的种类和元素的数量（一种插入排序）、然后按照统计的元素数量把源数据按照源数据的顺序进行排序（稳定）。

其中关键的步骤是将记录元素数量的数组转换成记录元素位置的数组（向前累加当前位置元素的数量）

void insertSort(int* pdataBegin ,int* pdataEnd, int* pNum) //左开右闭
{
    auto swap = [](int *pData1, int* pData2){
        int tempData = *pData2;
        *pData2 = *pData1;
        *pData1 = tempData;
    };
    if (pdataBegin == pdataEnd)
    {
        return ;
    }
    auto pInsertData = --pdataEnd;
    while( (pInsertData--)!= pdataBegin)
    {
        if (*pInsertData > *(pInsertData+1)) //如果前一个数据大于当前的数据，说明需要交换
        {
            swap(pInsertData, pInsertData+1);
            swap((pInsertData - pdataBegin) + pNum, (pInsertData - pdataBegin) + pNum +1);
        }
        else
        {
            break;
        }
    }
}


void CountingSort(int* pdataBegin ,int* pdataEnd)//左闭右开
{
    //目的实现稳定的计数排序
     int * DataIndex(new int[pdataEnd - pdataBegin]);//创建一组临时储存空间，以存放排序数据
     int * DataNum(new int[pdataEnd - pdataBegin]);//创建一组临时储存空间，以存放排序数据
     int * tempData(new int[pdataEnd - pdataBegin]);//创建一组临时储存空间，以存放排序数据
     memset(DataNum,0,(pdataEnd - pdataBegin)*sizeof(int));//空间初始化
     int * pIndexidx = DataIndex;
     for(auto pData = pdataBegin ; pData < pdataEnd; pData++)//统计数据
     {
         //统计数据的分布
         auto pIdx = DataIndex;
         for (; pIdx < pIndexidx; pIdx++)//遍历已有统计数据的index量
         {
             if (*pData == *pIdx)//有当前数据
             {
              (*(DataNum + (pIdx - DataIndex)))++;//统计数据的量
              break;
             }
         }
        if (pIdx == pIndexidx)//说明当前没有能匹配上的
        {
            *(pIndexidx) = *pData; //填充数目
            *(pIndexidx - DataIndex + DataNum) = 1;
            pIndexidx++;
            insertSort(DataIndex, pIndexidx, DataNum);//
        }
     }
     for (auto pNum = DataNum + 1; pNum - DataNum < pIndexidx - DataIndex ; pNum++)//把每个样本的对应数据量计算成相应的位置
     {
        *pNum += *(pNum-1);//加上上一个位置的数据就是当前样本的数据位置（数组位置需要减1）
     }
    /*printArray(DataIndex,pIndexidx);
    printArray(DataNum,(DataNum + (pIndexidx - DataIndex)));*/
    for (auto pData =  pdataEnd; pData >=  pdataBegin; pData--)//遍历原有数据
    {
         for (auto pIdx = DataIndex; pIdx < pIndexidx; pIdx++)//遍历已有统计数据的index量
         {
             if (*pData == *pIdx)//有当前数据
             {
                 //std::cout << *pData << "and *(DataNum) = " << (*(DataNum + (pIdx - DataIndex))) - 1 <<std::endl;
                *(tempData + (-- (*(DataNum + (pIdx - DataIndex))))) = *pData;
                break;
             }
         }
    }
    memcpy(pdataBegin, tempData, (pdataEnd - pdataBegin)*sizeof(int));
    //printArray(pdataBegin, pdataEnd);
    //printArray(tempData, (tempData + (pdataEnd - pdataBegin)) );
    delete []DataIndex;
    delete []DataNum;
    delete []tempData;
    return;
}

// 自定义排序算法（替换为您的排序算法）
void yourSort(std::vector<int>& arr) {
    int* RawData(new int [arr.size() + 1]);//创建一组临时储存空间，以存放相关数据
    int* pRawData = RawData;
    for (auto pos = arr.begin(); pos != arr.end();pos++, pRawData++)
    {
        *pRawData = *pos;
    }
    CountingSort(RawData, RawData + arr.size());//此处替换你的算法
    //printArray(RawData, arr.size());
    pRawData = RawData;
    for(auto pos = arr.begin(); pos != arr.end();pos++, pRawData++)
    {
        *pos = *pRawData;
    }
    printArray(arr);
    delete []RawData;
    RawData = nullptr;
}

基数排序

桶排序的一种，非比较排序，本质上是一种多关键字排序（个位数、十位数、百位数、年龄、绩效、等）

先排个位数、再排十位数、然后再排百位数。。。。

桶排序

将样本数据的范围分成若干份（分成几个桶），然后再将桶内进行选择排序。

重难点

• 桶内存储方式应该选用链表的方式，要能扩容，不要每个桶都分配那么多空间。
• 如果数据储存方式选用链表的方式，那么排序算法就很麻烦