基数排序(java实现)

  • 思路
  • 算法属性
  • 代码

 

思路

将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

  • 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。
  • 从最低位开始,依次进行一次排序。
  • 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

算法属性

参考文章:【点我】

时间复杂度:基数排序中r为基数,d为位数。时间复杂度为O(d(n+r))

空间复杂度:对于任何位数上的基数进行“装桶”操作时,都需要n+r个临时空间。

稳定性:相同的数字并不需要交换位置。所以基数排序是稳定的算法。

排序类型时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性复杂性
交换排序O(d(n+r))O(d(n+r))O(d(n+r))O(n+r)稳定较复杂

代码

public static void main(String[] args) {
	int[] a = { 1, 5, 6, 3, 2, 4 };
	digitSort(a, a.length);
	print(a);// 自定义输出数组
}

public static int maxBit(int[] inputList) {// 返回数组中最大的位数(如获取123的1所在的位数,结果返回3)
	int maxData = inputList[0];
	for (int i = 0; i < inputList.length; i++) {
		if (inputList[i] > maxData)
			maxData = inputList[i];
	}
	int bitsNum = 0;
	while (maxData > 0) {
		bitsNum++;
		maxData /= 10;
	}
	return bitsNum;
}

public static int digit(int num, int d) {// 返回数的第d位的数字(如123第2位的数字是2)
	int pow = 1;
	while (--d > 0) {
		pow *= 10;
	}
	return num / pow % 10;
}

public static void digitSort(int[] inputList, int n) {
	int[] bucket = new int[n];// 临时数组,来保存排序过程中的数字
	int[] count = new int[10];// 位计数器,当前位是0的有多少个,是1的有多少个...
	for (int d = 1; d <= maxBit(inputList); d++) {// 从低位往高位循环
		for (int i = 1; i < 10; i++) {
			count[i] = 0;// 计数器清零
		}
		for (int i = 0; i < n; i++) {// 统计各个桶中的个数
			count[digit(inputList[i], d)]++;
		}
		for (int i = 1; i < 10; i++) {// count[i]表示第i个桶的右边界索引
			count[i] += count[i - 1];
		}
		// 这里只能从数组后往前循环,因为排序时还需保持以前的已排序好的顺序,不应该打乱原来已排好的序
		for (int i = n - 1; i >= 0; i--) {
			int k = digit(inputList[i], d);// 求出关键码的第k位的数字, 例如:576的第3位是5
			bucket[count[k] - 1] = inputList[i];// 放入对应的桶中,count[j]-1是第j个桶的右边界索引
			count[k]--;// 对应桶的装入数据索引减一
		}
		for (int i = 0; i < n; i++) {// 数组放到inputList中
			inputList[i] = bucket[i];
		}
	}
}