数据结构--排序

专题--排序

1. 冒泡排序（O(n²)）

#include <iostream>
#include <vector>
using namespace std;
//降序排
void swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

//冒泡排序
//版本A
void BubbleSort(vector<int> &mvec)
{
    int len=mvec.size();
    for(int i=0;i<len-1;++i)
    {
        for(int j=i+1;j<len;++j)
        {
            if(mvec[i]<mvec[j])
                swap(mvec[i],mvec[j]);
        }
    }
}
//版本B：注意j从后向前循环
void BubbleSort1(vector<int> &mvec)
{
    int len=mvec.size();
    for(int i=0;i<len;++i)
    {
        for(int j=len-1;j>i;--j)  //从后向前
        {
            if(mvec[j-1]<mvec[j])
                swap(mvec[j-1],mvec[j]);
        }
    }
}
//版本C：避免不必要的循环
void BubbleSort2(vector<int> &mvec)
{
    bool flag=true;  //
    int len=mvec.size();
    for(int i=0;i<len&&flag;++i)
    {
        flag=false;
        for(int j=len-1;j>i;--j) //从后向前
        {
            if(mvec[j-1]<mvec[j])
            {
                flag=true;
                swap(mvec[j-1],mvec[j]);
            }
        }
    }
}

int main()
{
    vector<int> mvec{0,5,4,7,3,6,2,1,8,9};
    BubbleSort2(mvec);
    for(auto &mem:mvec)
        cout<<mem<<" ";
    cout<<endl;
    return 0;
}

2. 简单选择排序（O(n²)）

//简单选择排序
void SelectSort(vector<int> &mvec)
{
    int len=mvec.size();
    for(int i=0;i<len-1;++i)
    {
        int maxI=i;       //用于记录
        for(int j=i+1;j<len;++j)
        {
            if(mvec[maxI]<mvec[j])
                maxI=j;  //暂时不交换
        }
        if(maxI!=i)
            swap(mvec[maxI],mvec[i]);
    }
}


int main()
{
    vector<int> mvec{0,5,4,7,3,6,2,1,8,9};
    //BubbleSort2(mvec);
    SelectSort(mvec);
    for(auto &mem:mvec)
        cout<<mem<<" ";
    cout<<endl;
    return 0;
}

3. 直接插入排序（O(n²)）

　　注意：不需要调用swap()，适用于“记录少，基本有序的情况”。

//直接插入排序
void InsertSort(vector<int> &mvec)
{
    int len=mvec.size();
    for(int i=1;i<len;++i)     //从i=1开始：假设mvec[0]有序
    {
        if(mvec[i-1]<mvec[i])
        {
            int temp=mvec[i];  //记录mvec[i]，找到正确位置插入
            int j;
            for(j=i-1;mvec[j]<temp;--j)  //从后向前
                mvec[j+1]=mvec[j];  //将有序子表后移
            mvec[j+1]=temp;    //插入到正确位置
        }
    }
}

int main()
{
    vector<int> mvec{0,5,4,7,3,6,2,1,8,9};
    //BubbleSort2(mvec);
    //SelectSort(mvec);
    InsertSort(mvec);
    for(auto &mem:mvec)
        cout<<mem<<" ";
    cout<<endl;
    return 0;
}

 4. 堆排序和快速排序

//堆排序：注意：不计mvec[0]
//已知记录mvec中中的关键字除mvec[s]之外均满足堆的定义
void HeapAdjust(vector<int> &mvec,int s,int m)
{
    int temp=mvec[s];
    for(int j=2*s;j<=m;j*=2)
    {
        if(j<m && mvec[j]<mvec[j+1])  //右孩子大
            ++j;     //j为关键字中较大的记录的下标
        if(temp>=mvec[j])
            break;
        mvec[s]=mvec[j];
        s=j;
    }
    mvec[s]=temp;   //插入
}
void HeapSort(vector<int> &mvec)
{
    int len=mvec.size()-1;
    for(int i=len/2;i>0;--i)
    {
        HeapAdjust(mvec,i,len);
    }
    for(int i=len;i>1;--i)
    {
        swap(mvec[1],mvec[i]);
        HeapAdjust(mvec,1,i-1);
    }
}
//快速排序
int Partition(vector<int> &mvec,int lo,int hi)
{
    int pikey=mvec[lo];
    while(lo<hi)
    {
        while(lo<hi && mvec[hi]<=pikey)
            --hi;
        swap(mvec[lo],mvec[hi]);
        while(lo<hi && mvec[lo]>=pikey)
            ++lo;
        swap(mvec[lo],mvec[hi]);
    }
    return lo;  //最终lo和hi值相等;mvec[lo]==mvec[hi]==pikey
}
void QSort(vector<int> &mvec,int lo,int hi)
{
    if(lo<hi)
    {
        int pi=Partition(mvec,lo,hi); //已将mvec[pi]放到合适位置

        QSort(mvec,lo,pi-1);
        QSort(mvec,pi+1,hi);
    }
}
//快排主函数
void QuikSort(vector<int> &mvec)
{
    int len=mvec.size()-1;  //注意 hi=mvec.size()-1
    QSort(mvec,0,len);
}


int main()
{
    vector<int> mvec{9,5,4,7,3,6,2,1,0,8};
    //BubbleSort2(mvec);
    //SelectSort(mvec);
    //InsertSort(mvec);
    //HeapSort(mvec);
    QuikSort(mvec);
    for(auto &mem:mvec)
        cout<<mem<<" ";
    cout<<endl;
    return 0;
}