输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果在输入文件中有任何重复整数出现就是致命错误。没有其他数据与该整数相关联
输出：按升序排列的 输入整数的列表。
约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。
从0开始解决这个问题的话，可以把它分为两个部分：首先随机生成K个小于N的数；再对这K个数排列。
系统参数：GCC:#pragma pack(4) 小端模式 -std=c99
一、位图思想（bit-map）
引入：如何用一个Byte表示尽可能多的无重复的数？
一个bit只能表示0或1，两个bit能表示2(01)和3(11)，4则要3个bit，这样的话8个bit只能表示0-3四个数字。
我们得换个思路，暂且先丢掉头脑中的进制，用小学生排队的思想，拍第一的报1，第二的报2…嗯哼，我们一字节8个bit，这样就表示了8个数字。
所以，让我们走进内存中，丢掉进制的羁绊，来数数这个bit排第几。
这张图以左边为低位的话，就和作者系统的小端模式契合
二、生成K个小于N的不重复随机数
基于位图的思想，我们可以用K个bit来表示这么多个数字。由于存在内存对齐等问题，我声明了一个32Bit的union结构，为了更好的对这32个bit进行操作，我把它分为了4个char，而两个short则是为了测试与debug。
- typedef union str{
- short element[2];
- char ele_ch[4];
- }Bits;
- int n = 0;
- printf("Please input range:\n");
- scanf("%d",&n);
- const int N = n/32+1;
- Bits arr[N];
- memset(arr,0,sizeof(arr));
- int k = 0;
- printf("Please input count of number,");
- do{
- printf("this number is less than %d\n",n);
- scanf("%d",&k);
- }while(k>n);
所以，当生成了一个随机数num后，就把内存中第num位置为1，以表示该数已存在，同理，检查是否有重复时，只需看该位的值。
对检查该位的值以及修改该位的值这两个操作，用两个函数表示。
- /* 查看该位是否为0 *
- * 输入：一个整数n *
- * 返回：bit[n]的值 */
- bool bitValue(int num,Bits arr[],...);
- /* 把某位设为n *
- * 输入：一个整数n代表的地址 *
- * 操作：将该地址上的值设为1 */
- void setBitValue(Bits arr[],...);
所以我们可以用这样一个循环来寻找随机数。用rand得到随机数后，再判断这个数是否出现过，如果没出现过的话就把那一位设为1，并输出。
- while(k)
- {
- int value = rand()%n;
- if(bitValue(value,arr)==0)
- {
- setBitValue(arr,n);
- printf(" %d",value);
- k--;
- }
- }
由于申请的内存是以4B(32bit)为一个单位，所以N个数字在内存中有如下x种情况：
1.N为32 的倍数，则申请到的数组全满。（N = 32*n）
2.除最后一个数组外，其余数组全满。也分两种情况：
①.最后一个数组中，前x个char全满，后一个char被用到的bit小于8个。（N = n*32+8*x+bit）
②. 最后一个数组中，恰好满了x个char。（N = n*32+8*x）
所以bool bitValue(int num ,Bits arr[])接受两个参数，一个是数组首地址，一个是待求的数字（0~n-1）
- bool bitValue(int num,Bits arr[])
- {
- if(num!=0)
- int arr_n = num/(32); //在第几个数组
- int arr_b = num-arr_n*32;
- short arr_ch = 0; //在第几个char里
- if(arr_b)
- {
- arr_ch = arr_b/8;
- }
- int arr_c_b = arr_b; //第几个bit
- while(arr_c_b>=8)
- arr_c_b -= 8;
- return (arr[arr_n].ele_ch[arr_ch] & arr2n[arr_c_b]);
- else //处理0
- return (arr[num].ele_ch[0] & arr2n[0]);
-
}
又因为是以8bit为一单位，所以创建数组全局数组 arr2n[8]，用来存储2^0~2^7的值。在小端模式下，恰好是左第一位为2^0。
-
const int arr2n[8]={1,2,4,8,16,32,64,128};
所以void setBitValue()也和bool bitValue()过程类似，找到n在内存中的位置，在更新它的值。不过在这个函数里重复计算位置不划算，所以我们可以在第一次计算时把位置信息保存起来，要更新数据时再传给函数。
这里申明一个位置结构，用来存储一个数字在内存中相对于数组结构的位置。
- typedef struct bitLoca{
- int n_arr;
- int n_ch;
- int n_bit;
- }bitLoca;
然后在在主函数的while循环里加上它，并修改两个函数的参数：
- int main(void)
- //...
- while(key)
- bitLoca bitL;
- int value = rand()%n;
- if(bitValue(value,arr,&bitL)==0)
- {
- setBitValue(arr,&bitL);
- printf("%d\n",value);
- key--;
- }
- //...
- 更新后的bitValue():
- bool bitValue(int num,Bits arr[],bitLoca *bitL)
- int arr_n = num/(32);
- int arr_c_b = arr_b;
- bitL->n_arr = arr_n;
- bitL->n_ch = arr_ch;
- bitL->n_bit = arr_c_b;
- bitL->n_arr = 0;
- bitL->n_ch = 0;
- bitL->n_bit = 0;
- 这样的话setBitValue()也就简单多了：
- /* 把某位设为n *
- void setBitValue(Bits arr[],bitLoca *bitL)
- arr[bitL->n_arr].ele_ch[bitL->n_ch] = arr[bitL->n_arr].ele_ch[bitL->n_ch] | arr2n[bitL->n_bit];
- 写到这里，输出不重复的随机数部分就能跑了，不过有一个小问题，有关rand()函数的。
-
int __cdecl rand(void);
rand()函数产生一个0到RAND_MAX的伪随机数，而在楼主的系统里，RAND_MAX是32767，就是2^15。所以题目要求的k<1000000就死活打不成了，为了解决这个问题，我不假思索的写了这样一条语句：
-
int value = rand()*rand()%n;
再跑一次，ok，解决了…(\简单粗暴)
运行一下。
ok，第一部分——找随机数解决。
三、排序
其实到了现在这一步，这已经不适合叫排序了，倒更像是遍历。从0开始，把申请到的内存全过一遍，值为1 就输出。这一步只需要注意边界的问题，用for循环就可以搞定。
不过在这个地方我还是用的简单粗暴（不动脑子）的办法，先求出最后一个数字所在的位置（arr\ch\bit），再分情况依次遍历，所以写的又长又臭。
- void bitSort(Bits arr[],int n)
- int max_arr = n/32;
- int tbit = n-max_arr*32;
- short max_ch = 0; //在第几个char里
- if(tbit)
- max_ch = tbit/8;
- int max_bit = tbit%8;
- for(int tarr = 0;tarr<=max_arr;tarr++)
- if(tarr != max_arr) //全满的数组
- for(int tch = 0;tch<4;tch++)
- {
- for(int tbit = 0;tbit<8;tbit++)
- {
- if(arr[tarr].ele_ch[tch] & arr2n[tbit])
- {
- printf("%d ",tarr*32+tch*8+tbit);
- }
- }
- }
- else //非全满的数组
- for(int tch = 0;tch<=max_ch;tch++)
- if(tch != max_ch) //全满的ch
- printf("tarr = %d ,tch = %d ,tbit = %d : \n",tarr,tch,tbit);
- }
- else //非全满ch
- for(int tbit = 0;tbit<max_bit;tbit++)
- 再运行一遍：
位图排序思想及代码详解
四、下一步
仓促之下完成的代码，不可避免的留下了许多可以提升的空间，以下几点是重构、优化时必须要考虑的问题。
1.随机数分布不均的问题：rand()*rand()简单粗暴，不过从概率的角度上讲只能称之为无脑。
2.遍历的优化。
3.代码的封装：寻找一个数的地址的功能可以封装成一个函数。
4.位运算可以用位移操作代替。
五、代码
- /*
- 163_union_1_sort.c
- author:Magic激流
- 2018-5-26
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #include <windows.h>
- #include <stdbool.h>
- short element[2];
- char ele_ch[4];
- }Bits;
- int arr2n[8]={1,2,4,8,16,32,64,128};
- * 返回：bit[n]的值 */
- int arr_n = num/32;
- for(int tbit = 0;tbit<8;tbit++)
- if(arr[tarr].ele_ch[tch] & arr2n[tbit])
- printf("%d ",tarr*32+tch*8+tbit);
- int main (void)
- srand(time(NULL));
- while(k)
- bitLoca bitL;
- int value = rand()*rand()%n;
- // int value = rand()%n;
- if(bitValue(value,arr,&bitL)==0)
- setBitValue(arr,&bitL);
- printf("%d ",value);
- k--;
- printf("\nSort:\n");
- bitSort(arr,n);
- return 0;