基数排序

radix_sort.c

//answer to <introduction to algorithms> 8.3-4
//主要思想是进制设置为n，所以位数就为2
int pow_int(int radix, int i)
{
	int result = 1;
	if(i<0)
		return -1;
	while (i--)
	{
		result *= radix;
	}
	return result;
}

int get_bit(int m, int i, int radix)
{
	return (m%pow_int(radix, i+1))/pow_int(radix, i);
}
//d为位数、radix为进制数
void radix_sort(int a[], int d,int len, int radix)
{
	int *count = (int*)malloc(sizeof(int)*len);
	int *tmp = (int*)malloc(sizeof(int)*len);
	int *remainder = (int*)malloc(sizeof(int)*len);
	memset(count, 0, sizeof(int)*len);
	int bit;
	for (int i=0; i<d; ++i)
	{
		for (int j=0; j<len; ++j)
		{
			bit = get_bit(a[j], i, radix);
			remainder[j] = bit;
			count[bit]++;
		}
		for (int j=1; j<len; ++j)
		{
			count[j] += count[j-1];
		}
		for (int j=len-1; j>=0; j--)//保持stable，所以倒着来
		{
			tmp[--count[remainder[j]]] = a[j];
		}
		for (int j=0; j<len; ++j)
		{
			a[j] = tmp[j];
			count[j] = 0;
		}
	}
	free(count);
	free(tmp);
	free(remainder);
}

int main()  
{  
	const int LEN = 15;
	int a[LEN] = {35, 48, 0, 8, 15, 80, 99, 3, 24, 168, 195, 224, 63, 120, 143};
	radix_sort(a, 2, 15, 15);
	return 0;  
}