企业官网建设流程全解析

一、二叉树核心知识点

1. 满二叉树 & 完全二叉树

1. 满二叉树所有叶子节点都在同一层；高度为n时，叶子节点总数为 \(2^{n-1}\)，每一层节点都填满。
2. 完全二叉树节点从上到下、从左到右依次填满，最后一层允许右侧缺节点，但左侧必须连续。
   • 存储：可用数组顺序存储，下标天然对应父子关系
   • 数组映射规则（根节点下标 0）：
     • 下标i左孩子：2*i+1
     • 下标i右孩子：2*i+2
     • 下标i父节点：(i-1)/2

示例数组：[5,7,4,2,0,3,1,6]对应图示完全二叉树。

2. 二叉树遍历（深度优先 DFS + 广度优先 BFS）

（1）深度优先遍历（DFS，递归）

以根 A、左 B、右 C 的简单二叉树为例：

1. 先序遍历（根→左→右）：A → B → C
2. 中序遍历（左→根→右）：B → A → C
3. 后序遍历（左→右→根）：B → C → A

（2）广度优先遍历（BFS，层序遍历）

从上到下、每层从左到右遍历，示例树输出：5 7 4 2 0 3 1 6，和数组存储顺序完全一致。

二、哈夫曼树 & 哈夫曼编码

1. 基础概念

• 节点的权：字符出现的频次（如a:3代表字母 a 出现 3 次）
• 路径：根节点到叶子节点的通路
• 路径长度：路径上边的数量
• 带权路径长度 WPL：节点权值 × 路径长度
• 哈夫曼树：给定一组权值构造的WPL 最小的二叉树，只有叶子带权、无度为 1 的节点
• 树 WPL：所有叶子节点带权路径长度之和（图中示例 WPL=66）

2. 哈夫曼树构造规则

1. 取出权值最小的两个叶子节点，生成新父节点，父节点权 = 两子节点权之和
2. 将新父节点放回节点集合，重复步骤 1，直到只剩一个根节点
3. 左分支记0、右分支记1，从根到叶子的路径数字串即为该字符哈夫曼编码|

核心特性：前缀编码，任一字符编码不会是其他编码的前缀，解码无歧义。

三、四大基础排序算法

1. 冒泡排序 BubbleSort

原理

相邻两个元素两两比较，前 > 后则交换；每一轮遍历会把当前未排序区间最大值 “冒泡” 到末尾；共n-1轮，每轮减少 1 次内层比较。

• 时间复杂度：最坏 / 平均 \(O(n^2)\)，最好有序数组 \(O(n)\)（可优化标识提前退出）
• 稳定性：稳定排序（相等元素相对顺序不变）
• 核心逻辑：内层i对比i+1，逆序交换

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 j=0; j<arr.length-1; j++) { //内层：每轮末尾j个元素已有序，无需比较 for(int i=0; i<arr.length-1-j; i++) { if(arr[i] > arr[i+1]) { //交换相邻元素 int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = 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 j=0; j<arr.length-1; j++) { int min = arr[j]; int minIndex = j; //遍历无序区，查找最小值下标 for(int i=j+1; i<arr.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 i=1; i<arr.length; i++) { //j从待插入元素前一位，向前遍历有序区 for(int j=i-1; j>=0; j--) { if(arr[j] > arr[j+1]) { //前值更大，后移 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = 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 i=grp; i<arr.length; i++) { //组内向前插入排序，步长grp for(int j = i - grp; j >= 0; j -= grp) { if(arr[j] > arr[j+grp]) { int temp = arr[j]; arr[j] = arr[j+grp]; arr[j+grp] = temp; } else { break; } } } } } }

5. 基数排序 RadixSort（桶排序拓展，稳定排序）

原理

1. 准备编号0~9共 10 个桶，按低位优先排序：先按个位分桶收集，再按十位、百位…… 直到最高位处理完成
2. 每一轮：数字按当前位数值放入对应桶；全部入桶后，按桶顺序取出覆盖原数组
3. 循环次数 = 数组中最大值的数字位数

• 时间复杂度：\(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; } } }

四、五大排序对比总结表