一、二叉树核心知识点1. 满二叉树 完全二叉树满二叉树所有叶子节点都在同一层高度为n时叶子节点总数为 \(2^{n-1}\)每一层节点都填满。完全二叉树节点从上到下、从左到右依次填满最后一层允许右侧缺节点但左侧必须连续。存储可用数组顺序存储下标天然对应父子关系数组映射规则根节点下标 0下标i左孩子2*i1下标i右孩子2*i2下标i父节点(i-1)/2示例数组[5,7,4,2,0,3,1,6]对应图示完全二叉树。2. 二叉树遍历深度优先 DFS 广度优先 BFS1深度优先遍历DFS递归以根 A、左 B、右 C 的简单二叉树为例先序遍历根→左→右A → B → C中序遍历左→根→右B → A → C后序遍历左→右→根B → C → A2广度优先遍历BFS层序遍历从上到下、每层从左到右遍历示例树输出5 7 4 2 0 3 1 6和数组存储顺序完全一致。二、哈夫曼树 哈夫曼编码1. 基础概念节点的权字符出现的频次如a:3代表字母 a 出现 3 次路径根节点到叶子节点的通路路径长度路径上边的数量带权路径长度 WPL节点权值 × 路径长度哈夫曼树给定一组权值构造的WPL 最小的二叉树只有叶子带权、无度为 1 的节点树 WPL所有叶子节点带权路径长度之和图中示例 WPL662. 哈夫曼树构造规则取出权值最小的两个叶子节点生成新父节点父节点权 两子节点权之和将新父节点放回节点集合重复步骤 1直到只剩一个根节点左分支记0、右分支记1从根到叶子的路径数字串即为该字符哈夫曼编码|核心特性前缀编码任一字符编码不会是其他编码的前缀解码无歧义。三、四大基础排序算法1. 冒泡排序 BubbleSort原理相邻两个元素两两比较前 后则交换每一轮遍历会把当前未排序区间最大值 “冒泡” 到末尾共n-1轮每轮减少 1 次内层比较。时间复杂度最坏 / 平均 \(O(n^2)\)最好有序数组 \(O(n)\)可优化标识提前退出稳定性稳定排序相等元素相对顺序不变核心逻辑内层i对比i1逆序交换Java 完整代码package com.qby.sort; import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] arr {5,7,4,2,0,3,1,6}; sort(arr); System.out.println(Arrays.toString(arr)); } //冒泡排序 public static void sort(int[] arr) { //外层控制排序轮次共arr.length-1轮 for(int j0; jarr.length-1; j) { //内层每轮末尾j个元素已有序无需比较 for(int i0; iarr.length-1-j; i) { if(arr[i] arr[i1]) { //交换相邻元素 int temp arr[i]; arr[i] arr[i1]; arr[i1] temp; } } } } }2. 选择排序 SelectSort原理将数组分为「有序区」和「无序区」每一轮从无序区找到最小值记录下标一轮结束后交换到有序区末尾。时间复杂度固定 \(O(n^2)\)无论数组是否有序稳定性不稳定排序交换会打乱相等元素顺序特点交换次数远少于冒泡仅每轮 1 次交换Java 完整代码package com.qby.sort; import java.util.Arrays; public class SelectSort { public static void main(String[] args) { int[] arr {5,7,4,2,0,3,1,6}; sort(arr); System.out.println(Arrays.toString(arr)); } //选择排序 public static void sort(int[] arr) { //j为有序区末尾下标确定每轮要填充的位置 for(int j0; jarr.length-1; j) { int min arr[j]; int minIndex j; //遍历无序区查找最小值下标 for(int ij1; iarr.length; i) { if(arr[i] min) { min arr[i]; minIndex i; } } //最小值和无序区第一个元素交换 arr[minIndex] arr[j]; arr[j] min; } } }3. 直接插入排序 InsertSort原理数组左侧天然为有序区从第二个元素下标 1开始逐个取元素向前遍历有序区找到合适位置插入前侧元素大于当前值则后移遇到更小值直接终止循环。时间复杂度最坏逆序 \(O(n^2)\)最好完全有序 \(O(n)\)稳定性稳定排序适用小规模、接近有序的数组Java 完整代码package com.qby.sort; import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] arr {5,7,4,2,0,3,1,6}; sort(arr); System.out.println(Arrays.toString(arr)); } //直接插入排序 public static void sort(int[] arr) { //i指向待插入元素从1开始下标0天然有序 for(int i1; iarr.length; i) { //j从待插入元素前一位向前遍历有序区 for(int ji-1; j0; j--) { if(arr[j] arr[j1]) { //前值更大后移 int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; } else { //有序区找到正确位置直接退出 break; } } } } }4. 希尔排序 ShellSort插入排序优化版原理分组插入排序先取间隔grp 数组长度/2分组每组内部执行插入排序间隔不断折半缩小直到间隔 1退化为直接插入排序。思路先让数组整体趋近有序再做完整插入排序大幅减少元素移动次数时间复杂度平均优于 \(O(n^2)\)最坏 \(O(n^2)\)稳定性不稳定排序跨组交换会打乱相等元素Java 完整代码package com.qby.sort; import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] arr {5,7,4,2,0,3,1,6}; sort(arr); System.out.println(Arrays.toString(arr)); } //希尔排序 public static void sort(int[] arr) { //grp分组间隔初始长度一半每次折半直到0 for(int grp arr.length/2; grp 0; grp / 2) { //i遍历每组第二个及之后元素 for(int igrp; iarr.length; i) { //组内向前插入排序步长grp for(int j i - grp; j 0; j - grp) { if(arr[j] arr[jgrp]) { int temp arr[j]; arr[j] arr[jgrp]; arr[jgrp] temp; } else { break; } } } } } }5. 基数排序 RadixSort桶排序拓展稳定排序原理准备编号0~9共 10 个桶按低位优先排序先按个位分桶收集再按十位、百位…… 直到最高位处理完成每一轮数字按当前位数值放入对应桶全部入桶后按桶顺序取出覆盖原数组循环次数 数组中最大值的数字位数时间复杂度\(O(k \times n)\)n为数组长度k为数字最大位数空间复杂度\(O(n)\)需要二维桶数组存储临时数据稳定性稳定排序同数字入桶先后顺序不变限制仅支持非负整数排序图示示例数组[7,11,19,20,29,40,48,53,62,75,99,130,176,200]Java 完整代码package com.qby.sort; import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arr {51,72,4,32,40,53,61,106,8,99,105,3}; sort(arr); System.out.println(Arrays.toString(arr)); } //基数排序 public static void sort(int[] arr) { //1. 找到数组最大值确定最高位数 int max arr[0]; for(int i 0; i arr.length; i) { if(arr[i] max) { max arr[i]; } } //获取最大值的位数 int maxLen (max ).length(); //2. 初始化10个桶每个桶最多存全部数组元素 int[][] bucket new int[10][arr.length]; //记录每个桶当前存放元素个数 int[] elementCount new int[10]; //n代表当前取哪一位个位1、十位10、百位100... int n 1; //循环处理每一位个位→十位→百位... for(int h 0; h maxLen; h) { //步骤1所有数字按当前位放入对应桶 for(int i 0; i arr.length; i) { //取出当前数字的对应位数值0~9 int element arr[i] / n % 10; //该桶已存数量作为存入下标 int count elementCount[element]; bucket[element][count] arr[i]; elementCount[element]; } //步骤2按桶顺序取出数据覆盖原数组 int index 0; for(int k 0; k elementCount.length; k) { //当前桶有数据才取出 if(elementCount[k] ! 0) { for(int l 0; l elementCount[k]; l) { arr[index] bucket[k][l]; index; } } //清空当前桶计数给下一轮位排序复用 elementCount[k] 0; } //进位处理下一位 n n * 10; } } }四、五大排序对比总结表排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性核心特点冒泡排序\(O(n^2)\)\(O(n)\)优化\(O(n^2)\)\(O(1)\)稳定相邻交换容易实现效率低选择排序\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)\(O(1)\)不稳定交换次数少比较次数固定直接插入排序\(O(n^2)\)\(O(n)\)\(O(n^2)\)\(O(1)\)稳定接近有序数据效率极高希尔排序\(O(n^{1.3})\)\(O(n)\)\(O(n^2)\)\(O(1)\)不稳定插入排序优化大数据量更快基数排序\(O(kn)\)\(O(kn)\)\(O(kn)\)\(O(n)\)稳定基于桶分配只支持整数无比较排