Hark的数据结构与算法练习之基数排序

算法说明

基数排序是基于计数排序的，所以看这个之前要先看一下计数排序对于理解基数排序是很有帮助的（发现计数和基数的音节几乎一致啊）。这个我有写，请点击。

OK，现在你肯定已经熟悉了计数排序，那么我就来说一下基数排序。

所谓基数排序，其实就是分别对数字的个位，十位，百位，百位。。。。分别进行计数排序。

当然可以从个位往上进行计数排序，也可以从高位往个数计数排序，这里我们使用个位往上计数排序的方法。

话说，我想了好半天，不知道从哪里入手说基排（鸡排，哈哈）的思路……好蛋疼

这样，先从与计数排序的区别说起吧，区别在于计数排序是直接对数字进行排序。而基数排序是分别对个位，十位，百位。。。进行排序的。

然后，每个位数中，都有0至9共10个数字（即个数时，其实就是10个数字做排序；十数时，其实也是对10个数字做排序），接着我们对每个数字中的数字进行计数排序（好绕口，意思就是说，当进行个数排序时，个位为1时，所以个位为1的数字进行计排，例如11，21，31，221，411等等）。

所以我们申请的是二维数组int[][] radixBucket = new int[10][length]; （代码27行）第一维的10存储的就是我们每次都是对10个数分别进行计排。第二维存储的就是对应的要排序的数字啦

同时，因为我们要保证数字的稳定性，当我们把低位的数字进行计排后，要把低位数字输出至原始数组中，然后再进行高位排序。

OK，解释到现在不知道有没有说清楚了。。。我发现我语言表达能力还真的是很差劲啊。

我觉得看代码可能会更清楚些，代码上也有注释，代码如下：

代码

使用的是java

/*
 * 基数排序
 */
public class RadixSort {
	public static void main(String[] args) {
		int[] arrayData = { 2, 3, 1, 5, 6, 7, 4, 65, 42 };
		RadixSortMethod(arrayData, 100);
		for (int integer : arrayData) {
			System.out.print(integer);
			System.out.print(" ");
		}
	}

	/*
	 * arrayData - 要排序的数据 height - 要排序的步长 如果100，则只排序个位十位
	 */
	public static void RadixSortMethod(int[] arrayData, int height) {
		int maxNum = 0; // 最大值，用于存储桶数据临时数组空间大小
		for (int data : arrayData) {
			if (data > maxNum) {
				maxNum = data;
			}
		}

		int step = 1;
		int length = arrayData.length;
		int[][] radixBucket = new int[10][length]; // 二维数组，排序的容器
		int[] arrayTemp = new int[maxNum + 1]; // 这个是每个桶中的数字个数
		int num;
		int index = 0;
		while (step < height) {
			for (int data : arrayData) {
				// 当step=1时统计个数，这时取出个位的数字。
				// 当step=10时，统计十数，这时取出十位的数字
				num = data / step % 10;
				radixBucket[num][arrayTemp[num]] = data;
				arrayTemp[num]++;
			}

			for (int i = 0; i < 10; i++) {
				if (arrayTemp.length > i && arrayTemp[i] != 0) {
					for (int j = 0; j < arrayTemp[i]; j++) {
						arrayData[index] = radixBucket[i][j];
						index++;
					}
					arrayTemp[i] = 0; // 将当前数字个数重置为0，用于下次的统计
				}
			}

			step *= 10;
			index = 0;
		}
	}
}

结果

1 2 3 4 5 6 7 42 65

时间复杂度：

假设步长是s,待排序数组长度是n,数字最大值是m

那么时间复杂度就是O(s(n+(10*m)))=O(s(m+n))

空间复杂度：

待排序数组长度是n,数字最大值是m。

那么空间复杂度就是O(10*n+(m+1))=O(m+n)

稳定性：是稳定的

应用场景：

针对最大值相对比较小的正整数。