輸入：一個最多包含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;