[TOC]
使用常量来设置、清除以及测试位值：
提示：MASK 0x1f 2的SHIFT(5)次方，32位,把int型的变量每一位都当作一个标记。
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* bitsort.c -- bitmap sort from Column 1
* Sort distinct integers in the range [0..N-1]
*/
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
int main()
{ int i;
for (i = 0; i < N; i++)
clr(i);
/* Replace above 2 lines with below 3 for word-parallel init
int top = 1 + N/BITSPERWORD;
for (i = 0; i < top; i++)
a[i] = 0;
*/
while (scanf("%d", &i) != EOF)
set(i);
for (i = 0; i < N; i++)
if (test(i))
printf("%d\n", i);
return 0;
}
使用qsort快速排序
提示：
void qsort(voidbase,size_t num,size_t width,int(__cdeclcompare)(const void,const void));
各参数：1. 待排序数组首地址 2. 数组中待排序元素数量 3. 各元素的占用空间大小 4. 指向函数的指针
#include <stdio.h>
#include <stdlib.h>
int intcomp(int *x, int *y)
{ return *x - *y;
}
int a[1000000];
int main()
{ int i, n=0;
while (scanf("%d", &a[n]) != EOF)
n++;
qsort(a, n, sizeof(int), intcomp);
for (i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}
使用标准库版本的排序
#include <iostream>
#include <set>
using namespace std;
int main()
{ set<int> S;
int i;
set<int>::iterator j;
while (cin >> i)
S.insert(i);
for (j = S.begin(); j != S.end(); ++j)
cout << *j << "\n";
return 0;
}
1.6 习题
1.4 . 如何生成位于0至n-1之间的k个不同的随机顺序的随机整数? 尽量使你的程序简短且高效。
//生k个成0~n-1之间的随机数(k<n)
#include<iostream>
#include<time.h>
#include <stdlib.h> /* srand, rand */
using namespace std;
int const N = 10000;
int a[N];
int main(void)
{
int i,j,k=10;
for(i = 0 ;i < N; i++)
a[i] = i;
//初始化随机种子，产生随机数
srand((unsigned)time(NULL));
for(i = 0 ; i < k; i ++)
{
int tmp = rand() % (N - i);
cout << "tmp ->" << tmp << endl;
swap(a[tmp],a[N-i]);
}
for(i = N - 1 ; i > N - k;i--)
{
cout<<a[i]<<endl;
}
return 0;
}
1.6 增强，生成区间内的随机数，注意生成的随机数各不相同
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* bitsortgen.c -- gen $1 distinct integers from U[0,$2) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 2000000
int x[MAXN];
int randint(int a, int b)
{ return a + (RAND_MAX * rand() + rand()) % (b + 1 - a);
}
int main(int argc, char *argv[])
{ int i, k, n, t, p;
srand((unsigned) time(NULL));
k = atoi(argv[1]);
n = atoi(argv[2]);
for (i = 0; i < n; i++)
x[i] = i;
for (i = 0; i < k; i++) {
p = randint(i, n-1);
t = x[p]; x[p] = x[i]; x[i] = t;
printf("%d\n", x[i]);
}
return 0;
}
