常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
计数排序概念
计数排序（Counting Sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
排序步骤：
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
动图展示：
代码实现
import java.util.Arrays; public class CountingSort { public static void main(String[] args) { //测试 int[] arr = {1, 4, 6, 7, 5, 4, 3, 2, 1, 4, 5, 10, 9, 10, 3}; sortCount(arr); System.out.println(Arrays.toString(arr)); // [1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10] } //计数排序 public static void sortCount(int[] arr) { //一：求取最大值和最小值，计算中间数组的长度： int max = arr[0]; int min = arr[0]; int len = arr.length; for (int i : arr) { if (i > max) { max = i; } if (i < min) { min = i; } } //二、有了最大值和最小值能够确定中间数组的长度（中间数组是用来记录原始数据中每个值出现的频率） int[] temp = new int[max - min + 1]; //三.循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组temp中 for (int i = 0; i < len; i++) { temp[arr[i] - min] += 1; } //四、遍历输出 //先循环每一个元素 在计数排序器的下标中 for (int i = 0, index = 0; i < temp.length; i++) { int item = temp[i]; 循环出现的次数 while (item-- != 0) { //以为原来减少了min现在加上min，值就变成了原来的值 arr[index++] = i + min; } } } }
时间复杂度
最优时间复杂度：o(n+k)
最坏时间复杂度：o(n+k)
稳定性：不稳定
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法
