代码

    void sort(unsigned *a,int n)
    {
    	const int LOGBLOCK=8;
    	const int BLOCK= (1 << LOGBLOCK);
    	const int BLOCK1=BLOCK-1;
    	typedef unsigned int u32;
    	typedef unsigned long long u64;
	    u32 *b = new u32[n];
        int sum[BLOCK];
        
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < n; i += 4)
        {
            sum[a[i] & BLOCK1]++;
            sum[a[i + 1] & BLOCK1]++;
            sum[a[i + 2] & BLOCK1]++;
            sum[a[i + 3] & BLOCK1]++;
        }
        for(int i = 1; i < BLOCK; i++)
            sum[i] += sum[i - 1];
        for(int i = n - 4; i >= 0; i -= 4)
        {
            b[--sum[a[i + 3] & BLOCK1]] = a[i + 3];
            b[--sum[a[i + 2] & BLOCK1]] = a[i + 2];
            b[--sum[a[i + 1] & BLOCK1]] = a[i + 1];
            b[--sum[a[i] & BLOCK1]] = a[i];
        }
        
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < n; i += 4)
        {
            sum[(b[i] >> 8) & BLOCK1]++;
            sum[(b[i + 1] >> 8) & BLOCK1]++;
            sum[(b[i + 2] >> 8) & BLOCK1]++;
            sum[(b[i + 3] >> 8) & BLOCK1]++;
        }
        for(int i = 1; i < BLOCK; i++)
            sum[i] += sum[i - 1];
        for(int i = n - 4; i >= 0; i -= 4)
        {
            a[--sum[(b[i + 3] >> 8) & BLOCK1]] = b[i + 3];
            a[--sum[(b[i + 2] >> 8) & BLOCK1]] = b[i + 2];
            a[--sum[(b[i + 1] >> 8) & BLOCK1]] = b[i + 1];
            a[--sum[(b[i] >> 8) & BLOCK1]] = b[i];
        }
        
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < n; i += 4)
        {
            sum[(a[i] >> 16) & BLOCK1]++;
            sum[(a[i + 1] >> 16) & BLOCK1]++;
            sum[(a[i + 2] >> 16) & BLOCK1]++;
            sum[(a[i + 3] >> 16) & BLOCK1]++;
        }
        for(int i = 1; i < BLOCK; i++)
            sum[i] += sum[i - 1];
        for(int i = n - 4; i >= 0; i -= 4)
        {
            b[--sum[(a[i + 3] >> 16) & BLOCK1]] = a[i + 3];
            b[--sum[(a[i + 2] >> 16) & BLOCK1]] = a[i + 2];
            b[--sum[(a[i + 1] >> 16) & BLOCK1]] = a[i + 1];
            b[--sum[(a[i] >> 16) & BLOCK1]] = a[i];
        }
        
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < n; i += 4)
        {
            sum[b[i] >> 24]++;
            sum[b[i + 1] >> 24]++;
            sum[b[i + 2] >> 24]++;
            sum[b[i + 3] >> 24]++;
        }
        for(int i = 1; i < BLOCK; i++)
            sum[i] += sum[i - 1];
        for(int i = n - 4; i >= 0; i -= 4)
        {
            a[--sum[b[i + 3] >> 24]] = b[i + 3];
            a[--sum[b[i + 2] >> 24]] = b[i + 2];
            a[--sum[b[i + 1] >> 24]] = b[i + 1];
            a[--sum[b[i] >> 24]] = b[i];
        }
   }

评测结果