《算法导论》——计数排序Counting Sort

不念不忘少年蓝@ 2021-12-09 01:11 174阅读 0赞

今天贴出的算法是计数排序Counting Sort。在经过一番挣扎之前，我很纠结，今天这个算法在一些scenarios，并不是最优的算法。最坏情况和最好情况下，时间复杂度差距很大。

代码CountingSort.h：

#include <stdlib.h>
    
    namespace dksl
    {
        void  Sort(int *numArray,int length)
        {        
            int max=numArray[0];    
            int *temp=new int[length];
            for(int i=0;i<length;i++)
            {
                temp[i]=0;
                if(max<numArray[i])
                    max=numArray[i];
            }
            int* C=new int[max+1];
            for(int i=0;i<=max;i++)
                C[i]=0;
            for(int i=0;i<length;i++)
                C[numArray[i]]=C[numArray[i]]+1;
            for(int i=1;i<=max;i++)
                C[i]=C[i]+C[i-1];
            for(int i=0;i<length;i++)
            {
                temp[C[numArray[i]]-1]=numArray[i];
                C[numArray[i]]=C[numArray[i]]-1;
            }
            for(int i=0;i<length;i++)
                numArray[i]=temp[i];
            delete temp;
            delete C;
        }
    }

测试：

// CountingSort.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include "CountingSort.h"
    
    using namespace std;
    using namespace dksl;
    int _tmain(int argc, _TCHAR* argv[])
    {
        int a[10] = {
        1, 4, 8, 5, 10, 25, 54, 15, 12, 2};
        Sort(a,10);
        cout<<"The sorted array is:";    
        for(int i = 0; i < 10; i++)        
            cout<<a[i]<<" ";   
        cout<<endl;
        system("PAUSE");
        return 0;
    }

结果：

![27215628-908b6de4ac6944c2b84d2c289767af7b.png][]

转载于:https://www.cnblogs.com/DKSL/p/3159883.html

[27215628-908b6de4ac6944c2b84d2c289767af7b.png]: /images/20211209/30cc2e01b8704a858238fe6b6626700a.png