在《编程珠玑》上看到的,开篇第一个问题,有很多数,小于一个MAXNUM,没有重复的,怎么排序最快。
答案是位图排序. 如果某一位不为0,那么这一位存代表一个数,位数(在序列中的位置)代表这个数。
比方说这些数都存在数组a,然后利用一个数组b,b初始状态各位都为0,然后读取a,如果a[1]=2,那么b[2]为1,a[3]=6,那么b[6]=1。
实现如下:
1 #include2 #include 3 #include 4 #include 5 #define MAXNUM 200 6 int Isood(int n); 7 8 using namespace std; 9 10 11 int main(void)12 {13 vector v1,v2;14 int n;15 cin>>n;16 int m;17 m=MAXNUM;18 while(n)19 {20 int t;21 cin>>t;22 v1.push_back(t);23 n--;24 }25 26 while(m)27 {28 v2.push_back(0);29 m--;30 }31 32 for(int i=0;i