最近在

《编程珠玑》 这本书上看到一种有趣的高效排序方法， 在这里介绍下。

排序的前提条件：

• 排序的数据中没有重复的数据
• 数据的分布应该相对集中些

这时可以利用位操作来进行排序.比如说如果你要对0~999中的100个数排序, 先创建一个125字节(1000位)长的数组c.如果你从待排序的数据中读到x, 则将c的第x位置一. 之后通过按位读c的值, 就可以输出排序好的数据了. 简单而高效, 不过就是条件有些苛刻.

 

附上一段C写的实现, 代码可以产生一个含100万个大于0小于1000万的无重复随机数的文件data.txt, 并输出一个排好序的文件sort.txt

1 #include  
     
        2 #include  
      
         3 #include  
       
          4 #include  
        
           5 #include  
         
            6 #include  
          
            7 #include 
           
             8 9 #define N 10000000 10 #define N_M 1000000 11 12 13 unsigned char a[8] = { 1, 2, 4, 8, 16, 32, 64, 128}; 14 15 int main(int argc, char *argv[]) 16 { 17 void randdata(unsigned char *const c); 18 int sort(); 19 unsigned char * const c = (unsigned char* const)malloc(N/8); 20 randdata(c); 21 sort(); 22 free(c); 23 return 0; 24 } 25 26 //产生100万个0~1000万间无重复的随机数 27 void randdata(unsigned char *const c) 28 { 29 int i, j, k, idx; 30 FILE *fp; 31 fp = fopen("data.txt", "w"); 32 assert(fp != NULL); 33 srand(time(NULL)); 34 for( idx = 0 ; idx < N_M ; ) 35 { 36 //随机数有位数限制 37 i = ((rand() << 16) + rand()) % N; 38 j = i / 8; 39 k = i % 8; 40 if((c[j] & a[k]) == 0) 41 { 42 idx++; 43 c[j] |= a[k]; 44 fprintf(fp, "%d\n", i); 45 } 46 } 47 fclose(fp); 48 } 49 50 //高效排序 51 int sort() 52 { 53 unsigned char c[N/8] = { 0}; 54 int i, j, k; 55 FILE *fp; 56 fp = fopen("data.txt", "r"); 57 assert(fp != NULL); 58 while(fscanf(fp, "%d", &i) > 0) 59 { 60 j = i / 8; 61 k = i % 8; 62 c[j] |= a[k]; 63 }; 64 fclose(fp); 65 fp = fopen("sort.txt", "w"); 66 for( i = 0, j = 0; i < N/8; i++ ) 67 { 68 if(c[i] == 0)continue; 69 else 70 { 71 for( j = 0 ; j < 8 ; j++ ) 72 { 73 if(c[i] & a[j])fprintf(fp, "%d\n", (i<<3)+j); 74 } 75 } 76 } 77 fclose(fp); 78 return 0; 79 }