基数排序 C++ （正负数均可 + 详解）

Theory:

​ 从低位到高位, 每次分两步：

然后循环执行上述步骤k次，其中k是所有数中最大的数位

Attention:

1. 如果全是非负数,那么只需要开radix个桶；
2. 有负数时开20个(这里是对于十进制数), 因为有 -ab % 10 = -b，把[-9, -1]映射到[1, 9]，把[0, 9]映射到[10, 19] （即加上10）

Code:

int a[7] = {1, 0, 1, 8, -1, 0, -1}, n = 7;         //测试数据

int tank[20][100];         //20个桶, tank[x][i]表示当前位是x的第i个数，这里tank[x][0]表示tank[x]这个数组有多少个元素,故存数据时从tank[x][1]开始存

//基数排序（基数就对应着 进制数）
void radixSort(){       
    int k = 1, d = 1;        //k是最大位数，d是当前位的权重，即1, 10, 100.....
    
    //计算最大位数, 公式 k = (int)log10(x) + 1，注意x要大于0
    for(int i = 0; i < n; i++) 
		if(a[i])        //非零时, 计算 |a[i]| 的位数
            k = max((int)log10(abs(a[i])) + 1, k);
	
	while(k--){            //循环k次
		memset(tank, 0, sizeof(tank));        //每次循环先把tank清零
		
		for(int i = 0; i < n; i++){        //枚举n个数
			int x = a[i] / d % 10 + 10;		 //得到当前位的值x（记得要加10）
			tank[x][++tank[x][0]] = a[i];     //放到第x个桶里面，注意是++tank[x][0]
		}
		
		int cnt = 0;
		for(int i = 0; i < 20; i++)       //枚举20个桶
            //依次拿出每个桶里面的值[1, tank[i][0]], 注意取出顺序和放入顺序是一样的（类似队列,先进先出），故基数排序稳定
			for(int j = 1; j <= tank[i][0]; j++)   
				a[cnt++] = tank[i][j];        //回收
		d *= 10;        //权重 * 10
	} 
}