计数排序法

计数排序, 基数排序, 桶排序等非比较排序算法,平均时间复杂度都是O(n). 这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限.

计数排序是最简单的特例,它待排序元素是位于0到k之间的正整数, 因而它是很特殊的情况,基本上没有特别的应用价值; 但是另一方面, 它又是基数排序的基础,或者说是一部分,所以简单的描述一下:

输入数组 A : 元素特征是 0-k的正整数,可以有重复值;

输出数组 B : 输出A的一个非减序列

中间数组 C : 大小是k, 它的i( 0<= i <= k)索引位置存储的是A元素集合中值是k的元素的个数有关.

 

算法的基本思想是:

  • 统计A中元素的值的集合, 以A中元素的值为索引, 将值的个数填写到中间数组C的对应处.
  • 对C从头开始自累加, 这样C中存储的就是, 当输入数组A中的值为当前索引时, 它前面的元素数量(包含重复元素).
  • 将C依次输出到输出数组中.

例如:pku_2159

 

题目讲的很复杂,其实就是只要两个字符串中出现的字母的种类数和次数是一样的就YES,例如:
JWPUDJSTVP----------11111122
VICTORIOUS----------11111122
六个字母出现一次,两个字母出现两次,符合要求。
这样就转化为简单的排序了,用A1[]表示第一个字符串中的字符,
A1[1],A1[2]分别表示A B出现的次数,以此类推,用A2[]表示第二个字符串中
的字符,A2[1],A2[2]分别表示A B出现的次数,以此类推,然后用计数排序进
行排序,结果放入到B1,B2中,最后依此比较B1[i],B2[i]是否相等,全相等就
YES,否则NO。
 
代码:

#include 
<stdio.h>
int main()
{
    
int i;
    
bool flag=true;
    
char c;
    
//A1 A2分别存放两个字符串中A-Z共有多少个(A1[1],A2[1]存放A的个数,A1[2],A2[2]存放B的个数)    
    short A1[27]={0},A2[27]={0};
    
while((c=getchar())!='\n')
    
{
        A1[c
-64]++;
    }

    
//getchar();
    while((c=getchar())!='\n')
    
{
        A2[c
-64]++;
    }

    
//getchar();


    
//分别对两个数组进行计数排序
    int C1[101]={0},max_element=0;
    
int B1[27],temp;
    
    
for(i=1;i<=26;i++)
    
{
        temp
=A1[i];
        
if(temp>max_element)
            max_element
=temp;
        C1[temp]
++;
    }

      
for(i=0;i<=max_element;i++)
        C1[i
+1]+=C1[i];


    
for(i=26;i>=1;i--)
    
{
        B1[C1[A1[i]]]
=A1[i];
        C1[A1[i]]
--;
    }

      
    
int C2[101]={0};
    max_element
=0;
    
int B2[27];
    
    
for(i=1;i<=26;i++)
    
{
        temp
=A2[i];
        
if(temp>max_element)
            max_element
=temp;
        C2[temp]
++;
    }

    
for(i=0;i<=max_element;i++)
        C2[i
+1]+=C2[i];

    
for(i=26;i>=1;i--)
    
{
        B2[C2[A2[i]]]
=A2[i];
        C2[A2[i]]
--;
    }

    
//看对应是否相等
    for(i=1;i<=26;i++)
    
{
        
if(B1[i]!=B2[i])
        
{
            flag
=false;
            
break;
        }

        
    }


    
if(flag)
        printf(
"YES\n");
    
else
        printf(
"NO\n");

   
    
return 1;
}

posted on 2008-08-25 19:38 hobo 阅读(992) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC_ 算法

只有注册用户登录后才能发表评论。
<2008年8月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

相册

友情连接

搜索

最新评论

阅读排行榜

评论排行榜