Java 数据结构

数组

数组是一种连续存储线性结构，数组尺寸不能改变。元素类型相同，大小相等，通过使用整型索引值来访问他们的元素。数组是多维的。数组能够容纳基本数据类型（int、char等）或者对象引用（如类对象）。
数组的优点：存取速度快
数组的缺点：事先必须知道数组的长度、插入删除元素很慢、空间通常有限制、需要大块连续内存块、插入删除元素的效率很低
Java没有指针，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。所以看不到每个元素的地址情况

int[] numbers;                               // 声明一个 int 数组
numbers = new int[5];                        // 初始化一个长度为 5 的 int 数组
int[] values = {1, 2, 3, 4, 5};              // 声明并初始化一个 int 数组
... return new int[]{i, j};                  // 在方法中返回数组[i, j]
int length = arr.length;                     // 获取数组的长度
int value = arr[1];                          // 获取索引为 1 的元素
int[][] twoDimArray = new int[3][4];         // 创建一个 3x4 的二维数组
int[][] twodimArray = {{1,6},{7,3},{1,5}};   // 声明并初始化一个 二维 int 数组
int[][][] threeDimArray = new int[3][4][2];  // 创建一个 3x4x2 的三维数组
System.out.println(twoDimArray[0]);          // [I@7852e922：16进制数值，不是真正的地址，是处理后的

int[] numbers; 只是声明了一个名为 numbers 的整数数组的引用，它并没有创建数组对象，并没有分配内存或存储数据。
int[] numbers = new int[5]; 在这里，new int[5] 表示创建一个能够存储 5 个整数的整型数组，并将该数组的引用赋给 numbers 变量。这是一个基本的数组类型，而不是 Arrays、ArrayList 或 Vector 对象。
数组是基本的数据结构，而 Arrays 和 ArrayList 是 Java 中的类，提供了用于操作和管理数组的方法。

Arrays

Arrays 类是 Java API 中的一个工具类，它提供了一系列静态方法来操作数组，比如排序、搜索、比较等。

int[] arr = new int[5];
Arrays.fill(arr, 10);                           //  fill()：将数组的所有元素设置为指定值。
String[] array = {"apple", "banana", "orange"};
List<String> list = Arrays.asList(array);       //  asList()：将数组转换为 `List`。
int[] numbers = {5, 2, 9, 1, 5};
Arrays.sort(numbers);                           //  sort()：对数组进行排序。
int index = Arrays.binarySearch(numbers, 3);    //  binarySearch()：在排序数组中执行二分查找。
String str = Arrays.toString(numbers);          //  toString()：将数组转换为字符串表示形式。
boolean isEqual = Arrays.equals(arr, numbers);  //  equals()：比较两个数组是否相等。
int[] copy1 = Arrays.copyOf(arr, sou.length);   //  copyOf：复制数组或复制数组的指定范围。
int[] copy2 = Arrays.copyOfRange(arr, 2, 4);    //  copyOfRange()：复制数组或复制数组的指定范围。

Vector

Vector 是一个同步的动态数组类，类似于 ArrayList，可以自动增长和缩小以容纳对象。
ArrayList 和 Vector 都是动态数组实现的集合，而 Arrays 类主要用于数组的各种操作。
Vector 是线程安全的（是同步的），而 Arrays 不是（没有提供同步）。Vector 在对集合进行操作时会进行同步，适用于多线程环境。单线程环境下，推荐使用 ArrayList 而不是 Vector，因为 ArrayList 不是同步的，性能更高。

Vector<String> vector = new Vector<>();            // 创建 Vector
vector.add("Element 1");                           // 添加元素
int size = vector.size();                          // 获取 Vector 的大小
boolean isEmpty = vector.isEmpty();                // 检查 Vector 是否为空
String element = vector.get(0);                    // 访问 Vector 中的元素：获取索引为0的元素
int index = vector.indexOf("Element 2");           // 查找元素在 Vector 中的位置
vector.remove(1);                                  // 删除 Vector 中的元素：删除索引为1的元素
for (String element : vector) { ...}               // 遍历 Vector 中的元素

ArrayList

ArrayList是基于动态数组实现的，可以自动扩容。（动态数组是一种数据结构，而非类，是一种具有自动扩容能力的数组）
它支持快速随机访问元素，但在插入和删除元素时可能会比较耗时。适用于需要随机访问元素、按索引查找和遍历集合的场景。
1、add(E e)：在尾部添加元素。
2、get(int index)：获取指定位置的元素。
3、set(int index, E element)：用于替换指定索引处的元素。
4、remove(int index)：移除指定位置的元素。
5、size()：返回集合大小。

List<String> cur = new ArrayList<>();                        // 一维动态数组
List<List<Integer>> ans = new ArrayList<List<Integer>>();    // 二维动态数组
ans.get(i).set(j, ans.get(i).get(j) + ans.get(i-1).get(j));  // 二维数组读写

LinkedList

LinkedList是基于双向链表实现的，每个节点都存储了对前一个和后一个元素的引用。它在插入和删除元素时效率较高，但在随机访问元素时效率较低。LinkedList适用于需要频繁的插入、删除操作的场景。
1、add(E e)：在尾部添加元素。
2、addFirst(E e)：在头部添加元素。
3、get(int index)：获取指定位置的元素。
4、remove(int index)：移除指定位置的元素。
5、size()：返回集合大小。

---

链表

链表由一个节点序列组成，每个节点包含数据和指向下一个节点的引用。n个节点离散分配，每个节点只有一个前驱节点和一个后续节点，首节点没有前驱节点，尾节点没有后续节点。当你创建一个链表时，你持有的引用实际上指向链表中第一个节点的地址，也就是头节点。头节点存储了链表的起始地址，通过这个地址可以访问整个链表。
链表优点：空间没有限制、插入删除元素很快。链表缺点：存取速度很慢

单链表

单链表的每个节点包含两个部分：数据和指向下一个节点的引用。第一个节点称为头节点，最后一个节点的下一个节点为空null

public class Node {   // Java中单链表的节点（Node）通常会被定义为一个内部类。
    public int data;  // 数据域
    public Node next; // 指针域，指向下一个节点
    public Node() {    }
    public Node(int data) {        this.data = data;    }
    public Node(int data, Node next) {        this.data = data;        this.next = next;    }
}

public class SinglyLinkedList {
    private Node head;
    // 添加新节点
    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
    // 其他操作（删除节点、查找节点等）可以根据需要实现
}

双向链表 中的每个节点都有两个指针：一个指向前一个节点，一个指向后一个节点。双向链表允许在节点之间双向遍历。
将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现 循环链表，能通过任何一个节点找到其他所有的节点。

---

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。哈希表使用 O(N) 空间复杂度存储数据，并且以 O(1) 时间复杂度求解问题。

• 构造散列函数的方法有：
  1. 直接定址法： 取关键字或关键字的某个线性函数值为散列地址。即：h(key) = key 或 h(key) = a * key + b，其中 a，b 为常数
  2. 数字分析法
  3. 平方取值法： 取关键字平方后的中间几位为散列地址。
  4. 折叠法： 将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。
  5. 除留余数法： 取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址，即： h(key) = key MOD p p ≤ m
  6. 随机数法： 选择一个随机函数，取关键字的随机函数值为它的散列地址，即： h(key) = random(key)

使用了散列表的集合有map和set；

• HashSet 用于存储一个集合，可以查找元素是否在集合中。
  但是，如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在，就足够了。
• HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。

HashMap 常用方法

put(key, value)：将指定的键值对添加到哈希表中；如果该键已存在于 HashMap 中，则其旧值会被新值替换。
get(key)：根据键获取对应的值。
containsKey(key)：检查哈希表中是否包含指定的键。containsValue(value)：检查哈希表中是否包含指定的值。
remove(key)：根据键移除键值对。
size()：返回哈希表中键值对的数量。
isEmpty()：检查哈希表是否为空。
keySet()：返回哈希表中所有键的集合。values()：返回哈希表中所有值的集合。entrySet()：返回键值对的集合。

import java.util.HashMap;
import java.util.Map;
Map<String, Integer> hashMap = new HashMap<>();  // 创建一个HashMap
hashMap.put("Three", 3);  hashMap.remove("Three");
if (!hashMap.containsKey("Three"))  hashMap.put("Three", 3); 
// 遍历kv：2种方法
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {  
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
for(String s : hashMap.keySet()) System.out.println("Key: " + s + ", Value: " + hashMap.get(s));

HashSet 常用方法

add(E e): 向集合中添加元素。addAll(Collection<? extends E> c): 将另一个集合的所有元素添加到当前集合。
remove(Object o): 移除指定的元素。removeAll(Collection<?> c): 移除当前集合中包含在指定集合中的所有元素。
contains(Object o): 判断集合中是否包含指定元素。containsAll(Collection<?> c): 判断集合是否包含指定集合中的所有元素。
size(): 返回集合的大小（元素个数）。
isEmpty(): 判断集合是否为空。
clear(): 清空集合中的所有元素。
iterator(): 返回用于遍历集合的迭代器。

---

字符串

String 内部使用 char 数组存储数据。该数组被声明为 final，因此它不可被继承，初始化之后就不能再引用其它数组。并且 String 内部没有改变 value 数组的方法，因此可以保证 不可变。String 是一个类，而不是基本数据类型或容器。表示的是一个字符序列。
字符串是一个引用类型，因此在创建 String 对象时，实际上是在内存中分配了一块存储空间来存储字符串的值。(字符串常量池，堆，栈，

• 获取字符串信息：
  length()：返回字符串的长度。
  charAt(int index)：返回指定索引处的字符。
  substring(int beginIndex)：返回从 beginIndex 开始到字符串末尾的子字符串。
  substring(int beginIndex, int endIndex)：返回从 beginIndex 到 endIndex（不含）之间的子字符串
• 字符串拼接：直接使用 + 运算符，或 concat(String str)：将指定字符串 str 连接到原字符串的末尾。
  String 不可变，+= 操作符或 concat()实际上创建了一个新的字符串对象，该对象包含 字符串值修改后的内容，然后将其分配给了原 str变量，使 str 引用了新的字符串对象，而原始的空字符串对象仍然存在，没有被修改。
• 字符串查找和比较：
  indexOf(String str)：返回指定子字符串 str 在主字符串中第一次出现的位置。lastIndexOf()：返回最后一次..
  equals(Object another)：比较两个字符串是否相等。equalsIgnoreCase()：忽略大小写比较..。
• 字符串转换：
  toLowerCase()：将字符串转换为小写，toUpperCase()：转大写。对于字符，有 Character.toLowerCase() 方法；
  trim()：去除字符串首尾的空格。
• 切割字符串：

  String text = "Hello world! This is a Java example.";
  // split() 方法根据匹配给定的正则表达式来拆分字符串。(注意判断结果可能是空字符串)
  // 注意：`.`、`$`、`|` 和 `*` 等转义字符，必须得加 \\。多个分隔符，可以用 | 作为连字符。
  // 使用空格切割字符串: \\s+ 表示一个或多个空格
  String[] words = text.split("\\s+");

• 字符串替换：
  replace(char oldChar, char newChar)：将字符串中的 oldChar 替换为 newChar。
  replaceAll(String regex, String replace)：使用新字符串replace替换所有与 regex匹配的字符串。
  replaceFirst(String regex, String replacement)：替换第一个匹配的字符串。
• 字符串翻转：

  String original = "Hello, World!";
  StringBuffer reversed = new StringBuffer(original).reverse();
  String reversedString = reversed.toString();

---

栈和队列

数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用

栈（Stack）

栈是一种后进先出（LIFO，Last-In-First-Out）的数据结构。在Java中，可以使用 java.util.Stack 类实现栈的功能，也可以使用 Deque 接口（比如 ArrayDeque 或 LinkedList）来模拟栈的行为。
Java 中，Stack 类实际上继承自 Vector 类。Vector 类实现了一个动态数组，而 Stack 在 Vector 的基础上提供了栈的常见操作。

import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(10);                       // push(E item)：将元素压入栈顶。
stack.push(20); 
System.out.println(stack.pop());      // pop()：移除并返回栈顶元素。输出 30
System.out.println(stack.peek());     // peek()：返回但不移除栈顶元素。输出 20
System.out.println(stack.isEmpty());  // isEmpty()：检查队列是否为空。输出 false

队列（Queue）

队列是一种先进先出（FIFO，First-In-First-Out）的数据结构。在Java中，可以使用 java.util.Queue 接口和它的实现类来实现队列。

import java.util.LinkedList;
import java.util.Queue;
Queue<Integer> queue = new LinkedList<>();
queue.offer(10);                        // offer(E e)：将元素插入队列。
queue.offer(20);
int count = que.size();                 // 队列的大小
System.out.println(queue.poll());       // poll()：移除并返回队列头部的元素。输出 10
System.out.println(queue.peek());       // peek()：返回但不移除队列头部的元素。输出 20
System.out.println(queue.isEmpty());    // isEmpty()：检查队列是否为空。输出 false

双向队列 (Deque, “double ended queue”)，它可以从队列的两端添加和删除元素。Java的java.util包提供了ArrayDeque和LinkedList两种实现。

Deque<String> stack = new ArrayDeque<String>();  
if (!stack.isEmpty()) {
    stack.pollFirst();      // 前出
} else {
    stack.offerLast(name);  // 后入
}

优先级队列 (PriorityQueue), 是一个无界队列，它使用元素的自然顺序或者构造队列时提供的Comparator对元素进行排序。PriorityQueue不允许使用null元素。

// 创建一个基于自然顺序的优先级队列  
PriorityQueue<Integer> queue = new PriorityQueue<>();  
// 添加元素  
queue.add(3);  
queue.add(1);  
queue.add(4);  
int removed = queue.poll();  // 取出并删除队列中的最小元素 
System.out.println(queue);   // 输出队列：3, 4  

// 创建一个基于自定义Comparator的优先级队列  
PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(Math::abs));  
// 添加元素  
queue.add(-3);  
queue.add(-1);  
queue.add(4);  
queue.add(-2);  
System.out.println(queue);  // 输出队列：1, 2, 3, 4，因为它们的绝对值从小到大排列  

---

树

树：它是n(n>=0)个节点的有限集。n=0时为空树。n>0时，有限集的元素构成一个具有层次感的数据结构。
区别于线性表一对一的元素关系，树中的节点是一对多的关系。树具有以下特点:
1、n>0时，根节点是唯一的，不可能存在多个根节点。
2、每个节点有零个至多个子节点；除了根节点外，每个节点有且仅有一个父节点。根节点没有父节点。

1. 基本概念：
   • 子树: 除了根节点外，每个子节点都可以分为多个不相交的子树。
   • 孩子与双亲: 若一个结点有子树，那么该结点称为子树根的”双亲”，子树的根是该结点的”孩子”。
   • 兄弟: 具有相同双亲的节点互为兄弟。
   • 节点的度: 一个节点拥有子树的数目。
   • 叶子: 没有子树，也即是度为0的节点。
   • 分支节点: 除了叶子节点之外的节点，也即是度不为0的节点。
   • 内部节点: 除了根节点之外的分支节点。
   • 层次: 根节点为第一层，其余节点的层次等于其双亲节点的层次加1.
   • 树的高度: 也称为树的深度，树中节点的最大层次。
   • 有序树: 树中节点各子树之间的次序是重要的，不可以随意交换位置。
   • 无序树: 树种节点各子树之间的次序是不重要的。可以随意交换位置。
   • 森林: 0或多棵互不相交的树的集合。
2. 二叉树：最多有两棵子树的树被称为二叉树
   • 满二叉树: 二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上
   • 完全二叉树: 如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树
   • 插入
   • 删除
   • 遍历：前序遍历、中序遍历、后序遍历
   • 搜索
3. 动态查找树
   • 二叉搜索树 BST
     • 指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点。
     • 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为 O(logn) 。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。
   • 二叉平衡树 AVL
     • 含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树
     • 具有以下性质：要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；其左右子树也都是平衡二叉树；二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则AVL的所有节点的平衡因子只可能是-1,0,1。
   • 红黑树
     • 红黑树也是一种自平衡的二叉查找树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK;通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。
     • 特征：1、每个结点要么是红的要么是黑的。(红或黑) 2、根结点是黑的。(根黑) 3、每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。(叶黑) 4、如果一个结点是红的，那么它的两个儿子都是黑的。(红子黑) 5、对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。(路径下黑相同)
     • 红黑树与AVL树的比较
       1.AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
       2.红黑树的插入删除比AVL树更便于控制操作
       3.红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)
     • 用法最广：Java ConcurrentHashMap & TreeMap；C++ STL: map & set；linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块；epoll在内核中的实现，用红黑树管理事件块；nginx中，用红黑树管理timer等
   • 哈夫曼树：哈夫曼又称最优二叉树。是一种带权路径长度最短的二叉树，一般可以按下面步骤构建:
     • （1）将所有左，右子树都为空的作为根节点。（2）在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的。（3）从森林中删除这两棵树，同时把新树加入到森林中。
     • （4）重复（2）（3）步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
4. 多路查找树
   • B 树：是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一种自平衡的m阶树，与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统。
     • 根结点至少有两个子女。
     • 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
     • 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
     • 所有的叶子结点都位于同一层。
     • 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
       B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree:
   • B+ 树：B+ 树是一种树数据结构，通常用于关系型数据库(如Mysql)和操作系统的文件系统中。
     • B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。自底向上插入，与二叉树相反。
     • 在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。
     • b+树的非叶子节点不保存数据，只保存子树的临界值(最大或者最小)，所以同样大小的节点，b+树相对于b树能够有更多的分支，使得这棵树更加矮胖，查询时做的IO操作次数也更少。
       将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示:
   • B* 树
   • R 树：R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。

避免孤立的学习知识点，要关联学习。

比如实际应用当中，我们经常使用的是查找和排序操作，这在我们的各种管理系统、数据库系统、操作系统等当中，十分常用，我们通过这个线索将知识点串联起来：
数组的下标寻址十分迅速，但计算机的内存是有限的，故数组的长度也是有限的；而且无序数组的查找最坏情况需要遍历整个数组；后来人们提出了二分查找，要求数组的构造一定有序，二分法查找解决了普通数组查找复杂度过高的问题。任何一种数组无法解决的问题就是插入、删除操作比较复杂，因此，在一个增删查改比较频繁的数据结构中，数组不会被优先考虑
普通链表由于它的结构特点被证明根本不适合进行查找
哈希表是数组和链表的折中，同时它的设计依赖散列函数的设计，数组不能无限长、链表也不适合查找，所以也不适合大规模的查找 ??? ???
二叉查找树因为可能退化成链表，同样不适合进行查找
AVL树是为了解决可能退化成链表问题，但是AVL树的旋转过程非常麻烦，因此插入和删除很慢，也就是构建AVL树比较麻烦
红黑树是平衡二叉树和AVL树的折中，是比较合适的。集合类中的Map、关联数组具有较高的查询效率，它们的底层实现就是红黑树。
多路查找树 是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的(如果元素数量非常多的话，查找就退化成节点内部的线性查找了)，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。
B树与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。它的应用是文件系统及部分非关系型数据库索引。
B+树在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。通常用于关系型数据库(如Mysql)和操作系统的文件系统中。
B* 树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针, 在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。
R树是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引。Trie树是自然语言处理中最常用的数据结构，很多字符串处理任务都会用到。
Trie树本身是一种有限状态自动机，还有很多变体。什么模式匹配、正则表达式，都与这有关。与树类似，用于处理字符串相关的问题时非常高效,它可以实现快速检索，常用于字典中的单词查询，搜索引擎的自动补全甚至 IP 路由。下图展示了“top”, “thus”和“their”三个单词在前缀树中如何存储的：
针对大量数据，如果在内存中作业优先考虑红黑树(map,set之类多为RB-tree实现)，如果在硬盘中作业优先考虑B系列树

各树详解：https://pdai.tech/md/algorithm/alg-basic-tree-search.html

二叉树

在Java中，二叉树是一种常见的树形数据结构，每个节点最多有两个子节点，分别为左子节点和右子节点。二叉树的节点类似于一个结构体，包含了数据、左子节点和右子节点的引用。以下是一个简单的二叉树的实现示例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {   this.val = val;    this.left = null;    this.right = null;   }
}

public class BinaryTree {
    private TreeNode root;
    public BinaryTree() {    root = null;   }

    // 插入节点
    public void insert(int val) {
        root = insertRec(root, val);
    }
    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        return root;
    }
    // 其他操作（搜索节点、删除节点等）可以根据需要实现
}

红黑树

• 红黑树的特性
  （1）每个节点或者是黑色，或者是红色。
  （2）根节点是黑色。
  （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或NULL)的叶子节点！ ]
  （4）如果一个节点是红色的，则它的子节点必须是黑色的。
  （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
• 左旋
  对 x 进行左旋，意味着，将“x 的右孩子”设为“x 的父亲节点”；即，将 x 变成了一个左节点(x成了为 z 的左孩子)！因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
• 右旋
  对 x 进行右旋，意味着，将“x 的左孩子”设为“x 的父亲节点”；即，将 x 变成了一个右节点(x成了为 y 的右孩子)！因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
• 添加
  第一步: 将红黑树当作一颗二叉查找树，将节点插入。
  第二步：将插入的节点着色为”红色”。
  根据被插入节点的父节点的情况，可以将”当节点 z 被着色为红色节点，并插入二叉树”划分为三种情况来处理。
  ① 情况说明：被插入的节点是根节点。处理方法：直接把此节点涂为黑色。
  ② 情况说明：被插入的节点的父节点是黑色。处理方法：什么也不需要做。节点被插入后，仍然是红黑树。
  ③ 情况说明：被插入的节点的父节点是红色。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据”叔叔节点的情况”，将这种情况进一步划分为 3种情况(Case)
  ，，，
  第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。
• 删除
  第一步：将红黑树当作一颗二叉查找树，将节点删除。这和”删除常规二叉查找树中删除节点的方法是一样的”。分 3 种情况：
  ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。
  ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
  ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
  第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。 因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。
  选择重着色 3 种情况。
  ① 情况说明： x 是“红+黑”节点。处理方法：直接把 x 设为黑色，结束。此时红黑树性质全部恢复。
  ② 情况说明： x 是“黑+黑”节点，且 x 是根。处理方法：什么都不做，结束。此时红黑树性质全部恢复。
  ③ 情况说明： x 是“黑+黑”节点，且 x 不是根。处理方法：这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示：
  ，，，，

B树

B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下（其中 ceil(x)是一个取上限的函数） ：

1. 树中每个结点至多有 m 个孩子；
2. 除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子；
3. 若根结点不是叶子结点，则至少有 2 个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
4. 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
5. 每个非终端结点中包含有 n 个关键字信息： (n， P0， K1， P1， K2， P2， ……， Kn， Pn)。其中：
   • Ki (i=1…n)为关键字，且关键字按顺序排序 K(i-1)< Ki。
   • Pi 为指向子树根的接点，且指针 P(i-1)指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)。
   • 关键字的个数 n 必须满足： ceil(m / 2)-1 <= n <= m-1。

一棵 m 阶的 B+tree 和 m 阶的 B-tree 的差异在于：

1. 有 n 棵子树的结点中含有 n 个关键字； (B-tree 是 n 棵子树有 n-1 个关键字)
2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)
3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(B-tree 的非终节点也包含需要查找的有效信息)

位图

位图的原理就是用一个 bit 来标识一个数字是否存在，采用一个 bit 来存储一个数据，所以这样可以大大的节省空间。 bitmap 是很常用的数据结构， 比如用于 Bloom Filter 中；用于无重复整数的排序等等。 bitmap 通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。

---

图

图(Graph)是由顶点和连接顶点的边构成的离散结构。图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。
理解：图基础，图的遍历，最小生成树(Prim & Kruskal)，最短路径(Dijkstra & Frolyd)，拓扑排序(Topological sort)，AOE & 关键路径等。

• 图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。和线性表，树的差异:
  • 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
  • 线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点(有穷非空性)。
  • 线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示(边集可以为空)
• 相关术语
  • 顶点的度：顶点Vi的度(Degree)是指在图中与Vi相关联的边的条数。对于有向图来说，有入度(In-degree)和出度(Out-degree)之分，有向图顶点的度等于该顶点的入度和出度之和。
  • 邻接：若无向图中的两个顶点V1和V2存在一条边(V1,V2)，则称顶点V1和V2邻接(Adjacent)；若有向图中存在一条边<V3,V2>，则称顶点V3与顶点V2邻接，且是V3邻接到V2或V2邻接直V3；
  • 路径：在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称该顶点序列为从顶点Vi到顶点Vj的路径(Path)。
  • 连通：若从Vi到Vj有路径可通，则称顶点Vi和顶点Vj是连通(Connected)的。
  • 权(Weight)：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。
• 类型
  • 无向图：如果图中任意两个顶点之间的边都是无向边(没有方向的边)，则称该图为无向图。边使用小括号“()”表示;如 (V1,V2);
  • 有向图：如果图中任意两个顶点之间的边都是有向边(有方向的边)，则称该图为有向图。边使用尖括号“<>”表示;如 <V1,V2>
  • 无向完全图: 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。(有(n*(n-1))/2条边)
  • 有向完全图: 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。(含有n个顶点的有向完全图有n*(n-1)条边)
• 图的存储结构
  • 邻接矩阵表示法：用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。 不足: 由于存在n个顶点的图需要n*n个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将会出现大量0元素，这会造成极大的空间浪费。这时，可以考虑使用邻接表表示法来存储图中的数据
  • 邻接表表示法：邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。

DFS

深度优先搜索: 假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。

void dfs(vexnode *g[], int v1) {
    stack<vexnode*> stk;
    stk.push(g[v1]);
    g[v1]->visited = true;
    while (!stk.empty()) {
        vexnode *cur = stk.top();
        stk.pop();
        cout << cur->val << " ";
        for (vexnode *neighbor : cur->neighbors) {
            if (!neighbor->visited) {
                neighbor->visited = true;
                stk.push(neighbor);
            }
        }
    }
}

BFS

广度优先搜索算法(Breadth First Search)，又称为”宽度优先搜索”或”横向优先搜索”。
它的思想是: 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。

void bfs(vexnode *g[], int v1) {
    queue<vexnode*> que;
    que.push(g[v1]);
    g[v1]->visited = true;

    while (!que.empty()) {
        vexnode *cur = que.front();
        que.pop();
        cout << cur->val << " ";

        for (vexnode *neighbor : cur->neighbors) {
            if (!neighbor->visited) {
                neighbor->visited = true;
                que.push(neighbor);
            }
        }
    }
}

DFS & BFS 实现 https://pdai.tech/md/algorithm/alg-basic-graph-bfs-dfs.html

---

ACM模式Java输入

核心代码模式下不用考虑输入输出的问题，只需要根据所给函数框架写中间逻辑代码。但是在ACM模式下要，即函数的输入是从控制台键入的几行数据，而输出是直接将结果打印到控制台。
nextInt()：直至读取到空格或回车之后结束本次的int值；
next()：直至读取到空格或回车之后结束本次的String值，不可读取回车；
nextLine()：直至读取到换行符（回车）之后结束本次读取的String，可读取回车（空值）

单个输入

有的函数输入很简单，就是一个数，或者一个字符串，或者一行数中间用空格隔开，这种输入很简单，处理方法如下。

import java.util.Scanner;

public class test{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入的一个整型
        int n = sc.nextInt();
        // 如果输入的是double类型
        double d = sc.nextDouble();
        // 如果输入的是一个字符串
        String s = sc.next(); 
        // 读取的是一整行
        String l = sc.nextLine(); 
    }
}

一行输入

如果输入的是一行数据，中间用空格隔开，比如输入的是2 3 4

Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();  // 接收第1个数
int n2 = sc.nextInt();	// 接收第2个数
int n3 = sc.nextInt();	// 接收第3个数

有时候输入不是空格分隔，而是逗号分割的，比如输入的是1,2,3,4,5，并假设我们需要用数组接收，可以这么操作

Scanner sc = new Scanner(System.in);
//以字符串形式作为输入
String str = sc.next();
//通过分隔符将其转为字符串数组
String[] arr = str.split(",");
//初始化一个整数数组
int[] nums = new int[arr.length];
//给整数数组赋值
for (int j = 0; j < nums.length; j++) {
    nums[j] = Integer.parseInt(arr[j]);
}

多行输入

一共输入两行，第一行表示第二行有多少个数，比如第一行为4，第二行为0 2 3 4。

Scanner sc = new Scanner(System.in);
// 第一行的数表示第二行有多少个数，即数组的长度
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
    nums[i] = sc.nextInt();
}

持续输入

如果题目中没有明说一次给几个输入，为了保险可以直接无脑用 while(sc.hasNext()) {} 包括起来，一直等待输入，除非终止程序。

while (sc.hasNext()) {
    String str = sc.nextLine();
    // 多个输入都需要经过相同的逻辑判断然后在输出
}

Acm模式输出

System.out.print();   // 用于打印不带换行符的内容到控制台
System.out.println(); // 用于打印带换行符的内容到控制台，打印完后会换行
System.out.format();  // 用于格式化输出，可以通过格式化字符串来指定输出的格式
System.out.printf();  // 也用于格式化输出，但是使用更简单，格式化字符串以及对应的参数放在一起即可
System.out.println("Hello" + ", " + "world" + "!"); // 字符串连接可以直接用 + 号："Hello, world!"

// 规格化的输出：
// `#` 表示如果该位置有数字则显示，否则不显示；`0` 表示该位置无论是否有数字都显示，如果没有数字则显示 `0`；
DecimalFormat fd = new DecimalFormat("#.00#");
DecimalFormat gd = new DecimalFormat("0.000");
System.out.println("x =" + fd.format(x)); // `.00#` 表示保留两位小数并四舍五入；x = 12.3456， fd.format(x) 输出的结果是 12.35
System.out.println("x =" + gd.format(x)); // `0.000` 表示保留三位小数四舍五入； x = 12.3456， gd.format(x) 输出的结果是 12.346

// 二进制字符串输出：
String binaryString = Integer.toBinaryString(42); // 将整数转换为二进制字符串
System.out.println("Binary representation of " + number + " is: " + binaryString);

日期处理

SimpleDateFormat 用于日期格式化和解析，可以将日期对象格式化为指定的字符串，也可以将特定格式的字符串解析为日期对象。

1. 格式化日期为字符串：

   SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
   Date now = new Date();
   String formattedDate = sdf.format(now);

2. 解析字符串为日期：

   SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
   String dateString = "2024-03-02 15:30:00";
   Date parsedDate = sdf.parse(dateString);
   System.out.println("Parsed Date: " + parsedDate);

文件读写

我们读取 a.txt 和 b.txt 中的内容，并将其写入到 c.txt 中。然后，我们统计总行数并在第一行写入总行数。
请注意，在写入总行数之前需要先将文件关闭并重新打开以实现在文件的开头插入内容。

public class FileCopyWithLineCount {
    public static void main(String[] args) {

        try (
            BufferedReader reader1 = new BufferedReader(new FileReader("a.txt"));
            BufferedReader reader2 = new BufferedReader(new FileReader("b.txt"));
            BufferedWriter writer = new BufferedWriter(new FileWriter("c.txt"))
        ) {
            // 读取第一个文件并写入到输出文件
            String line;
            int totalCount = 0;
            while ((line = reader1.readLine()) != null) {
                writer.write(line);
                writer.newLine();
                totalCount++;
            }

            // 读取第二个文件并写入到输出文件
            while ((line = reader2.readLine()) != null) {
                writer.write(line);
                writer.newLine();
                totalCount++;
            }

            // 在第一行写入总行数
            writer.flush();
            writer.close();
            BufferedWriter writer2 = new BufferedWriter(new FileWriter("c.txt", true));
            writer2.write("Total Lines: " + totalCount);
            writer2.newLine();
            writer2.flush();
            writer2.close();

            System.out.println("内容已成功从 " + "a.txt" + " 和 " + "b.txt" + " 读取并写入 " + "c.txt");
        } catch (IOException e) {
            System.err.println("发生IO异常: " + e.getMessage());
        }
    }
}

---

位运算

Java 中的位运算是对二进制数据进行操作的一种方式，常用的位运算符有以下几种：

1. 按位与（&）：两个位都为 1 时，结果为 1；否则为 0。例如：1010 & 1100 = 1000。

2. 按位或（|）：两个位中至少有一个为 1 时，结果为 1；否则为 0。例如：1010 | 1100 = 1110。

3. 按位异或（^）：两个位相同为 0，不同为 1。例如：1010 ^ 1100 = 0110。

4. 按位取反（~）：对一个二进制数的每个位取反，0 变为 1，1 变为 0。例如：~1010 = 0101。

5. 左移（<<）：将一个数的所有位向左移动指定的位数，右侧空出的位用 0 填充。例如：1010 << 2 = 101000。

6. 右移（>>）：将一个数的所有位向右移动指定的位数，左侧空出的位用符号位填充（正数用 0，负数用 1）。例如：1010 >> 2 = 10。

7. 无符号右移（>>>）：将一个数的所有位向右移动指定的位数，左侧空出的位用 0 填充。例如：1010 >>> 2 = 10。

---

时间复杂度

• 时间复杂度是一种用来衡量算法运行时间与输入规模之间关系的概念。它不是用来精确测量程序运行时间的，而是描述在输入规模变化时，算法运行时间的增长趋势。
• 大O表示上界，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
  O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

♥常见排序算法知识体系详解♥

A. 重点理解几个排序之间的对比，时间和空间复杂度，以及应用。PS：越简单越要提高认知效率，做到战略上藐视战术上重视。
B. 具体分析各种排序及其复杂度，查漏补缺；在综合复杂度及稳定性情况下，通常希尔, 快排和 归并需要重点掌握。
稳定性：指相等元素的相对顺序在排序前后是否保持不变。稳定性在某些应用场景中很重要，例如在对相同优先级的任务进行排序时，保持原始顺序可确保任务的处理顺序不被打乱。

https://leo710aka.github.io/2020/09/09/5%20%E7%B4%A2%E5%BC%95_%E6%8E%92%E5%BA%8F_/

• 冒泡排序(Bubble Sort)
  它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止

  public static void bubbleSort1(int [] a, int n){
      int i, j;
      for(i=0; i<n; i++){//表示 n 次排序过程。
          for(j=1; j<n-i; j++){
              if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
                  //交换 a[j-1]和 a[j]
                  int temp;
                  temp = a[j-1];
                  a[j-1] = a[j];
                  a[j]=temp;
              }
          }
      }
  }

• 插入排序(Insertion Sort)
  基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

  public void sort(int arr[]){
      for(int i = 1; i < arr.length; i++) {
          // 插入的数
          int insertVal = arr[i];
          // 被插入的位置(准备和前一个数比较)
          int index = i - 1;
          // 如果插入的数比被插入的数小
          while(index >= 0 && insertVal < arr[index]) {
              // 将把 arr[index] 向后移动
              arr[index+1] = arr[index];
              // 让 index 向前移动
              index--;
          }
          // 把插入的数放入合适位置
          arr[index+1] = insertVal;
          }
      }

• 选择排序(Selection sort)
  基本思想是: 首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

  void SelectionSort(int a[], int len) {
  	for (int i = 0; i < len - 1; i++) { 
  		int minIndex = i;
  		for (int j = i + 1; j <len; j++) {
  			if(a[j] < a[minIndex]) {
  				minIndex = j;
  			}
  		}
  		swap(a[i], a[minIndex]);
  	}
  }

• 快速排序(Quick Sort)
  采用分治的思想，将一个数组分成两个子数组，然后递归地对子数组进行排序。它选择一个元素作为”pivot”（基准），并将数组中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边，然后对左右子数组进行递归排序。

  public void quickSort(int[] nums, int low, int high) {
      if (low >= high) return; // 边界条件判断
      int start = low;
      int end = high;
      int key = nums[low];
      while (end > start) {
          while (end > start && nums[end] >= key) {
              end--;
          }
          if (end > start) {
              nums[start] = nums[end];
          }
          while (end > start && nums[start] <= key) {
              start++;
          }
          if (end > start) {
              nums[end] = nums[start];
          }
      }
      nums[start] = key; // 基准值放回合适位置
      quickSort(nums, low, start - 1); // 左边序列递归排序
      quickSort(nums, start + 1, high); // 右边序列递归排序
  }

• 希尔排序(Shell Sort)：实质上是一种分组插入方法。
  它的基本思想是: 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

  private void shellSort(int[] a) {
      int dk = a.length/2;
      while( dk >= 1 ){
          ShellInsertSort(a, dk);
          dk = dk/2;
      }
  }
  private void ShellInsertSort(int[] a, int dk) {
      //类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了
      for(int i=dk;i<a.length;i++){
          if(a[i]<a[i-dk]){
              int j;
              int x=a[i];//x 为待插入元素
              a[i]=a[i-dk];
              for(j=i-dk; j>=0 && x<a[j];j=j-dk){
                  //通过循环，逐个后移一位找到要插入的位置。
                  a[j+dk]=a[j];
              }
              a[j+dk]=x;//插入
          }
      }
  }

堆排序(Heap Sort)

• 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
  它具有 O(n log n) 的时间复杂度，并且是原地排序算法（不需要额外的空间）。堆排序分为两个阶段：建堆和排序。

  1. 建堆（Heapify）：
     • 将待排序数组视为完全二叉树，从最后一个非叶子节点开始，依次向上进行调整，使得每个节点都满足堆的性质（最大堆或最小堆）。
     • 对于最大堆，父节点的值大于或等于子节点的值；对于最小堆，父节点的值小于或等于子节点的值。
     • 建堆过程可以通过自上而下的调整（向下调整）或自下而上的调整（向上调整）来实现。
  2. 排序：
     • 将堆顶元素（根节点）与最后一个元素交换，并将最后一个元素移出堆（视为已排序部分）。
     • 对剩余的元素重新进行堆调整，使得剩余元素重新构成堆。
     • 重复上述步骤，直到所有元素都被移出堆，完成排序。

• 下面是堆排序的详细步骤：

  1. 将待排序数组构建成一个最大堆（或最小堆），即建堆过程。可以选择自上而下的调整（向下调整）或自下而上的调整（向上调整）来实现。
  2. 从最后一个非叶子节点开始，依次向前对每个节点进行堆调整，使得当前节点及其子树满足堆的性质。
  3. 交换堆顶元素（根节点）和最后一个元素，并将最后一个元素移出堆（视为已排序部分）。
  4. 对剩余的元素重新进行堆调整，使得剩余元素重新构成堆。
  5. 重复步骤3和步骤4，直到所有元素都被移出堆，完成排序。

• void AdjustDwon(int* a, int size, int parent){
      int child = parent * 2 + 1;
      while (child < size) {
          if (child + 1 < size && a[child + 1] > a[child]) {
              ++child;
          }
          if (a[child] > a[parent]) {
              swap(a[child], a[parent]);
              parent = child;
              child = parent * 2 + 1;
          }
          else {
              break;
          }
      }
  }
  void HeapSort(int* a, int n){
      for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
          AdjustDwon(a, n, i);
      }
      int end = n - 1;
      while (end > 0)	{
          swap(a[0], a[end]);
          AdjustDwon(a, end, 0);
          --end;
      }
  }

• 桶排序：原理很简单，将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

  public static void bucketSort(int[] arr){
      int max = Integer.MIN_VALUE;
      int min = Integer.MAX_VALUE;
      for(int i = 0; i < arr.length; i++){
          max = Math.max(max, arr[i]);
          min = Math.min(min, arr[i]);
      }
      //创建桶
      int bucketNum = (max - min) / arr.length + 1;
      ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
      for(int i = 0; i < bucketNum; i++){
          bucketArr.add(new ArrayList<Integer>());
      }
      //将每个元素放入桶
      for(int i = 0; i < arr.length; i++){
          int num = (arr[i] - min) / (arr.length);
          bucketArr.get(num).add(arr[i]);
      }
      //对每个桶进行排序
      for(int i = 0; i < bucketArr.size(); i++){
          Collections.sort(bucketArr.get(i));
      }
  }

• 归并排序算法：采用分治的思想将一个大问题分割成多个小问题来解决。
  具体来说，归并排序的过程包括分割、排序和合并三个步骤。

  void merge(vector<int>& arr, int left, int mid, int right) {
      int n1 = mid - left + 1, n2 = right - mid;
      vector<int> leftArr(n1), rightArr(n2);                        // 创建临时数组来存储左右两部分的数据
      for (int i = 0; i < n1; i++)  leftArr[i] = arr[left + i];     // 将数据复制到临时数组
      for (int i = 0; i < n2; i++)  rightArr[i] = arr[mid + 1 + i];    
      int i = 0, j = 0, k = left;                                   // 合并两个临时数组
      while (i < n1 && j < n2) {
          if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];  
          else arr[k++] = rightArr[j++]; 
      }
      while (i < n1)  arr[k++] = leftArr[i++];                      // 处理剩余元素
      while (j < n2)  arr[k++] = rightArr[j++];  
  }
  void mergeSort(vector<int>& arr, int left, int right) {           // 归并排序主函数
      if (left < right) {
          int mid = left + (right - left) / 2;
          mergeSort(arr, left, mid);                                // 分割左右两部分
          mergeSort(arr, mid + 1, right); 
          merge(arr, left, mid, right);                             // 合并已排序的两部分
      }
  }

• 基数排序
  基本思想是: 将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是: 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

  public class radixSort {
      int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,2 5,53,51};
      public radixSort(){
          sort(a);
          for(inti=0;i<a.length;i++){
              System.out.println(a[i]);
          }
      }
      public void sort(int[] array){
          //首先确定排序的趟数;
          int max=array[0];
          for(inti=1;i<array.length;i++){
              if(array[i]>max){
                  max=array[i];
              }
          }
          int time=0;
          //判断位数;
          while(max>0){
              max/=10;
              time++;
          }
          //建立 10 个队列;
          List<ArrayList> queue=newArrayList<ArrayList>();
          for(int i=0;i<10;i++){
              ArrayList<Integer>queue1=new ArrayList<Integer>();
              queue.add(queue1);
          }
          //进行 time 次分配和收集;
          for(int i=0;i<time;i++){
              //分配数组元素;
              for(intj=0;j<array.length;j++){
                  //得到数字的第 time+1 位数;
                  int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
                  ArrayList<Integer>queue2=queue.get(x);
                  queue2.add(array[j]);
                  queue.set(x, queue2);
                  }
                  int count=0;//元素计数器;
                  //收集队列元素;
                  for(int k=0;k<10;k++){
                  while(queue.get(k).size()>0){
                      ArrayList<Integer>queue3=queue.get(k);
                      array[count]=queue3.get(0);
                      queue3.remove(0);
                      count++;
                  }
              }
          }
      }
  }