计数排序

布满荆棘的人生 2022-07-14 01:26 315阅读 0赞

计数排序，他的主要目的是对整数排序并且会比普通的排序算法性能更好。

1.  初始化一个计数数组，大小是输入数组中的最大的数。
2.  遍历输入数组，遇到一个数就在计数数组对应的位置上加一。例如：遇到5，就将计数数组第五个位置的数加一。
3.  把计数数组直接覆盖到输出数组（节约空间）。

/*
     *      计数排序
     *      这种算法只适用于已知所排序元素范围的排序操作
     *      有一定的局限性
     *      对于计数，一般只能是正数，因为数组的下标是不能为负的
     */
    
    #include <iostream>
    #include <time.h>
    
    #define size 10
    
    using namespace std;
    
    void printsort(int p[],int n)
    {
        for(int i=0;i<n;i++)
            cout<<p[i]<<" ";
    }
    
    int findmax(int p[],int n)
    {
        int max=p[0];
        for(int i=1;i<n;i++)
        {
            if(p[i]>max)
                max=p[i];
        }
        return max;
    }
    
    void countersort(int p[],int n,int q[],int m)
    {
        for(int i=0;i<n;i++)
        {
            if(p[i]>0)
                q[p[i]-1]++;
        }
        cout<<"计数数组："<<endl;
        int num1=0;
        for(int i=0;i<m;i++)
        {
            cout<<q[i]<<" ";
            num1++;
            if(num1%10==0)
                cout<<endl;
        }
            cout<<endl;
    
        int num=0;
        for(int i=0;i<m;i++)
        {
            if(q[m]!=0)
            {
                for(int j=0;j<q[i];j++)
                    p[num++]=i+1;
            }
        }
    }
    
    int main()
    {
        int p[size]={0};
        srand((unsigned)time(NULL));//保证每次生成的数不一样
        cout<<"需排序数组："<<endl;
        for(int i=0;i<size;i++)  //随机生成10个大于0的数
        {
            p[i]=rand()%100+1;
            cout<<p[i]<<" ";
        }
        cout<<endl;
    
        int size2=findmax(p,size);//得到计数数组的大小
        int q[size2]={0};
    
        countersort(p,size,q,size2);
    
        cout<<"排序后："<<endl;
        printsort(p,size);
        return 0;
    }

![Center][]

[Center]: /images/20220714/171c4bc9ed5e4ac3b43b3c1030a45cd0.png