原理

把数字比较想象成每一位的多因素排序，只要保持每次排序的稳定即可，最高位权重最大最后排，这种是lsd类型，还有msd类型，通过分治递归来排序

代码实现

int getMaxBit(int* arr, int n)	//找数组中最高的有几位
{
	int maxBit = 0;
	int max = arr[0];
	int div = 1;
	for (int i = 1; i < n; i++) {
		if (max < arr[i]) {
			max = arr[i];
		}

	}

	if (max / div == 0)
	{
		return 1;
	}

	int i = 1;
	while (max / div != 0)
	{
		maxBit++;
		div = pow(10, i);
		i++;
	}

	return maxBit;
}

void sort(int* arr, int n)	//lsd 低位优先
{
	int* arrRes = (int*)malloc(sizeof(int) * n);
	int* arrCount = (int*)malloc(sizeof(int) * 10);	//0-9
	
	for (int i = 0; i < getMaxBit(arr, n); i++)	//从低位开始排序
	{
		int div = pow(10, i);
		
		for (int k = 0; k < 10; k++)
		{
			arrCount[k] = 0;
		}

		for (int j = 0; j < n; j++)		//对每位进行计数
		{
			arrCount[arr[j] / div % 10]++;
		}

		for (int k = 1; k < 10; k++)	//增量数组 开始进行增量排序
		{
			arrCount[k] = arrCount[k - 1] + arrCount[k];
		}

		for (int k = n - 1; k >= 0; k--)
		{
			arrRes[arrCount[arr[k] / div % 10] - 1] = arr[k];
			arrCount[arr[k] / div % 10]--;
		}

		memcpy(arr, arrRes, sizeof(int) * n);
	}

	free(arrRes);
	free(arrCount);
}

评价

稳定，值范围远小于数组个数的时候效率高