基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部分资讯，将要排序的元素分配至“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为 $O\left(Nlog\right(r\left)m\right)$O(Nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。—— 百度百科

基本做法

最简单和最入门的情况，就是对正整数进行排序，然后划分出【0，9】的桶。首先我们需要找出需要排序的数组中数位长度最长的数，这个被找出来的数值，在接下来就是我们需要循环排序的次数，而这每一次循环，其实就是为了取数在对应数位上的数，比如取83427的第3位，值位4。第一次循环，遍历数组中每个数的第一位取出，放入对应的【0，9】桶中的一个，遍历结束之后，再把【0，9】号桶中的数依次取出，重新放入数组中，目前的数组，对于第一个数位而言，已经是有序数组了。而之后的操作如第一个一般，只是数位在往高位变而已，直到最后循环结束，数组已经是一个整体有序的数组了，即每一次的循环都在矫正数组中的数的排列位置。

代码说明

int midArr[LEN]做为中介数组，为了每次循环后，重新对源数组进行更新，int digitsHave[10]是说明各个桶中数的数量，int digitsStart[10]则是为了之后说明当前数该排的位置。

先取数组长度，然后找数组中数的最长数位，之后就是循环对应的次数，而每次循环，取出数对应数位的值，放入到桶中（逻辑上），而digitsHave则是要更新对应桶中数的数量。之后计算每个桶中的数是从第几个位置开始的，把值放入digitsStart，以方便之后对midArr数组的赋值。最后自然就是取出对应数位，同时依靠digitsStart的值，知道要插入的位置，然后进行插入，再是更新下个同个桶中数的插入位置即可。当前循环的最后，更新源数组，再是进入下一次循环。循环出来以后，整个源数组已经是一个有序数组了。

代码

class Solution {
public:
	Solution() {}
	~Solution() {}
	vector<int> sortArray(vector<int>& nums) {
		const int LEN= nums.size();
		int midArr[LEN];
		int digitsHave[10];
		int digitsStart[10];
		int maxDigits = 0;

		memset(midArr, 0, sizeof(midArr));
		for (auto val : nums) {
			maxDigits = max(maxDigits, digits(val));
		}
		int getDigit = 1;
		while (maxDigits--) {
			memset(digitsHave, 0, sizeof(digitsHave));
			for (auto val : nums) {
				int x = val / getDigit % 10;
				digitsHave[x]++;
			}
			memset(digitsStart, 0, sizeof(digitsStart));
			for (int i = 1; i < 10; ++i) {
				digitsStart[i] = digitsStart[i - 1] + digitsHave[i - 1];
			}
			for (auto val : nums) {
				int x = val / getDigit % 10;
				midArr[digitsStart[x]++] = val;
			}
			for (int i = 0; i < LEN; ++i) {
				nums[i] = midArr[i];
			}
			getDigit *= 10;
		}
		return nums;
	}

	int digits(int num) {
		int len = 0;
		for (; num; num /= 10) len++;
		return len;
	}
};