体系结构:
一、工夫复杂度和空间复杂度
1、什么是工夫复杂度和空间复杂度
如何辨别一个算法的好坏，如果在程序上执行，会被各种因素所烦扰，所以引出了工夫复杂度和空间复杂度的概念。
工夫复杂度就是这个算法执行的是不是很快，空间复杂度就是这个算法是不是很消耗程序的空间。
算法的渐进工夫复杂度：T(n) = O(F(n))——> 大 O 表示法。
2、工夫复杂度
比方咱们这个算法要执行很屡次，那么它的表达式是怎么样的？取最高次项即可。
- 比方一行最根本的代码，它的就是 O（1）；
- 如果某个算法中计算的工夫雷同，它必定是次数越多工夫越长，而且是线性增长，比方每次吃鸡腿都是 1 分钟，那么它执行 n 次，工夫就是 n 分钟，所以它的工夫复杂度就是 O（n）;
- 如果计算 1 到 100 的和，计算的表达式就是（1 + n）* n/2–> 也就是 0.5n² + 0.5n，疏忽掉 n 的一次方，那么它的工夫复杂度就是 O（n²）
- 再比方一根绳子 16 厘米，每次剪掉残余的一半，那么多久会剩下 1 厘米，那么就须要用到对数了，这个时候工夫复杂度是 O（log16）
3、空间复杂度
空间复杂度不须要过于深刻理解，然而要晓得它不是形容占用多少内存，而是比拟的 内存变动。
- 比方一个变量 =1，而后每次都对它进行 ++ 赋值运算，变量还是一个，只不过一直的赋值，内存占用不会变动，所以还是 1
- 再比方一个 for 循环，每次都创立一个新的变量，必定它的空间复杂度是 n
- 如果是一个二维数组，再用双层 for 循环赋值，它的空间复杂度就是 n²
二、数组
1、介绍
数组是最根本的数据结构之一，能够存储无限个元素（固定长度），能够增删改查
2、代码实现
public class MyArray {
// 定义一个数组
int[] elements;
// 初始化数组
public MyArray(){elements = new int[0];
}
// 获取数组的长度
public int size(){return elements.length;}
// 往数组的开端增加一个元素
public void add(int ele){int[] newArr = new int[elements.length + 1];
for (int i = 0;i < elements.length;i++){newArr[i] = elements[i];
}
newArr[elements.length] = ele;
elements = newArr;
}
// 遍历数组的办法
public void arrayShow(){System.out.println(Arrays.toString(elements));
}
// 删除一个元素
public void delete(int index){if (index < 0 || index > elements.length - 1){throw new RuntimeException("传入下标不正确");
}
int[] newArr = new int[elements.length - 1];
for (int i = 0;i < newArr.length;i++){if (i < index){newArr[i] = elements[i];
}else{newArr[i] = elements[i + 1];
}
}
elements = newArr;
}
// 取出指定地位的元素
public int get(int index){if (index < 0 || index > elements.length -1){throw new RuntimeException("传入下标不正确，不能读取元素");
}
return elements[index];
}
// 插入一个元素到指定地位
public void insert(int index,int ele){int[] newArr = new int[elements.length + 1];
for (int i = 0;i < newArr.length;i++){if (i < index){newArr[i] = elements[i];
}else{newArr[i + 1] = elements[i];
}
}
// 插入新的元素
newArr[index] = ele;
// 替换数组
elements = newArr;
}
// 替换其中的一个元素
public void update(int index,int ele){if (index < 0 || index > elements.length - 1){throw new RuntimeException("传入下标不正确，不能批改数组");
}
elements[index] = ele;
}
// 线性查找
public int search(int target){for (int i = 0;i < elements.length;i++){if (elements[i] == target){return i;}
}
// 未找到相应元素
return -1;
}
}测试数组：
public class TestMyArray {public static void main(String[] args) {MyArray myArray = new MyArray();
myArray.add(2);
myArray.add(11);
myArray.add(15);
myArray.add(7);
myArray.add(14);
myArray.add(3);
myArray.add(8);
myArray.delete(2);
myArray.arrayShow();}
}三、队列
1、介绍
- 队列是一个有序列表，能够用数组或是链表来实现。
- 遵循先入先出的准则。即：先存入队列的数据，要先取出。后存入的要后取出
2、代码实现
public class MyQueue {
// 创立一个数组
int[] elements;
// 构造方法
public MyQueue(){elements = new int[0];
}
// 给队列增加元素
public void addQueue(int ele){int[] newArr = new int[elements.length + 1];
for (int i = 0;i < elements.length;i++){newArr[i] = elements[i];
}
newArr[elements.length] = ele;
elements = newArr;
}
// 从队列取出元素
public int getQueue(){int ele = elements[0];
int[] newArr = new int[elements.length - 1];
for (int i = 0;i < newArr.length;i++){newArr[i] = elements[i + 1];
}
elements = newArr;
return ele;
}
// 判断队列是否为空
public boolean isEmpty(){return elements.length == 0;}
// 查问所有元素
public void show(){for (int i = 0;i < elements.length;i++){System.out.println("以后队列第" + (i + 1) + "个元素是:" + elements[i]);
}
}
}测试。
public class TestMyQueue {public static void main(String[] args) {MyQueue mq = new MyQueue();
System.out.println("队列是否为空:" + mq.isEmpty());
mq.addQueue(10);
System.out.println("队列是否为空:" + mq.isEmpty());
mq.addQueue(12);
mq.addQueue(8);
mq.addQueue(15);
mq.addQueue(22);
mq.addQueue(113);
mq.show();}
}四、链表
1、介绍
- 链表是以节点的形式来存储, 是链式存储
- 每个节点蕴含 data 域，next 域：指向下一个节点.
- 链表的各个节点不肯定是间断存储.
2、单向链表代码实现
public class SingleLinkedListDemo {public static void main(String[] args) {
// 进行测试
// 先创立节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// 创立要给链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
// 退出
singleLinkedList.add(hero1);
singleLinkedList.add(hero4);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
// 测试一下单链表的反转性能
System.out.println("原来链表的状况~~");
singleLinkedList.list();
// System.out.println("反转单链表~~");
// reversetList(singleLinkedList.getHead());
// singleLinkedList.list();
System.out.println("测试逆序打印单链表, 没有扭转链表的构造~~");
reversePrint(singleLinkedList.getHead());
/*
// 退出依照编号的程序
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
// 显示一把
singleLinkedList.list();
// 测试批改节点的代码
HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
singleLinkedList.update(newHeroNode);
System.out.println("批改后的链表状况~~");
singleLinkedList.list();
// 删除一个节点
singleLinkedList.del(1);
singleLinkedList.del(4);
System.out.println("删除后的链表状况~~");
singleLinkedList.list();
// 测试一下 求单链表中无效节点的个数
System.out.println("无效的节点个数 =" + getLength(singleLinkedList.getHead()));//2
// 测试一下看看是否失去了倒数第 K 个节点
HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);
System.out.println("res=" + res);
*/
}
// 形式 2：// 能够利用栈这个数据结构，将各个节点压入到栈中，而后利用栈的先进后出的特点，就实现了逆序打印的成果
public static void reversePrint(HeroNode head) {if(head.next == null) {return;// 空链表，不能打印}
// 创立要给一个栈，将各个节点压入栈
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
// 将链表的所有节点压入栈
while(cur != null) {stack.push(cur);
cur = cur.next; //cur 后移，这样就能够压入下一个节点
}
// 将栈中的节点进行打印,pop 出栈
while (stack.size() > 0) {System.out.println(stack.pop()); //stack 的特点是先进后出
}
}
// 将单链表反转
public static void reversetList(HeroNode head) {
// 如果以后链表为空，或者只有一个节点，无需反转，间接返回
if(head.next == null || head.next.next == null) {return ;}
// 定义一个辅助的指针(变量)，帮忙咱们遍历原来的链表
HeroNode cur = head.next;
HeroNode next = null;// 指向以后节点 [cur] 的下一个节点
HeroNode reverseHead = new HeroNode(0, "","");
// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
// 动脑筋
while(cur != null) {
next = cur.next;// 先临时保留以后节点的下一个节点，因为前面须要应用
cur.next = reverseHead.next;// 将 cur 的下一个节点指向新的链表的最前端
reverseHead.next = cur; // 将 cur 连贯到新的链表上
cur = next;// 让 cur 后移
}
// 将 head.next 指向 reverseHead.next , 实现单链表的反转
head.next = reverseHead.next;
}
// 查找单链表中的倒数第 k 个结点【新浪面试题】// 思路
//1. 编写一个办法，接管 head 节点，同时接管一个 index
//2. index 示意是倒数第 index 个节点
//3. 先把链表从头到尾遍历，失去链表的总的长度 getLength
//4. 失去 size 后，咱们从链表的第一个开始遍历 (size-index)个，就能够失去
//5. 如果找到了，则返回该节点，否则返回 nulll
public static HeroNode findLastIndexNode(HeroNode head, int index) {
// 判断如果链表为空，返回 null
if(head.next == null) {return null;// 没有找到}
// 第一个遍历失去链表的长度(节点个数)
int size = getLength(head);
// 第二次遍历 size-index 地位，就是咱们倒数的第 K 个节点
// 先做一个 index 的校验
if(index <=0 || index > size) {return null;}
// 定义给辅助变量，for 循环定位到倒数的 index
HeroNode cur = head.next; //3 // 3 - 1 = 2
for(int i =0; i< size - index; i++) {cur = cur.next;}
return cur;
}
// 办法：获取到单链表的节点的个数(如果是带头结点的链表，需要不统计头节点)
/**
*
* @param head 链表的头节点
* @return 返回的就是无效节点的个数
*/
public static int getLength(HeroNode head) {if(head.next == null) { // 空链表
return 0;
}
int length = 0;
// 定义一个辅助的变量, 这里咱们没有统计头节点
HeroNode cur = head.next;
while(cur != null) {
length++;
cur = cur.next; // 遍历
}
return length;
}
}
// 定义 SingleLinkedList 治理咱们的英雄
class SingleLinkedList {
// 先初始化一个头节点, 头节点不要动, 不寄存具体的数据
private HeroNode head = new HeroNode(0, "","");
// 返回头节点
public HeroNode getHead() {return head;}
// 增加节点到单向链表
// 思路，当不思考编号程序时
//1. 找到以后链表的最初节点
//2. 将最初这个节点的 next 指向 新的节点
public void add(HeroNode heroNode) {
// 因为 head 节点不能动，因而咱们须要一个辅助遍历 temp
HeroNode temp = head;
// 遍历链表，找到最初
while(true) {
// 找到链表的最初
if(temp.next == null) {//
break;
}
// 如果没有找到最初, 将将 temp 后移
temp = temp.next;
}
// 当退出 while 循环时，temp 就指向了链表的最初
// 将最初这个节点的 next 指向 新的节点
temp.next = heroNode;
}
// 第二种形式在增加英雄时，依据排名将英雄插入到指定地位
//(如果有这个排名，则增加失败，并给出提醒)
public void addByOrder(HeroNode heroNode) {// 因为头节点不能动，因而咱们依然通过一个辅助指针 (变量) 来帮忙找到增加的地位
// 因为单链表，因为咱们找的 temp 是位于 增加地位的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false; // flag 标记增加的编号是否存在，默认为 false
while(true) {if(temp.next == null) {// 阐明 temp 曾经在链表的最初
break; //
}
if(temp.next.no > heroNode.no) { // 地位找到，就在 temp 的前面插入
break;
} else if (temp.next.no == heroNode.no) {// 阐明心愿增加的 heroNode 的编号未然存在
flag = true; // 阐明编号存在
break;
}
temp = temp.next; // 后移，遍历以后链表
}
// 判断 flag 的值
if(flag) { // 不能增加，阐明编号存在
System.out.printf("筹备插入的英雄的编号 %d 曾经存在了, 不能退出 \n", heroNode.no);
} else {
// 插入到链表中, temp 的前面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 批改节点的信息, 依据 no 编号来批改，即 no 编号不能改.
// 阐明
//1. 依据 newHeroNode 的 no 来批改即可
public void update(HeroNode newHeroNode) {
// 判断是否空
if(head.next == null) {System.out.println("链表为空~");
return;
}
// 找到须要批改的节点, 依据 no 编号
// 定义一个辅助变量
HeroNode temp = head.next;
boolean flag = false; // 示意是否找到该节点
while(true) {if (temp == null) {break; // 曾经遍历完链表}
if(temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;
}
// 依据 flag 判断是否找到要批改的节点
if(flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else { // 没有找到
System.out.printf("没有找到 编号 %d 的节点，不能批改 \n", newHeroNode.no);
}
}
// 删除节点
// 思路
//1. head 不能动，因而咱们须要一个 temp 辅助节点找到待删除节点的前一个节点
//2. 阐明咱们在比拟时，是 temp.next.no 和 须要删除的节点的 no 比拟
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // 标记是否找到待删除节点的
while(true) {if(temp.next == null) { // 曾经到链表的最初
break;
}
if(temp.next.no == no) {
// 找到的待删除节点的前一个节点 temp
flag = true;
break;
}
temp = temp.next; //temp 后移，遍历
}
// 判断 flag
if(flag) { // 找到
// 能够删除
temp.next = temp.next.next;
}else {System.out.printf("要删除的 %d 节点不存在 \n", no);
}
}
// 显示链表[遍历]
public void list() {
// 判断链表是否为空
if(head.next == null) {System.out.println("链表为空");
return;
}
// 因为头节点，不能动，因而咱们须要一个辅助变量来遍历
HeroNode temp = head.next;
while(true) {
// 判断是否到链表最初
if(temp == null) {break;}
// 输入节点的信息
System.out.println(temp);
// 将 temp 后移，肯定小心
temp = temp.next;
}
}
}
// 定义 HeroNode，每个 HeroNode 对象就是一个节点
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next; // 指向下一个节点
// 结构器
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
// 为了显示办法，咱们从新 toString
@Override
public String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}3、双向链表代码实现
public class DoubleLinkedListDemo {public static void main(String[] args) {
// 测试
System.out.println("双向链表的测试");
// 先创立节点
HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
// 创立一个双向链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
doubleLinkedList.add(hero4);
doubleLinkedList.list();
// 批改
HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");
doubleLinkedList.update(newHeroNode);
System.out.println("批改后的链表状况");
doubleLinkedList.list();
// 删除
doubleLinkedList.del(3);
System.out.println("删除后的链表状况~~");
doubleLinkedList.list();}
}
// 创立一个双向链表的类
class DoubleLinkedList {
// 先初始化一个头节点, 头节点不要动, 不寄存具体的数据
private HeroNode2 head = new HeroNode2(0, "","");
// 返回头节点
public HeroNode2 getHead() {return head;}
// 遍历双向链表的办法
// 显示链表[遍历]
public void list() {
// 判断链表是否为空
if (head.next == null) {System.out.println("链表为空");
return;
}
// 因为头节点，不能动，因而咱们须要一个辅助变量来遍历
HeroNode2 temp = head.next;
while (true) {
// 判断是否到链表最初
if (temp == null) {break;}
// 输入节点的信息
System.out.println(temp);
// 将 temp 后移，肯定小心
temp = temp.next;
}
}
// 增加一个节点到双向链表的最初.
public void add(HeroNode2 heroNode) {
// 因为 head 节点不能动，因而咱们须要一个辅助遍历 temp
HeroNode2 temp = head;
// 遍历链表，找到最初
while (true) {
// 找到链表的最初
if (temp.next == null) {//
break;
}
// 如果没有找到最初, 将将 temp 后移
temp = temp.next;
}
// 当退出 while 循环时，temp 就指向了链表的最初
// 造成一个双向链表
temp.next = heroNode;
heroNode.pre = temp;
}
// 批改一个节点的内容, 能够看到双向链表的节点内容批改和单向链表一样
// 只是 节点类型改成 HeroNode2
public void update(HeroNode2 newHeroNode) {
// 判断是否空
if (head.next == null) {System.out.println("链表为空~");
return;
}
// 找到须要批改的节点, 依据 no 编号
// 定义一个辅助变量
HeroNode2 temp = head.next;
boolean flag = false; // 示意是否找到该节点
while (true) {if (temp == null) {break; // 曾经遍历完链表}
if (temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;
}
// 依据 flag 判断是否找到要批改的节点
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else { // 没有找到
System.out.printf("没有找到 编号 %d 的节点，不能批改 \n", newHeroNode.no);
}
}
// 从双向链表中删除一个节点,
// 阐明
// 1 对于双向链表，咱们能够间接找到要删除的这个节点
// 2 找到后，自我删除即可
public void del(int no) {
// 判断以后链表是否为空
if (head.next == null) {// 空链表
System.out.println("链表为空，无奈删除");
return;
}
HeroNode2 temp = head.next; // 辅助变量(指针)
boolean flag = false; // 标记是否找到待删除节点的
while (true) {if (temp == null) { // 曾经到链表的最初
break;
}
if (temp.no == no) {
// 找到的待删除节点的前一个节点 temp
flag = true;
break;
}
temp = temp.next; // temp 后移，遍历
}
// 判断 flag
if (flag) { // 找到
// 能够删除
// temp.next = temp.next.next;[单向链表]
temp.pre.next = temp.next;
// 这里咱们的代码有问题?
// 如果是最初一个节点，就不须要执行上面这句话，否则呈现空指针
if (temp.next != null) {temp.next.pre = temp.pre;}
} else {System.out.printf("要删除的 %d 节点不存在 \n", no);
}
}
}
// 定义 HeroNode2，每个 HeroNode 对象就是一个节点
class HeroNode2 {
public int no;
public String name;
public String nickname;
public HeroNode2 next; // 指向下一个节点, 默认为 null
public HeroNode2 pre; // 指向前一个节点, 默认为 null
// 结构器
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
// 为了显示办法，咱们从新 toString
@Override
public String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}五、栈
1、介绍
- 栈是一个先入后出 (FILO-First In Last Out) 的有序列表。
-
栈 (stack) 是限度线性表中元素的插入和删除只能在线性表的同一端进行的一种非凡线性表。容许插入和删除的一端，为变动的一端
称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
- 依据栈的定义可知，最先放入栈中元素在栈底，最初放入的元素在栈顶，而删除元素刚好相同，最初放入的元素最先删除，最先放入的元素最初删除
2、代码实现
public class MyStack {
// 用数组来存储栈
private int[] elements;
// 构造方法
public MyStack(){elements = new int[0];
}
// 获取数组长度
public int size(){return elements.length;}
// 压入元素
public void push(int ele){
// 创立新数组
int[] newArr = new int[elements.length + 1];
// 把原数组元素增加到新数组
for (int i = 0;i < elements.length;i++){newArr[i] = elements[i];
}
// 新数组增加新元素
newArr[elements.length] = ele;
// 新数组赋值给旧数组
elements = newArr;
}
// 取出栈顶元素
public int pop(){
// 栈空的话抛异样
if (elements.length == 0){throw new RuntimeException("栈中无数据, 不能弹出元素");
}
// 新建数组
int[] newArr = new int[elements.length - 1];
// 把元素放入新数组
for (int i = 0;i < newArr.length;i++){newArr[i] = elements[i];
}
// 先取出栈顶元素
int ele = elements[elements.length - 1];
// 赋值给原来的数组
elements = newArr;
// 返回栈顶元素
return ele;
}
// 查看栈顶元素
public int showPeek(){
// 栈空的话抛异样
if (elements.length == 0){throw new RuntimeException("栈中无数据, 不能查看栈顶元素");
}
return elements[elements.length - 1];
}
// 判断栈是否为空
public boolean isEmpty(){return elements.length == 0;}
}测试。
public class TestMyStack {public static void main(String[] args) {MyStack myStack = new MyStack();
myStack.push(10);
myStack.push(20);
myStack.push(30);
System.out.println(myStack.isEmpty());
System.out.println(myStack.showPeek());
System.out.println(myStack.pop());
System.out.println(myStack.showPeek());
System.out.println(myStack.pop());
System.out.println(myStack.showPeek());
System.out.println(myStack.pop());
System.out.println(myStack.isEmpty());
}
}六、递归
1、介绍
递归就是办法本人调用本人, 每次调用时传入不同的变量. 递归有助于编程者解决简单的问题, 同时能够让代码变得简洁。
2、一般代码实现
public class TestRecursive {public static void main(String[] args) {show(10);
}
public static void show(int i){if (i > 0){System.out.println(i);
show(--i);
}
}
}3、汉诺塔问题实现
public class TestHanoi {public static void main(String[] args) {hanoi(3,'A','B','C');
}
/**
* 汉诺塔实现逻辑
* @param n 一共有几个盘子
* @param start 起始地位
* @param middle 转换地位
* @param end 指标地位
*/
public static void hanoi(int n,char start,char middle,char end){if (n == 1){System.out.println("把第 1 个盘子从" + start + "挪到" + end);
}
else{
// 把最初一个下面的盘子都挪走
hanoi(n - 1,start,end,middle);
System.out.println("第" + n + "个盘子从" + start + "挪到" + end);
hanoi(n-1,middle,start,end);
}
}
}4、斐波那契而数列问题实现
public class TestFebonacci {public static void main(String[] args) {System.out.println(febonacci(8));
}
public static int febonacci(int i) {if (i == 1 || i == 2){return 1;}
return febonacci(i - 1) + febonacci(i - 2);
}
}七、树
1、介绍
树是一种非线性的数据结构，它是由 n（n>=0）个无限结点组成一个具备档次关系的汇合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 根结点：根节点没有前驱结点。
- 除根节点外，其余结点被分成是一棵构造与树相似的子树。每棵子树的根结点有且只有一个前驱，能够有 0 个或多个后继。
- 因而，树是递归定义的。
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/20210319015701606.png” alt=”img” style=”zoom: 67%;” />
2、几个罕用的概念
- 节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A 的为 2
- 叶节点：度为 0 的节点称为叶节点；如上图：G、H、I 节点为叶节点
- 非终端节点或分支节点：度不为 0 的节点；如上图：B、D、C、E、F 节点为分支节点
- 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A 是 B 的父节点
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B 是 A 的孩子节点
- 兄弟节点：具备雷同父节点的节点互称为兄弟节点；如上图：B、C 是兄弟节点
- 树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为 2
- 节点的档次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；
- 树的高度或深度：树中节点的最大档次；如上图：树的高度为 4
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I 互为兄弟节点
- 节点的先人：从根到该节点所经分支上的所有节点；如上图：A 是所有节点的先人
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是 A 的子孙
- 森林：由 m 棵互不相交的树的汇合称为森林；
3、二叉树
3.1 介绍
一棵二叉树是结点的一个无限汇合，该汇合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：
- 每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。
- 二叉树的子树有左右之分，其子树的秩序不能颠倒。
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/20210319150612530.png” alt=” 在这里插入图片形容 ” style=”zoom: 80%;” />
3.2 存储构造
二叉树个别能够应用两种存储构造，一种程序构造，一种链式构造。
3.3 链式存储二叉树
代码实现：
创立节点代码：
public class TreeNode {
// 节点三元素
private Integer value;
private TreeNode leftNode;
private TreeNode rightNode;
// 初始化一个节点须要给它指定一个值
public TreeNode(Integer value) {this.value = value;}
// 给元素赋值
public void setLeftNode(TreeNode leftNode) {this.leftNode = leftNode;}
public void setRightNode(TreeNode rightNode) {this.rightNode = rightNode;}
public Integer getValue() {return value;}
public void setValue(Integer value) {this.value = value;}
// 前序遍历
public void frontShow(){System.out.println(value);
if (leftNode != null){leftNode.frontShow();
}
if (rightNode != null){rightNode.frontShow();
}
}
// 中序遍历
public void midShow(){if (leftNode != null){leftNode.midShow();
}
System.out.println(value);
if (rightNode != null){rightNode.midShow();
}
}
// 后序遍历
public void afterShow(){if (leftNode != null){leftNode.afterShow();
}
if (rightNode != null){rightNode.afterShow();
}
System.out.println(value);
}
// 前序查找
public TreeNode frontSearch(int num){
TreeNode target = null;
if (value == num){return this;}else{if (leftNode != null){target = leftNode.frontSearch(num);
}
if (target != null){return target;}
if (rightNode != null){target = rightNode.frontSearch(num);
}
}
return target;
}
@Override
public String toString() {
return "TreeNode{" +
"value=" + value +
", leftNode=" + leftNode +
", rightNode=" + rightNode +
'}';
}
// 删除子树
public void delete(int num){
TreeNode parent = this;
if (parent.leftNode != null && parent.leftNode.value == num){
parent.leftNode = null;
return;
}
if (parent.rightNode != null && parent.rightNode.value == null){
parent.rightNode = null;
return;
}
parent = leftNode;
if (parent != null){leftNode.delete(num);
};
parent = rightNode;
if (parent != null){rightNode.delete(num);
}
}
}创立二叉树的代码：
public class BinaryTree {
TreeNode root;
// 二叉树要设置根节点
public TreeNode getRoot() {return root;}
public void setRoot(TreeNode root) {this.root = root;}
public void frontShow(){root.frontShow();
}
public void midShow(){root.midShow();
}
public void afterShow(){root.afterShow();
}
public TreeNode frontSearch(int num){return root.frontSearch(num);
}
public void delete(int num){root.delete(num);
}
}测试：
public class TestBinaryTree {public static void main(String[] args) {BinaryTree tree = new BinaryTree();
TreeNode node_01_01 = new TreeNode(1);
// 树设置了根节点
tree.setRoot(node_01_01);
TreeNode node_02_02 = new TreeNode(2);
TreeNode node_02_03 = new TreeNode(3);
node_01_01.setLeftNode(node_02_02);
node_01_01.setRightNode(node_02_03);
TreeNode node_03_04 = new TreeNode(4);
TreeNode node_03_05 = new TreeNode(5);
TreeNode node_03_06 = new TreeNode(6);
TreeNode node_03_07 = new TreeNode(7);
node_02_02.setLeftNode(node_03_04);
node_02_02.setRightNode(node_03_05);
node_02_03.setLeftNode(node_03_06);
node_02_03.setRightNode(node_03_07);
TreeNode node_04_08 = new TreeNode(8);
TreeNode node_04_09 = new TreeNode(9);
TreeNode node_04_10 = new TreeNode(10);
TreeNode node_04_11 = new TreeNode(11);
TreeNode node_04_12 = new TreeNode(12);
TreeNode node_04_13 = new TreeNode(13);
TreeNode node_04_14 = new TreeNode(14);
TreeNode node_04_15 = new TreeNode(15);
node_03_04.setLeftNode(node_04_08);
node_03_04.setRightNode(node_04_09);
node_03_05.setLeftNode(node_04_10);
node_03_05.setRightNode(node_04_11);
node_03_06.setLeftNode(node_04_12);
node_03_06.setRightNode(node_04_13);
node_03_07.setLeftNode(node_04_14);
node_03_07.setRightNode(node_04_15);
tree.delete(5);
tree.frontShow();}
}3.4 顺序存储二叉树
其实每一个二叉树都能够转换为一个数组，一个数组也能够变为一个二叉树。然而个别只思考齐全二叉树的状况，因为其余状况可能数组两头存在空值。
下面这个二叉树能够变为如下数组：
这样能够依据下面这个二叉树来推断出下标：
- 父节点下标为 n，则它的左子节点下标（2n+1）
- 父节点下标为 n，则它的右子节点下标（2n+2）
- 子节点下标为 n，则它的父节点下标为（n-1)/2
代码实现：
public class ArrayBinaryTree {int[] data;
public ArrayBinaryTree(int[] data) {this.data = data;}
public void frontShow(){frontShow(0);
}
public void frontShow(int index){if (data == null || data.length == 0){return;}
// 先遍历以后节点的内容
System.out.println(data[index]);
if (2*index + 1 < data.length){frontShow(2*index + 1);
}
if (2*index + 2 < data.length){frontShow(2*index + 2);
}
}
}输入对应下标的值：
public class TestArrayBinaryTree {public static void main(String[] args) {int[] array = new int[]{1,2,3,5,7,11,14,145};
ArrayBinaryTree tree = new ArrayBinaryTree(array);
tree.frontShow(7);
}
}4、线索二叉树
节点：
public class ThreadedNode {
// 节点的权
int value;
// 左儿子
ThreadedNode leftNode;
// 右儿子
ThreadedNode rightNode;
// 标识指针类型
int leftType;
int rightType;
public ThreadedNode(int value) {this.value=value;}
// 设置左儿子
public void setLeftNode(ThreadedNode leftNode) {this.leftNode = leftNode;}
// 设置右儿子
public void setRightNode(ThreadedNode rightNode) {this.rightNode = rightNode;}
// 前序遍历
public void frontShow() {
// 先遍历以后节点的内容
System.out.println(value);
// 左节点
if(leftNode!=null) {leftNode.frontShow();
}
// 右节点
if(rightNode!=null) {rightNode.frontShow();
}
}
// 中序遍历
public void midShow() {
// 左子节点
if(leftNode!=null) {leftNode.midShow();
}
// 以后节点
System.out.println(value);
// 右子节点
if(rightNode!=null) {rightNode.midShow();
}
}
// 后序遍历
public void afterShow() {
// 左子节点
if(leftNode!=null) {leftNode.afterShow();
}
// 右子节点
if(rightNode!=null) {rightNode.afterShow();
}
// 以后节点
System.out.println(value);
}
// 前序查找
public ThreadedNode frontSearch(int i) {
ThreadedNode target=null;
// 比照以后节点的值
if(this.value==i) {
return this;
// 以后节点的值不是要查找的节点
}else {
// 查找左儿子
if(leftNode!=null) {
// 有可能能够查到，也能够查不到，查不到的话，target 还是一个 null
target = leftNode.frontSearch(i);
}
// 如果不为空，阐明在左儿子中曾经找到
if(target!=null) {return target;}
// 查找右儿子
if(rightNode!=null) {target=rightNode.frontSearch(i);
}
}
return target;
}
// 删除一个子树
public void delete(int i) {
ThreadedNode parent = this;
// 判断左儿子
if(parent.leftNode!=null&&parent.leftNode.value==i) {
parent.leftNode=null;
return;
}
// 判断右儿子
if(parent.rightNode!=null&&parent.rightNode.value==i) {
parent.rightNode=null;
return;
}
// 递归查看并删除左儿子
parent=leftNode;
if(parent!=null) {parent.delete(i);
}
// 递归查看并删除右儿子
parent=rightNode;
if(parent!=null) {parent.delete(i);
}
}
}树的实现代码：
public class ThreadedBinaryTree {
ThreadedNode root;
// 用于长期存储前驱节点
ThreadedNode pre=null;
// 遍历线索二叉树
public void threadIterate() {
// 用于长期存储以后遍历节点
ThreadedNode node = root;
while(node!=null) {
// 循环找到最开始的节点
while(node.leftType==0) {node=node.leftNode;}
// 打印以后节点的值
System.out.println(node.value);
// 如果以后节点的右指针指向的是后继节点，可能后继节点还有后继节点、while(node.rightType==1) {
node=node.rightNode;
System.out.println(node.value);
}
// 替换遍历的节点
node=node.rightNode;
}
}
// 设置根节点
public void setRoot(ThreadedNode root) {this.root = root;}
// 中序线索化二叉树
public void threadNodes() {threadNodes(root);
}
public void threadNodes(ThreadedNode node) {
// 以后节点如果为 null，间接返回
if(node==null) {return;}
// 解决左子树
threadNodes(node.leftNode);
// 解决前驱节点
if(node.leftNode==null){
// 让以后节点的左指针指向前驱节点
node.leftNode=pre;
// 扭转以后节点左指针的类型
node.leftType=1;
}
// 解决前驱的右指针，如果前驱节点的右指针是 null(没有指下右子树)
if(pre!=null&&pre.rightNode==null) {
// 让前驱节点的右指针指向以后节点
pre.rightNode=node;
// 扭转前驱节点的右指针类型
pre.rightType=1;
}
// 每解决一个节点，以后节点是下一个节点的前驱节点
pre=node;
// 解决右子树
threadNodes(node.rightNode);
}
// 获取根节点
public ThreadedNode getRoot() {return root;}
// 前序遍历
public void frontShow() {if(root!=null) {root.frontShow();
}
}
// 中序遍历
public void midShow() {if(root!=null) {root.midShow();
}
}
// 后序遍历
public void afterShow() {if(root!=null) {root.afterShow();
}
}
// 前序查找
public ThreadedNode frontSearch(int i) {return root.frontSearch(i);
}
// 删除子树
public void delete(int i) {if(root.value==i) {root=null;}else {root.delete(i);
}
}
}测试：
public class TestThreadedBinaryTree {public static void main(String[] args) {
// 创立一颗树
ThreadedBinaryTree binTree = new ThreadedBinaryTree();
// 创立一个根节点
ThreadedNode root = new ThreadedNode(1);
// 把根节点赋给树
binTree.setRoot(root);
// 创立一个左节点
ThreadedNode rootL = new ThreadedNode(2);
// 把新创建的节点设置为根节点的子节点
root.setLeftNode(rootL);
// 创立一个右节点
ThreadedNode rootR = new ThreadedNode(3);
// 把新创建的节点设置为根节点的子节点
root.setRightNode(rootR);
// 为第二层的左节点创立两个子节点
rootL.setLeftNode(new ThreadedNode(4));
ThreadedNode fiveNode = new ThreadedNode(5);
rootL.setRightNode(fiveNode);
// 为第二层的右节点创立两个子节点
rootR.setLeftNode(new ThreadedNode(6));
rootR.setRightNode(new ThreadedNode(7));
// 中序遍历树
binTree.midShow();
System.out.println("===============");
// 中前线索化二叉树
binTree.threadNodes();
binTree.threadIterate();}
}5、赫夫曼树
5.1 介绍
叶子节点的带权门路：如上图所示，每个节点（A/B/C/D）上的线段上都有一段数字，它就是权，带权门路就是走过了几个这样的线段 * 权值。
比方（a）图中 A 的带权门路就是 9×2 = 18，B 的带权门路就是 4×2 = 8.
树的带权门路长度 WPL：是一棵树的所有叶子节点的带权门路之和。
那么计算一下：
（a）图中的 WPL：9×2 + 4×2 + 5×2 + 2×2 = 40
（b）图中的 WPL：9×1 + 5×2 + 4×3 + 2×3 = 37
（c）图中的 WPL：4×1 + 2×2 + 5×3 +9×3 =50
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权门路长度（WPL）最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。也就是说 b 是赫夫曼树。
5.2 实践实现
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个卓有成效的方法：
- 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
- 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值退出到 n–2 个权值的行列中，以此类推；
- 反复 1 和 2，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
5.3 代码实现
创立节点：
public class Node implements Comparable<Node> {
int value;
Node left;
Node right;
public Node(int value) {this.value = value;}
@Override
public int compareTo(Node o) {return -(this.value - o.value);
}
@Override
public String toString() {return "Node [value=" + value + "]";
}
}赫夫曼树：
public class TestHuffmanTree {public static void main(String[] args) {int[] arr = {3,7,8,29,5,11,23,14};
Node node = createHuffmanTree(arr);
System.out.println(node);
}
// 创立赫夫曼树
public static Node createHuffmanTree(int[] arr) {
// 先应用数组中所有的元素创立若干个二叉树，（只有一个节点）List<Node> nodes = new ArrayList<>();
for(int value:arr) {nodes.add(new Node(value));
}
// 循环解决，while(nodes.size()>1) {
// 排序
Collections.sort(nodes);
// 取出来权值最小的两个二叉树
// 取出最权值最小的二叉树
Node left = nodes.get(nodes.size()-1);
// 取出最权值次小的二叉树
Node right = nodes.get(nodes.size()-2);
// 创立一颗新的二叉树
Node parent = new Node(left.value+right.value);
// 把取出来的两个二叉树移除
nodes.remove(left);
nodes.remove(right);
// 放入原来的二叉树汇合中
nodes.add(parent);
}
return nodes.get(0);
}
}5.4 赫夫曼编码
举例：比方要传递这样一个语句 can you can a can as a can canner can a can.
如果依照以往的编码模式，对每个单词间接进行编码，咱们会看到十分宏大的二进制字节码。
先变成这样：
99 97 110 32 121 111 117 32 99 97 110 32 97 32 99 97 110 32 97 115 32 97 32 99 97 110 32 99 97 110 110 101 114 32 99 97 110 32 97 32 99 97 110 46
而后变成这样：长度一共是 396
01100011 01100001 01101110 00100000 01111001 01101111 01110101 00100000 01100011 01100001 01101110 00100000 01100001 00100000 01100011 01100001 01101110 00100000 01100001 01110011 00100000 01100001 00100000 01100011 01100001 01101110 00100000 01100011 01100001 01101110 01101110 01100101 01110010 00100000 01100011 01100001 01101110 00100000 01100001 00100000 01100011 01100001 01101110 00101110
这样存储的太多了，很吃内存。
那么有人思考不如换一种形式吧：
先记录下每个字母呈现的次数：r:1 s:1 u:1 e:1 y:1 .:1 o:1 c:7 n:8 空格:11 a:11
那么把呈现最多的字母用比拟小的数字示意，呈现比拟少的字母用大的数字示意就能够解决这个问题了。
比方依照这个逻辑：0=a,1= 空格,10=n,11=c,100=o,101=.,110=y,111=e,1000=u,1001=s,1010=r
那么就变成了这个模式：11 0 10 1 110 100 11010111001010011……
理论字节码是没有空格的：11010111010011010111001010011…
这样又有了一个问题，到底怎么断句啊，第一个是 1，是 11，还是 110？
这个时候就能够采纳赫夫曼树来寄存了。如下图：
那么每个字符的编码就能够依照下面的权来寄存。
这样能够保证数据的唯一性。
保留的字符编码如下：
111 10 00 01 110010 11000 110100 01 111 10 00 01 10 01 111 10 00 01 10 110111 01 10 01 111 10 00 01 111 10 00 00 110101 110110 01 111 10 00 01 10 01 111 10 00 110011
去掉空格：长度一共是 122
11110000111001011000110100011111000011001111100001101101110110011111000011111000001101011101100111110000110011111000110011
从 396 到 122 可见压缩了十分多。
代码实现：
应该分为如下几步：
- 统计字符数而后排序
- 创立赫夫曼树
- 创立赫夫曼编码表
- 编码
创立节点：
public class Node implements Comparable<Node> {
Byte data;
int weight;
Node left;
Node right;
public Node(Byte data,int weight) {
this.data=data;
this.weight=weight;
}
@Override
public String toString() {return "Node [data=" + data + ", weight=" + weight + "]";
}
@Override
public int compareTo(Node o) {return o.weight-this.weight;}
}创立赫夫曼树：
public class TestHuffmanCode {public static void main(String[] args) {
// String msg="can you can a can as a can canner can a can.";
// byte[] bytes = msg.getBytes();
// // 进行赫夫曼编码压缩
// byte[] b = huffmanZip(bytes);
// // 应用赫夫曼编码进行解码
// byte[] newBytes = decode(huffCodes,b);
// System.out.println(new String(newBytes));
String src="1.bmp";
String dst="2.zip";
// try {// zipFile(src, dst);
// } catch (IOException e) {// e.printStackTrace();
// }
try {unZip("2.zip", "3.bmp");
} catch (Exception e) {e.printStackTrace();
}
}
/**
* 文件的解压
* @param src
* @param dst
* @throws Exception
*/
public static void unZip(String src,String dst) throws Exception {
// 创立一个输出流
InputStream is = new FileInputStream("2.zip");
ObjectInputStream ois = new ObjectInputStream(is);
// 读取 byte 数组
byte[] b = (byte[]) ois.readObject();
// 读取赫夫曼编码表
Map<Byte, String> codes = (Map<Byte, String>) ois.readObject();
ois.close();
is.close();
// 解码
byte[] bytes = decode(codes, b);
// 创立一个输入流
OutputStream os = new FileOutputStream(dst);
// 写出数据
os.write(bytes);
os.close();}
/**
* 压缩文件
* @param src
* @param dst
* @throws IOException
*/
public static void zipFile(String src,String dst) throws IOException {
// 创立一个输出流
InputStream is = new FileInputStream(src);
// 创立一个和输出流指向的文件大小一样的 byte 数组
byte[] b = new byte[is.available()];
// 读取文件内容
is.read(b);
is.close();
// 应用赫夫曼编码进行编码
byte[] byteZip = huffmanZip(b);
// 输入流
OutputStream os = new FileOutputStream(dst);
ObjectOutputStream oos = new ObjectOutputStream(os);
// 把压缩后的 byte 数组写入文件
oos.writeObject(byteZip);
// 把赫夫曼编码表写入文件
oos.writeObject(huffCodes);
oos.close();
os.close();}
/**
* 应用指定的赫夫曼编码表进行解码
* @param huffCodes2
* @param b
* @return
*/
private static byte[] decode(Map<Byte, String> huffCodes, byte[] bytes) {StringBuilder sb = new StringBuilder();
// 把 byte 数组转为一个二进制的字符串
for(int i=0;i<bytes.length;i++) {byte b = bytes[i];
// 是否是最初一个。boolean flag = (i==bytes.length-1);
sb.append(byteToBitStr(!flag,b));
}
// 把字符串依照指定的赫夫曼编码进行解码
// 把赫夫曼编码的键值对进行调换
Map<String, Byte> map = new HashMap<>();
for(Map.Entry<Byte, String> entry:huffCodes.entrySet()) {map.put(entry.getValue(), entry.getKey());
}
// 创立一个汇合，用于存 byte
List<Byte> list = new ArrayList<>();
// 解决字符串
for(int i=0;i<sb.length();) {
int count=1;
boolean flag = true;
Byte b=null;
// 截取出一个 byte
while(flag) {String key = sb.substring(i, i+count);
b = map.get(key);
if(b==null) {count++;}else {flag=false;}
}
list.add(b);
i+=count;
}
// 把汇合转为数组
byte[] b = new byte[list.size()];
for(int i=0;i<b.length;i++) {b[i]=list.get(i);
}
return b;
}
private static String byteToBitStr(boolean flag,byte b) {
int temp=b;
if(flag) {temp|=256;}
String str = Integer.toBinaryString(temp);
if(flag) {return str.substring(str.length()-8);
}else {return str;}
}
/**
* 进行赫夫曼编码压缩的办法
* @param bytes
* @return
*/
private static byte[] huffmanZip(byte[] bytes) {
// 先统计每一个 byte 呈现的次数，并放入一个汇合中
List<Node> nodes = getNodes(bytes);
// 创立一颗赫夫曼树
Node tree = createHuffmanTree(nodes);
// 创立一个赫夫曼编码表
Map<Byte, String> huffCodes = getCodes(tree);
// 编码
byte[] b = zip(bytes,huffCodes);
return b;
}
/**
* 进行赫夫曼编码
* @param bytes
* @param huffCodes2
* @return
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {StringBuilder sb = new StringBuilder();
// 把须要压缩的 byte 数组解决成一个二进制的字符串
for(byte b:bytes) {sb.append(huffCodes.get(b));
}
// 定义长度
int len;
if(sb.length()%8==0) {len=sb.length()/8;
}else {len=sb.length()/8+1;
}
// 用于存储压缩后的 byte
byte[] by = new byte[len];
// 记录新 byte 的地位
int index = 0;
for(int i=0;i<sb.length();i+=8) {
String strByte;
if(i+8>sb.length()) {strByte = sb.substring(i);
}else {strByte = sb.substring(i, i+8);
}
byte byt = (byte)Integer.parseInt(strByte, 2);
by[index]=byt;
index++;
}
return by;
}
// 用于长期存储门路
static StringBuilder sb = new StringBuilder();
// 用于存储赫夫曼编码
static Map<Byte, String> huffCodes = new HashMap<>();
/**
* 依据赫夫曼树获取赫夫曼编码
* @param tree
* @return
*/
private static Map<Byte, String> getCodes(Node tree) {if(tree==null) {return null;}
getCodes(tree.left,"0",sb);
getCodes(tree.right,"1",sb);
return huffCodes;
}
private static void getCodes(Node node, String code, StringBuilder sb) {StringBuilder sb2 = new StringBuilder(sb);
sb2.append(code);
if(node.data==null) {getCodes(node.left, "0", sb2);
getCodes(node.right, "1", sb2);
}else {huffCodes.put(node.data, sb2.toString());
}
}
/**
* 创立赫夫曼树
* @param nodes
* @return
*/
private static Node createHuffmanTree(List<Node> nodes) {while(nodes.size()>1) {
// 排序
Collections.sort(nodes);
// 取出两个权值最低的二叉树
Node left = nodes.get(nodes.size()-1);
Node right = nodes.get(nodes.size()-2);
// 创立一颗新的二叉树
Node parent = new Node(null, left.weight+right.weight);
// 把之前取出来的两颗二叉树设置为新创建的二叉树的子树
parent.left=left;
parent.right=right;
// 把后面取出来的两颗二叉树删除
nodes.remove(left);
nodes.remove(right);
// 把新创建的二叉树放入汇合中
nodes.add(parent);
}
return nodes.get(0);
}
/**
* 把 byte 数组转为 node 汇合
* @param bytes
* @return
*/
private static List<Node> getNodes(byte[] bytes) {List<Node> nodes = new ArrayList<>();
// 存储每一个 byte 呈现了多少次。Map<Byte, Integer> counts = new HashMap<>();
// 统计每一个 byte 呈现的次数
for(byte b:bytes) {Integer count = counts.get(b);
if(count==null) {counts.put(b, 1);
}else {counts.put(b, count+1);
}
}
// 把每一个键值对转为一个 node 对象
for(Map.Entry<Byte, Integer> entry:counts.entrySet()) {nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
}6、二叉排序树
6.1 介绍
具备如下特点：
- 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
- 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
- 二叉排序树的左右子树也要求都是二叉排序树；
6.2 代码实现
节点：
public class Node {
int value;
Node left;
Node right;
public Node(int value) {this.value=value;}
/**
* 向子树中增加节点
* @param node
*/
public void add(Node node) {if(node==null) {return;}
// 判断传入的节点的值比以后子树的根节点的值大还是小
// 增加的节点比以后节点的值更小
if(node.value<this.value) {
// 如果左节点为空
if(this.left==null) {
this.left=node;
// 如果不为空
}else {this.left.add(node);
}
}else {if(this.right==null) {this.right=node;}else {this.right.add(node);
}
}
}
/**
* 中序遍历
* @param node
*/
public void midShow(Node node) {if(node==null) {return;}
midShow(node.left);
System.out.println(node.value);
midShow(node.right);
}
/**
* 查找节点
* @param value2
*/
public Node search(int value) {if(this.value==value) {return this;}else if(value<this.value) {if(left==null) {return null;}
return left.search(value);
}else{if(right==null) {return null;}
return right.search(value);
}
}
/**
* 搜寻父节点
* @param value
* @return
*/
public Node searchParent(int value) {if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)) {return this;}else {if(this.value>value&&this.left!=null) {return this.left.searchParent(value);
}else if(this.value<value&&this.right!=null){return this.right.searchParent(value);
}
return null;
}
}
}二叉排序树：
public class BinarySortTree {
Node root;
/**
* 向二叉排序树中增加节点
* @param node
*/
public void add(Node node){
// 如果是一颗空树
if(root==null) {root=node;}else {root.add(node);
}
}
/**
* 中序遍历二叉排序树，从小到大的程序
*/
public void midShow() {if(root!=null) {root.midShow(root);
}
}
/**
* 节点的查找
* @param value
* @return
*/
public Node search(int value) {if(root==null) {return null;}else {return root.search(value);
}
}
/**
* 删除节点
* @param value
*/
public void delete(int value) {if(root==null) {return;}else {
// 找到这个节点
Node target = search(value);
// 如果没有这个节点
if(target==null) {return;}
// 找到他的父节点
Node parent = searchParent(value);
// 要删除的节点是叶子节点
if(target.left==null&&target.right==null) {
// 要删除的节点是父节点的左子节点
if(parent.left.value==value) {
parent.left=null;
// 要删除的节点是父节点的右子节点
}else {parent.right=null;}
// 要删除的节点有两个子节点的状况
}else if(target.left!=null&&target.right!=null) {
// 删除右子树中值最小的节点，取获取到该节点的值
int min = deleteMin(target.right);
// 替换指标节点中的值
target.value=min;
// 要删除的节点有一个左子节点或右子节点
}else {
// 有左子节点
if(target.left!=null) {
// 要删除的节点是父节点的左子节点
if(parent.left.value==value) {
parent.left=target.left;
// 要删除的节点是父节点的右子节点
}else {parent.right=target.left;}
// 有右子节点
}else {
// 要删除的节点是父节点的左子节点
if(parent.left.value==value) {
parent.left=target.right;
// 要删除的节点是父节点的右子节点
}else {parent.right=target.right;}
}
}
}
}
/**
* 删除一颗树中最小的节点
* @param right
* @return
*/
private int deleteMin(Node node) {
Node target = node;
// 递归向左找
while(target.left!=null) {target=target.left;}
// 删除最小的这个节点
delete(target.value);
return target.value;
}
/**
* 搜寻父节点
* @param value
* @return
*/
public Node searchParent(int value) {if(root==null) {return null;}else {return root.searchParent(value);
}
}
}测试：
public class TestBinarySortTree {public static void main(String[] args) {int[] arr = new int[] {7,3,10,12,5,1,9};
// 创立一颗二叉排序树
BinarySortTree bst = new BinarySortTree();
// 循环增加
for(int i:arr) {bst.add(new Node(i));
}
// 查看树中的值
bst.midShow();
System.out.println("-----");
// 查找
// Node node = bst.search(10);
// System.out.println(node.value);
//
// Node node2 = bst.search(20);
// System.out.println(node2);
// // 测试查找父节点
// Node p1 = bst.searchParent(12);
// System.out.println(p1.value);
// System.out.println("-----");
// 删除叶子节点
// bst.delete(5);
// bst.midShow();
// System.out.println("===");
// 删除只有一个子节点的节点
// bst.delete(3);
// bst.midShow();
// 删除有两个子节点的节点
bst.delete(3);
System.out.println("----");
bst.midShow();}
}7、AVL 树（均衡二叉树）
7.1 介绍
均衡二叉树（Balanced Binary Tree）又被称为 AVL 树（有别于 AVL 算法），且具备以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵均衡二叉树。这个计划很好的解决了二叉查找树进化成链表的问题，把插入，查找，删除的工夫复杂度最好状况和最坏状况都维持在 O(logN)。然而频繁旋转会使插入和删除就义掉 O(logN)左右的工夫，不过绝对二叉查找树来说，工夫上稳固了很多。
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/080001386298697.jpg” alt=”img” style=”zoom:80%;” />
7.2 旋转代码实现
public class Node {
int value;
Node left;
Node right;
public Node(int value) {this.value=value;}
/**
* 返回以后节点的高度
* @return
*/
public int height() {return Math.max(left==null?0:left.height(), right==null?0:right.height())+1;
}
/**
* 获取左子树的高度
* @return
*/
public int leftHeight() {if(left==null) {return 0;}
return left.height();}
/**
* 获取右子树的高度
* @return
*/
public int rightHeight() {if(right==null) {return 0;}
return right.height();}
/**
* 向子树中增加节点
* @param node
*/
public void add(Node node) {if(node==null) {return;}
// 判断传入的节点的值比以后子树的根节点的值大还是小
// 增加的节点比以后节点的值更小
if(node.value<this.value) {
// 如果左节点为空
if(this.left==null) {
this.left=node;
// 如果不为空
}else {this.left.add(node);
}
}else {if(this.right==null) {this.right=node;}else {this.right.add(node);
}
}
// 查问是否均衡
// 进行右旋转
if(leftHeight()-rightHeight()>=2) {
// 双旋转
if(left!=null&&left.leftHeight()<left.rightHeight()) {
// 先左旋转
left.leftRotate();
// 再右旋转
rightRotate();
// 单旋转
}else {rightRotate();
}
}
// 左旋转
if(leftHeight()-rightHeight()<=-2) {
// 双旋转
if(right!=null&&right.rightHeight()<right.leftHeight()) {right.rightRotate();
leftRotate();
// 单旋转
}else {leftRotate();
}
}
}
/**
* 左旋转
*/
private void leftRotate() {Node newLeft = new Node(value);
newLeft.left=left;
newLeft.right=right.left;
value=right.value;
right=right.right;
left=newLeft;
}
/**
* 右旋转
*/
private void rightRotate() {
// 创立一个新的节点，值等于以后节点的值
Node newRight = new Node(value);
// 把新节点的右子树设置了以后节点的右子树
newRight.right=right;
// 把新节点的左子树设置为以后节点的左子树的右子树
newRight.left=left.right;
// 把以后节点的值换为左子节点的值
value=left.value;
// 把以后节点的左子树设置了左子树的左子树
left=left.left;
// 把以后节点的右子树设置为新节点
right=newRight;
}
/**
* 中序遍历
* @param node
*/
public void midShow(Node node) {if(node==null) {return;}
midShow(node.left);
System.out.println(node.value);
midShow(node.right);
}
/**
* 查找节点
* @param value2
*/
public Node search(int value) {if(this.value==value) {return this;}else if(value<this.value) {if(left==null) {return null;}
return left.search(value);
}else{if(right==null) {return null;}
return right.search(value);
}
}
/**
* 搜寻父节点
* @param value
* @return
*/
public Node searchParent(int value) {if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)) {return this;}else {if(this.value>value&&this.left!=null) {return this.left.searchParent(value);
}else if(this.value<value&&this.right!=null){return this.right.searchParent(value);
}
return null;
}
}
}均衡二叉树
public class BinarySortTree {
Node root;
/**
* 向二叉排序树中增加节点
* @param node
*/
public void add(Node node){
// 如果是一颗空树
if(root==null) {root=node;}else {root.add(node);
}
}
/**
* 中序遍历二叉排序树，从小到大的程序
*/
public void midShow() {if(root!=null) {root.midShow(root);
}
}
/**
* 节点的查找
* @param value
* @return
*/
public Node search(int value) {if(root==null) {return null;}else {return root.search(value);
}
}
/**
* 删除节点
* @param value
*/
public void delete(int value) {if(root==null) {return;}else {
// 找到这个节点
Node target = search(value);
// 如果没有这个节点
if(target==null) {return;}
// 找到他的父节点
Node parent = searchParent(value);
// 要删除的节点是叶子节点
if(target.left==null&&target.right==null) {
// 要删除的节点是父节点的左子节点
if(parent.left.value==value) {
parent.left=null;
// 要删除的节点是父节点的右子节点
}else {parent.right=null;}
// 要删除的节点有两个子节点的状况
}else if(target.left!=null&&target.right!=null) {
// 删除右子树中值最小的节点，取获取到该节点的值
int min = deleteMin(target.right);
// 替换指标节点中的值
target.value=min;
// 要删除的节点有一个左子节点或右子节点
}else {
// 有左子节点
if(target.left!=null) {
// 要删除的节点是父节点的左子节点
if(parent.left.value==value) {
parent.left=target.left;
// 要删除的节点是父节点的右子节点
}else {parent.right=target.left;}
// 有右子节点
}else {
// 要删除的节点是父节点的左子节点
if(parent.left.value==value) {
parent.left=target.right;
// 要删除的节点是父节点的右子节点
}else {parent.right=target.right;}
}
}
}
}
/**
* 删除一颗树中最小的节点
* @param right
* @return
*/
private int deleteMin(Node node) {
Node target = node;
// 递归向左找
while(target.left!=null) {target=target.left;}
// 删除最小的这个节点
delete(target.value);
return target.value;
}
/**
* 搜寻父节点
* @param value
* @return
*/
public Node searchParent(int value) {if(root==null) {return null;}else {return root.searchParent(value);
}
}
}测试：
public class TestBinarySortTree {public static void main(String[] args) {// int[] arr = new int[] {8,9,6,7,5,4};
int[] arr = new int[] {8,9,5,4,6,7};
// 创立一颗二叉排序树
BinarySortTree bst = new BinarySortTree();
// 循环增加
for(int i:arr) {bst.add(new Node(i));
}
// 查看高度
System.out.println(bst.root.height());
//
System.out.println(bst.root.value);
}
}8、多路查找树
8.1 计算机的存储
内存存储绝对比磁盘快的多。
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL21lbmd4aWFveHUvbWVuZ3hpYW94dS5naXRodWIuaW8vbWFzdGVyL3Bvc3QtaW1hZ2VzLzE1Njk2NzkyNjY4ODIuanBn” alt=”img” style=”zoom: 67%;” />
磁盘上有一圈一圈的磁道，咱们应用磁臂来进行读写操作。这样看显著要慢的多。而且因为磁盘读取绝对较慢，磁盘会缩小磁盘的 IO 操作，它会提前预读一部分数据到内存中，这部分数据不是按需读取的，而是读取肯定长度的数据，可能这部分数据立即能用到，也可能用不到。预读的长度个别是页的整数倍。
那么再看，读取二叉树的话，会先读一部分到内存中去，但因为内存无限会把一部分数据读到磁盘中去。二叉树一个节点就是一个页。这样每次读取 IO 操作理论只存取了一个节点。
这样不如采纳多路查找树的形式。
8.2 2- 3 树
2- 3 树是最简略的 B - 树（或 - 树）构造，其每个非叶节点都有两个或三个子女，而且所有叶都在对立层上。
2- 3 树查找元素 5：
2- 3 树增加数据到一个元素的地位：
2- 3 树增加数据到两个元素的地位：
2- 3 树增加元素的另一种状况：
2- 3 树删除元素：
8.3 B 树和 B + 树
B 树和二三树根本相似。
八、哈希表（散列表）
1、介绍
是依据关键码值 (Key value) 而间接进行拜访的数据结构。也就是说，它通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度。这个映射函数叫做散列函数，寄存记录的数组叫做散列表。
2、代码实现
学生信息
public class StuInfo {
private int age;
private int count;
public int getAge() {return age;}
public void setAge(int age) {this.age = age;}
public int getCount() {return count;}
public void setCount(int count) {this.count = count;}
/**
* 散列函数
*/
public int hashCode() {return age;}
public StuInfo(int age, int count) {super();
this.age = age;
this.count = count;
}
public StuInfo(int age) {super();
this.age = age;
}
@Override
public String toString() {return "StuInfo [age=" + age + ", count=" + count + "]";
}
}哈希表：
public class HashTable {private StuInfo[] data = new StuInfo[100];
/**
* 向散列表中增加元素
* @param stuInfo
*/
public void put(StuInfo stuInfo) {
// 调用散列函数获取存储地位
int index = stuInfo.hashCode();
// 增加元素
data[index]=stuInfo;
}
public StuInfo get(StuInfo stuInfo) {return data[stuInfo.hashCode()];
}
@Override
public String toString() {return "HashTable [data=" + Arrays.toString(data) + "]";
}
}测试：
public class TestHashTable {public static void main(String[] args) {StuInfo s1 = new StuInfo(16, 3);
StuInfo s2 = new StuInfo(17, 11);
StuInfo s3 = new StuInfo(18, 23);
StuInfo s4 = new StuInfo(19, 24);
StuInfo s5 = new StuInfo(20, 9);
HashTable ht = new HashTable();
ht.put(s1);
ht.put(s2);
ht.put(s3);
ht.put(s4);
ht.put(s5);
System.out.println(ht);
// 想要获取的指标数据
StuInfo target = new StuInfo(18);
StuInfo info = ht.get(target);
System.out.println(info);
}
}3、地址抵触问题
3.1 凋谢地址法
产生哈希抵触后，依照某一秩序找到下一个闲暇的单元，把抵触的元素放入。
3.1.1 线性探查法
从发生冲突的单元开始探查，顺次查看下一个单元是否为空，如果到了最初一个单元还是空，那么再从表首顺次判断。如此执行直到碰到了闲暇的单元或者曾经探查完所有单元。
3.2.2 平方探查法
从发生冲突的单元加上 1^2,2^2,3^2,…,n^2，直到遇到闲暇的单元。
3.2 链地址法
将哈希值雷同的元素形成一个链表，head 放在散列表中。个别链表长度超过了 8 就转为红黑树，长度少于 6 个就变为链表。
3.3 再哈希法
同时结构多个不同的哈希函数，Hi = RHi(key) i= 1,2,3 … k; 当 H1 = RH1(key) 发生冲突时，再用 H2 = RH2(key) 进行计算，直到抵触不再产生，这种办法不易产生汇集，然而减少了计算工夫。
九、图
1、介绍
当咱们须要示意多对多的关系时，以前的树、链表等就不适合了，这个时候就用到了图。
图是一种 数据结构，其中结点能够具备零个或多个相邻元素。两个结点之间的连贯称为边。结点也能够称为顶点。
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/image-20210609165235863.png” alt=”image-20210609165235863″ style=”zoom:80%;” />
有箭头的为有向图，没有箭头的为无向图。
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/image-20210609165540606.png” alt=”image-20210609165540606″ />
图中有权值的为带权图。
2、代码实现
public class Vertex {
private String value;
public boolean visited;
public String getValue() {return value;}
public void setValue(String value) {this.value = value;}
public Vertex(String value) {super();
this.value = value;
}
@Override
public String toString() {return value;}
}图构造：
public class Graph {private Vertex[] vertex;
private int currentSize;
public int[][] adjMat;
private MyStack stack = new MyStack();
// 以后遍历的下标
private int currentIndex;
public Graph(int size) {vertex=new Vertex[size];
adjMat=new int[size][size];
}
/**
* 向图中退出一个顶点
* @param v
*/
public void addVertex(Vertex v) {vertex[currentSize++]=v;
}
public void addEdge(String v1,String v2) {
// 找出两个顶点的下标
int index1=0;
for(int i=0;i<vertex.length;i++) {if(vertex[i].getValue().equals(v1)) {
index1=i;
break;
}
}
int index2=0;
for(int i=0;i<vertex.length;i++) {if(vertex[i].getValue().equals(v2)) {
index2=i;
break;
}
}
adjMat[index1][index2]=1;
adjMat[index2][index1]=1;
}
/**
* 深度优先搜索算法遍历图
*/
public void dfs() {
// 把第 0 个顶点标记为已拜访状态
vertex[0].visited=true;
// 把第 0 个顶点的下标。stack.push(0);
// 打印顶点的值
System.out.println(vertex[0].getValue());
// 遍历
out:while(!stack.isEmpty()) {for(int i=currentIndex+1;i<vertex.length;i++) {
// 如果和下一个遍历的元素是通的
if(adjMat[currentIndex][i]==1&&vertex[i].visited==false) {
// 把下一个元素压入栈中
stack.push(i);
vertex[i].visited=true;
System.out.println(vertex[i].getValue());
continue out;
}
}
// 弹出栈顶元素
stack.pop();
// 批改以后地位为栈顶元素的地位
if(!stack.isEmpty()) {currentIndex=stack.peek();
}
}
}
}测试：
public class TestGraph {public static void main(String[] args) {Vertex v1 = new Vertex("A");
Vertex v2 = new Vertex("B");
Vertex v3 = new Vertex("C");
Vertex v4 = new Vertex("D");
Vertex v5 = new Vertex("E");
Graph g = new Graph(5);
g.addVertex(v1);
g.addVertex(v2);
g.addVertex(v3);
g.addVertex(v4);
g.addVertex(v5);
// 减少边
g.addEdge("A", "C");
g.addEdge("B", "C");
g.addEdge("A", "B");
g.addEdge("B", "D");
g.addEdge("B", "E");
for(int[] a:g.adjMat) {System.out.println(Arrays.toString(a));
}
// 深度优先遍历
g.dfs();}
}十、排序算法
0、排序算法分类
1、冒泡排序法
1.1 示意图
1.2 代码实现
public class BubbleSort {public static void main(String[] args) {int[] arr = new int[]{10,6,2,14,5,7,15,4,1,3};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr){for (int i = 0;i < arr.length;i++){for (int j = 0;j < arr.length - 1 - i;j++){if (arr[j] > arr[j+1]) {int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}2、抉择排序法
2.1 示意图
2.2 代码实现
public class SelectSort {public static void main(String[] args) {int[] elements = new int[]{10,5,15,2,6,4,14,11,1,101,23};
selectSort(elements);
System.out.println(Arrays.toString(elements));
}
public static void selectSort(int[] ele){for(int i = 0;i < ele.length;i++){
int minIndex = i;
for (int j = i + 1;j < ele.length;j++){if (ele[minIndex] > ele[j]){minIndex = j;}
}
if (minIndex != i){int temp = ele[i];
ele[i] = ele[minIndex];
ele[minIndex] = temp;
}
}
}
}3、疾速排序法
3.1 示意图
3.2 代码实现
public class QuickSort {public static void main(String[] args) {int[] arr = new int[]{10,2,5,16,3,7,17,8,4,25,-11,223,100};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int start,int end){if (start < end){
// 定义一个标准值
int standard = arr[start];
// 定义两个起始下标
int low = start;
int high = end;
// 循环了
while (low < high){
// 当左边值比标准值大的状况下，始终挪动 high 下标
while(low < high && arr[high] >= standard){high--;}
// 当发现比标准值小的状况，间接换值
arr[low] = arr[high];
while(low < high && arr[low] <= standard){low++;}
arr[high] = arr[low];
}
// 都循环完了 low = high 了，那么给 arr[low]赋值
arr[low] = standard;
quickSort(arr,start,low);
quickSort(arr,low+1,end);
}
}
}4、插入排序
4.1 示意图
4.2 代码实现
public class InsertSort {public static void main(String[] args) {int[] array = new int[]{11,5,2,16,7,3,10,3,1};
insertSort(array);
System.out.println(Arrays.toString(array));
}
/**
* 插入排序逻辑
* @param array 需排序的数组
*/
public static void insertSort(int[] array){
// 外圈管制循环次数
for (int i = 1;i < array.length;i++){
// 如果这个数比后面的数小
if (array[i] < array[i-1]){
// 把这个值先赋值给一个长期变量
int temp = array[i];
// 再赋值个二次循环的下标
int j;
// 从以后下标前一个地位往前循环，直到找到了比它小的元素
for (j = i - 1;j >= 0 && array[j] > temp;j--){array[j+1] = array[j];
}
array[j+1] = temp;
}
}
}
}5、归并排序
5.1 示意图
5.2 代码实现
public class MergeSort {public static void main(String[] args) {int[] arr = new int[]{11,5,8,18,2,5,3,9,6,13,7};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 归并排序
* @param arr
* @param low
* @param high
*/
public static void mergeSort(int[] arr,int low,int high){int middle = (low + high)/2;
if (low < high){mergeSort(arr,low,middle);
mergeSort(arr,middle+1,high);
merge(arr,low,middle,high);
}
}
/**
* 归并逻辑
* @param arr
* @param low
* @param middle
* @param high
*/
public static void merge(int[] arr,int low,int middle,int high){
// 创立一个长期数组，用于放元素
int[] temp = new int[high-low+1];
// 记录第一个数组的初始值
int i = low;
// 记录第二个数组的初始值
int j = middle + 1;
// 还须要一个下标记录新数组的地位
int index = 0;
// 循环, 如果两个数组都没循环完就持续循环
while(i <= middle && j <= high){if (arr[i] <= arr[j]){temp[index] = arr[i];
i++;
}else{temp[index] = arr[j];
j++;
}
index++;
}
// 有一个循环完了就依照这个循环，没循环完的就持续加值
while(i <= middle){temp[index] = arr[i];
i++;
index++;
}
while(j <= high){temp[index] = arr[j];
j++;
index++;
}
// 把 temp 中的值挪入原数组
for (int k = 0;k < temp.length;k++){arr[k+low] = temp[k];
}
}
}6、希尔排序
6.1 示意图
6.2 代码实现
public class ShellSort {public static void main(String[] args) {int[] arr = new int[] {11,6,5,16,2,9,1,25,5,0};
System.out.println(Arrays.toString(arr));
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
int k = 1;
// 遍历所有的步长
for (int d = arr.length / 2; d > 0; d /= 2) {
// 遍历所有有元素
for (int i = d; i < arr.length; i++) {
// 遍历本组中所有的元素
for (int j = i - d; j >= 0; j -= d) {
// 如果以后元素大于加上步长后的那个元素
if (arr[j] > arr[j + d]) {int temp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = temp;
}
}
}
System.out.println("第" + k + "次排序后果：" + Arrays.toString(arr));
k++;
}
}
}7、基数排序
7.1 示意图
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/5092611170d3423d89f7075d33104b6a.gif” alt=”img” style=”zoom:80%;” />
7.2 代码实现
public class RadixSort {public static void main(String[] args) {int[] arr = new int[] {23,6,189,45,9,287,56,1,798,34,65,652,5};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr){
// 存数组中最大的数字
int max = Integer.MIN_VALUE;
for (int i = 0;i < arr.length;i++){if (arr[i] > max){max = arr[i];
}
}
// 看看最大数是几位的
int maxLength = (max+"").length();
// 创立寄存这些数字的数组
int[][] temp = new int[10][arr.length];
// 还须要一个数组寄存有每格有几个
int[] counts = new int[10];
// 最外层循环确定要循环多少次
for (int i = 0,n = 1;i < maxLength;i++,n*=10){
// 内层循环是遍历每个数
for (int j = 0;j < arr.length;j++){
// 计算余数
int ys = arr[j]/n % 10;
temp[ys][counts[ys]] = arr[j];
counts[ys]++;
}
// 数组下标
int index = 0;
// 把元素取出来, 遍历每一列
for (int k = 0;k < counts.length;k++){
// 如果这一列不为 0
if (counts[k] != 0){
// 那么就看看外面有几个元素，取几次
for (int l = 0;l < counts[k];l++){arr[index] = temp[k][l];
index++;
}
counts[k] = 0;
}
}
}
}
}8、桶排序
8.1 示意图
8.2 代码实现
public class BottleSort {public static void main(String[] args) {int[] x = {20,12,44,145,111,22,102,122,3,14,292,15,8};
int[] sorted = bucketSort(x, 500);
for (int i = 0; i < sorted.length; i++)
{if (sorted[i] > 0)
System.out.println(sorted[i]);
}
}
public static int[] bucketSort(int[] nums, int maxNum){int[] sorted = new int[maxNum+1];
for(int i=0; i<nums.length; i++){sorted[nums[i]] = nums[i];// 把数据放到对应索引的地位
}
return sorted;
}
}9、堆排序
9.1 示意图
<img src=”https://gitee.com/yzdswzt/cloudimages/raw/master/img/20150826101207480″ alt=” 堆排序 ” style=”zoom:80%;” />
9.2 代码实现
public class HeapSort {public static void main(String[] args) {int[] arr = new int[] {9,6,8,7,0,1,10,4,2};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
// 开始地位是最初一个非叶子节点，即最初一个节点的父节点
int start = (arr.length-1)/2;
// 调整为大顶堆
for(int i=start;i>=0;i--) {maxHeap(arr, arr.length, i);
}
// 先把数组中的第 0 个和堆中的最初一个数替换地位，再把后面的解决为大顶堆
for(int i=arr.length-1;i>0;i--) {int temp = arr[0];
arr[0]=arr[i];
arr[i]=temp;
maxHeap(arr, i, 0);
}
}
public static void maxHeap(int[] arr,int size,int index) {
// 左子节点
int leftNode = 2*index+1;
// 右子节点
int rightNode = 2*index+2;
int max = index;
// 和两个子节点别离比照，找出最大的节点
if(leftNode<size&&arr[leftNode]>arr[max]) {max=leftNode;}
if(rightNode<size&&arr[rightNode]>arr[max]) {max=rightNode;}
// 替换地位
if(max!=index) {int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// 替换地位当前，可能会毁坏之前排好的堆，所以，之前的排好的堆须要从新调整
maxHeap(arr, size, max);
}
}
}