学步园

大概是空间换时间的思想，用一个bit标示一个数字；

关于产生前N个数的随机排列的方法需要注意~

#include <stdio.h><br /> #include <stdlib.h><br /> #include <time.h></p> <p>#define N 1000000</p> <p>unsigned int Rand(int low, int high)<br /> {<br /> if ( low == high )<br /> return low;<br /> return low + rand()%(high-low);<br /> }</p> <p>void Swap( int * a, int * b)<br /> {<br /> int tmp = *a;<br /> *a = *b;<br /> *b = tmp;<br /> }<br /> void Input(int a[] )<br /> {<br /> srand(time(0));<br /> int i;<br /> for ( i = 0; i < N; ++i )<br /> a[i] = i;<br /> for ( i = 0; i < N; ++i )<br /> Swap(&a[i], &a[Rand(i, N-1)]);</p> <p>}</p> <p>static unsigned char bits[N/8] ;<br /> void Sort(int a[])<br /> {<br /> int i;<br /> for ( i = 0; i < N; ++i )<br /> {<br /> int index = a[i]/8;<br /> int offset = a[i]%8;<br /> bits[index] |= (0x01<<offset);<br /> }<br /> }</p> <p>void Output( int a[] )<br /> {<br /> int i;<br /> for ( i = 0; i < N/8; ++i )<br /> {<br /> unsigned char mask = 0x01;<br /> int cnt = -1;<br /> while ( ++cnt < 8)<br /> {<br /> if ( bits[i] & mask )<br /> printf("%d/n" , i*8 + cnt );<br /> mask <<= 1;<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> unsigned int array[N];<br /> Input(array) ;<br /> Sort(array);<br /> Output(array);<br /> return 0;<br /> }<br />