TOC

9.桶排序、排序总结相关题目分析 总览

笔记思维导图链接

算法与数据结构思维导图

参考左程云体系算法课程笔记
参考慕课网算法体系课程笔记

常见题目汇总：

题1：计数排序

题意

• 假设有n个样本数，数的范围是0-200，对这n个数进行排序

题解

• 范围小，故可以用计数排序，只需要准备200个桶，0-199，每个桶放一种样本数据，从小到大顺序
• 遍历一遍，将数据放到这200个桶类，再将200个桶依次倒出，就是最终排序的结果

代码实现

package class08;

public class Code03_CountSort {
	// only for 0~200 value
	public static void countSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 1. 找出样本的最大值，确定需要多少个桶
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
		}
		// 2. 每个样本对应创建一个桶，统计每个样本的次数
		int[] bucket = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			bucket[arr[i]]++;
		}
		// 3. 将桶按照顺序，依次导出样本，即最终排序结果
		int i = 0;
		for (int j = 0; j < bucket.length; j++) {
			while (bucket[j]-- > 0) {
				arr[i++] = j;
			}
		}
	}
}

复杂度分析

• 入桶，是O(n), 出桶也是O(n),故总的时间复杂度为O(n)

题2：基数排序

题意

• 数据非负，且为10进制。
• 例如最大数是321三位，将这些数进行排序

题解

• 先确定最大数是几位数，确定要处理几轮的入桶出桶操作
• 比如最大位是321，先处理个位数，按照个数数先排序，再处理十位、按照十位数值排序，最后处理第三位百位，最终排序的结果就是有序的
• 对于每次的入桶出桶可以优化，无需每次都要准备10个桶，装0-9种数，可以只准备两个辅助count，help
  • count，统计每个数出现的次数，类似计数排序，count[2]表示2出现的次数
  • count’，统计前几个数一共出现的次数，count’[2]表示0，1，2一共出现的次数
  • help数组处理最后从右往左遍历要处理的数，count’[2]出现5次，表明最后一个数应该出现在4位置，放置后，减一次，用来处理下个该位是2的数
• 每轮将help的结果交给原数组arr，每轮arr就排好序了

代码实现

package class08;

public class Code04_RadixSort {
	// only for no-negative value
	public static void radixSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		radixSort(arr, 0, arr.length - 1, maxbits(arr));
	}

	// 1. 获取最大数的位数
	public static int maxbits(int[] arr) {
		// 获取最大数
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
		}
		// 获取位数
		int res = 0;
		while (max != 0) {
			res++;
			max /= 10;
		}
		return res;
	}

	// arr[L..R]排序 , 最大值的十进制位的位数digit
	public static void radixSort(int[] arr, int L, int R, int digit) {
		final int radix = 10; // 每次都准备10个桶处理每一位的数
		int i = 0, j = 0;
		// 有多少个数准备多少个辅助空间
		int[] help = new int[R - L + 1];
		for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
			// 代码优化，省去10个桶，用两个数组count，count'来处理每次的进出操作
			// 用count统计当前位的数，出现的次数，类似计数排序
			int[] count = new int[radix]; // count[0..9]
			for (i = L; i <= R; i++) { // 遍历要处理的每个数
				// 103 1 3
				// 209 1 9
				j = getDigit(arr[i], d); // 找出当前位的数
				count[j]++;
			}
			// 处理count'数组，统计每个数应该占多少位，即count'[2]表示0，1，2一共出现的次数
			for (i = 1; i < radix; i++) {
				count[i] = count[i] + count[i - 1];
			}
			// 从右往左遍历，例如103，3一共出现了5次，则，103应该放在4位置
			for (i = R; i >= L; i--) {
				j = getDigit(arr[i], d);
				help[count[j] - 1] = arr[i]; // count[j]出现的次数，表明要占j个位置，最后一个位置是j- 1
				count[j]--;
			}
			// 对数组按照当前位进行排序，就是help数组最终放置的数的顺序
			for (i = L, j = 0; i <= R; i++, j++) {
				arr[i] = help[j];
			}
		}
	}

	// 获取第d位数的值
	public static int getDigit(int x, int d) {
		return ((x / ((int) Math.pow(10, d - 1))) % 10);
	}

}

复杂度分析