Java教程

算法与数据体系课笔记之- 9.桶排序、排序总结相关题目

本文主要是介绍算法与数据体系课笔记之- 9.桶排序、排序总结相关题目,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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);
	}

}

复杂度分析

在这里插入图片描述
这篇关于算法与数据体系课笔记之- 9.桶排序、排序总结相关题目的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!