• 计数&桶&基数排序算法

    基数排序 vs 桶排序 vs 计数排序：

    这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异。

    • 计数排序：每个桶只存储一个类型值，但是数量不限
    • 桶排序：存储一定范围的值
    • 基数排序：根据每一位的关键字来分配桶

    在这里插入图片描述

    一、计数排序

    1、算法描述：

    计数排序，不是基于元素比较，而是利用数组下标确定元素的正确位置。

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

    适用范围：量大但是范围小。

    算法的步骤如下：

    • 1）找出待排序的数组中最大和最小的元素
    • 2）统计数组中每个值为 i的元素出现的次数，存入数组 C的第 i项
    • 3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
    • 4）反向填充目标数组：将每个元素 i放在新数组的第 C(i)项，每放一个元素就将 C(i)减去1。

    2、示例

    	public static void main(String[] args) {
		int[] array = { 8, 5, 2, 9, 3, 15, 5, 9999, 2, 7, 5 };
		countingSort(array);
		System.out.println("最终排序结果为：" + Arrays.toString(array));
	}


	public static void countingSort(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}
		int maxVal = array[0];
		int minVal = array[0];
		// 1.找出最大最小值
		for (int i = 1; i < array.length; i++) {
			if (array[i] < minVal) {
				minVal = array[i];
			}
			if (array[i] > maxVal) {
				maxVal = array[i];
			}
		}
		// 2.已经找到最大最小值，将数字出现的次数放进对应位置的数组里
		int[] temp = new int[maxVal - minVal + 1]; // 默认元素都为0
		for (int i = 0; i < array.length; i++) {
			temp[array[i] - minVal]++;  //对应值次数加1。
		}
		// 3.把排序好的放回array里
		int arrayIndex = 0;
		for (int i = 0; i < temp.length; i++) {
			while (temp[i] > 0) { //次数大于0写入
				array[arrayIndex] = i + minVal;
				temp[i]--; //对应值次数减1
				arrayIndex++;
			}
			System.out.println("第 " + i + " 次的排序结果为：" + Arrays.toString(array));
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    二、桶排序

    1、算法描述：

    桶排序是计数排序的升级，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素。

    通过函数的某种映射关系，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序（可以使用别的排序算法或是以递归方式继续使用桶排序），最后将非空桶中的元素逐个放入原序列中。

    高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

    • 在额外空间充足的情况下，尽量增大桶的数量
    • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

    同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

    什么时候最快：

    • 当输入的数据可以均匀的分配到每一个桶中。

    什么时候最慢：

    • 当输入的数据被分配到了同一个桶中。

    算法的步骤如下：

    • 1）遍历原始数组，找到数组中的最大值和最小值，可以确定出数组所在范围min~max
    • 2）根据数据范围确定桶的数量
      • 若桶的数量太少，则桶排序失效
      • 若桶的数量太多，则有的桶可能，没有数据造成空间浪费

    所以桶的数量由我们自己来确定，但尽量让元素平均分布到每一个桶里，这里提供一个方式（一般左闭右开）：

    (最大值 - 最小值)/每个桶所能放置多少个不同数值+1

    • 3）再次遍历原始数组，利用映射函数将元素分配到各个桶中
    • 4）遍历桶数组，把排序好的元素放回array中

    2、示例

    	public static void main(String[] args) {
		int[] array = { 8, 5, 2, 9, 3, 15, 25, 9, 2, 7, 5 };
		int[] res = bucketSort(array, 5);
		System.out.println("最终排序结果为：" + Arrays.toString(res));
	}

	public static int[] bucketSort(int[] array, int bucketSize) {
		if (array == null || array.length <= 1) {
			return array;
		}

		int minValue = array[0];
		int maxValue = array[0];
		// 1.找出最大最小值
		for (int value : array) {
			if (value < minValue) {
				minValue = value;
			} else if (value > maxValue) {
				maxValue = value;
			}
		}

		// 2.获取桶的数量
		int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1; // Math.floor()向下取整
		// 创建桶并初始化
		int[][] buckets = new int[bucketCount][0];

		// 3.利用映射函数将元素分配到各个桶中
		for (int i = 0; i < array.length; i++) {
			int index = (int) Math.floor((array[i] - minValue) / bucketSize);
			buckets[index] = arrAppend(buckets[index], array[i]);
		}

		// 4.遍历桶数组，把排序好的元素放回array中
		int arrIndex = 0;
		for (int i = 0; i < buckets.length; i++) {
			int[] bucket = buckets[i];
			if (bucket.length <= 0) {
				continue;
			}
			if (bucket.length == 1) {
				array[arrIndex++] = bucket[0];
			} else {
				// 对每个桶进行排序，这里使用了插入排序
				insertionSort(bucket);
				for (int value : bucket) {
					array[arrIndex++] = value;
				}
			}
			System.out.println("第 " + i + " 次的排序结果为：" + Arrays.toString(array));
		}
		return array;
	}

	private static void insertionSort(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}

		for (int i = 1; i < array.length; i++) {
			int temp = array[i];
			int j = i - 1;
			for (; j >= 0; j--) { // 从尾到头比较
				if (temp < array[j]) {
					array[j + 1] = array[j]; // 数据往后移动
				} else {
					break;
				}
			}
			array[j + 1] = temp;
		}
	}

	/**
	 * 自动扩容，并保存数据
	 *
	 * @param arr
	 * @param value
	 */
	private static int[] arrAppend(int[] arr, int value) {
		arr = Arrays.copyOf(arr, arr.length + 1);
		arr[arr.length - 1] = value;
		return arr;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    三、基数排序

    1、算法描述：

    基数排序属于“分配式排序”，又称“桶子法”。

    按照从右往左的顺序，依次将元素的每一位都当做一次关键字（循环次数），通过关键字的各个位的数值，将要排序的元素分配至某些“桶中”，来达到排序的作用。
    同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。

    基数排序是桶排序的扩展，基数排序不是基于比较的算法。

    基数是什么意思？

    • 对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基（关键字），
    • 同理二进制数字的基为2；
    • 对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

    基数排序有两种方法：

    • MSD 从高位开始进行排序（从左往右）
    • LSD 从低位开始进行排序（从右往左）

    2、示例

    下面以整数数组为例。（如果是小数可转换为整数处理注意：输出时记得转换为小数）。

    对于十进制整数，每一位的大小范围为0~9的数，总共10种可能，于是可以准备十个桶，然后放到对应的桶里，然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。

    	public static void main(String[] args) {
		int[] array = { 82, 50, 0, 9, 100, 155, 55, 9999, 14, 73, 25 };
		radixSort(array);
		System.out.println("最终排序结果为：" + Arrays.toString(array));
	}

	/**
	 * 基数排序
	 *
	 * @param array
	 */
	public static void radixSort(int[] array) {
		if (array == null || array.length <= 1) {
			return;
		}
		// 1.获取数组最大值
		int maxValue = getMax(array);
		System.out.println("max = " + maxValue);

		/**
		 * 2.创建桶并初始化。也可以使用二维数组作为桶存储。<br/>
		 * 这里关键字位置上的数值[0,9]，所以定义size=10，将关键字位置上数值相同的元素归类存储在桶中。
		 */
		ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
		for (int i = 0; i < 10; i++) {
			bucket.add(new ArrayList<>());
		}
		/**
		 * 3.基于关键字排序<br/>
		 * 按照从右往左的顺序，重复执行d次（若关键字为{1,10,100}，则d=3），每一轮排序都基于上轮排序后的结果
		 */
		for (int exp = 1; exp < maxValue; exp *= 10) {
			radixOne(array, exp, bucket);
			//radixOne2(array, exp);
			System.out.println("第 " + exp + " 次的排序结果为：" + Arrays.toString(array));
		}
	}

	/**
	 * “归类”和“收集”
	 * 
	 * @param array
	 *            - 待排序的数组
	 * @param exp
	 *            - 关键字
	 * @param bucket
	 *            - 存储桶
	 */
	private static void radixOne(int[] array, int exp, ArrayList<ArrayList<Integer>> bucket) {
		// 将关键字位置（个位/十位/百位）上数值相同的元素归类存储在桶中
		for (int i = 0; i < array.length; i++) {
			// 每个元素除以关键字后，就得到当前关键字位置上的数值
			int num = (array[i] / exp) % 10;
			// 把元素归类存储到对应的桶中
			bucket.get(num).add(array[i]);
		}
		// 从第一个位置依次把桶中的元素重新放回原数组中，并把桶中的元素清空
		int index = 0;
		for (int i = 0; i < bucket.size(); i++) {
			// 桶中对应的元素
			ArrayList<Integer> list = bucket.get(i);
			for (int m = 0; m < list.size(); m++) {
				// 从第一个位置依次放回原数组中
				array[index++] = list.get(m);
			}
			// 清除桶中的元素
			bucket.get(i).clear();
		}
	}

	/**
	 * 获取数组最大值
	 * 
	 * @param array
	 *            待排序数组
	 * @return 最大值
	 */
	public static int getMax(int[] array) {
		int maxValue = array[0];
		for (int i = 1; i < array.length; i++) {
			if (maxValue < array[i]) {
				maxValue = array[i];
			}
		}
		return maxValue;
	}

	/**
	 * “归类”和“收集”
	 * @param array 待排序数组
	 * @param exp 关键字
	 * @author zpr
	 */
	public static void radixOne2(int[] array, int exp){

		// 辅助存放数组
		int[][] bucket = new int[10][array.length];
		// 辅助记录数组
		int[] orderNum = new int[10];

		for (int arr : array) {
			// 每个元素除关键字后，就得到当前关键字位置上的数值
			int num = (arr / exp) % 10;
			// 存入对应辅助序列
			bucket[num][orderNum[num]] = arr;
			// 对应数值类型记录+1
			orderNum[num]++;
		}

		int index = 0;
		// 遍历二维辅助数组
		for (int i = 0; i < bucket.length; i++) { // 10个辅助序列
			for (int j = 0; j < orderNum[i]; j++) { // 每个数值类有几个元素
				// 从第一个位置依次放回原序列
				array[index++] = bucket[i][j];
			}
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118

    参考文章：

    – 求知若饥，虚心若愚。

  • 相关阅读:
    Java本地高性能缓存的几种实现方式
    linux系统备份及还原
    leetcode做题笔记2760. 最长奇偶子数组
    财务会计与管理会计（二）
    【Git企业开发】第一节.Git 初识
    Win10编译chrome
    『网易实习』周记(四)
    06贪心：跳跃游戏
    【面试】你有使用过链路追踪技术吗？
    Pyglet综合应用｜推箱子游戏地图编辑器之图片跟随鼠标
  • 原文地址：https://blog.csdn.net/qq_42402854/article/details/125395740