# 数据结构与算法 **Repository Path**: lzq19920606/data-structuresand-algorithms ## Basic Information - **Project Name**: 数据结构与算法 - **Description**: 数据结构与算法学习 - **Primary Language**: Java - **License**: GPL-3.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 1 - **Created**: 2024-08-07 - **Last Updated**: 2024-08-07 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README 数据结构与算法 流水不争先，争的是滔滔不绝。 数组 概述 数组（Array）是有序的元素序列。 若将有限个类型相同的变量的集合命名，那么这个名称为数组名。这些有序排列的同类数据元素的集合称为数组。数组是用于储存多个相同类型数据的集合。 下面是以创建一个稀疏数组来实现一个棋盘的存储和复现 实现 public class SparseArray { public static void main(String[] args) throws IOException { /* * 思路 * - 创建一个二维数组代表棋盘，用1来代表黑子，2来代表白子，0代表未使用 * - 设定一个sum来存储二维数组中已经被使用的个数 * - 创建一个二维数字来存储棋盘中已经使用的位置和棋子的颜色 * - 通过for循环来扫描棋盘，扫描到非0时存储到稀疏数组中 * - 复现棋盘 * - 创建一个新的二维数组，判断i与j是否与稀疏数组中的值相等，如果相等，则进行赋值 * */ int[][] c1 = new int[11][11]; c1[1][2] = 1; c1[1][3] = 2; c1[1][1] = 1; int sum = 0; for (int[] ints : c1) { for (int anInt : ints) { if (anInt != 0) sum++; } } int[][] s1 = new int[sum+1][3]; s1[0][0] = c1.length; s1[0][1] = c1[0].length; s1[0][2] = sum; int count = 0; for (int i = 0; i < c1.length; i++) { for (int j = 0; j < c1[0].length; j++) { if (c1[i][j] != 0){ count++; s1[count][0] = i; s1[count][1] = j; s1[count][2] = c1[i][j]; } } } int[][] c2 = new int[c1.length][c1.length]; int temp = 1; for (int i = 0; i < c1.length; i++) { for (int j = 0; j < c1.length; j++) { if (temp > count){ break; } if (i == s1[temp][0] && j == s1[temp][1]){ c2[i][j] = s1[temp][2]; temp++; } } } for (int[] ints : c2) { for (int anInt : ints) { // 只有printf才能进行这样的赋值方式 System.out.printf("%3d",anInt); } System.out.println(); } } } 队列 概述 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 先进先出 分析 1. 创建一个数组 2. 设定两个指向，指向前和后 实现 class ArrQueue{ /* * 思路 * - 创建一个数组设定大小，设定两个变量来指向数组的前和后 * - 两个变量的初始值都是-1，这是因为当入队一个数值时，rear往前移动一个 * - 出队一个数值时，front往前移动一个起到出队的效果 * - 这里为了达到队列的循环利用使用取模的方法，并且下面的实现方式会导致队列的数组有一个位置是不能利用的 * */ private int[] arr; private int maxSize; private int front; private int rear; public ArrQueue(int maxSize){ this.maxSize = maxSize; arr = new int[maxSize]; this.front = -1; this.rear = -1; } // 判断是否为空 public boolean isEmpty(){ return this.front == this.rear; } public boolean isFull(){ return (rear + 1)%maxSize == front; } public void addQueue(int n){ if (isFull()) { System.out.println("队列已满。无法添加"); return; } else { this.rear++; if (rear == maxSize){ rear = 0; } else { rear = rear % maxSize; } arr[rear] = n; } } public int getQueue(){ if (isEmpty()) throw new RuntimeException("队列为空，无法取出"); else { this.front++; if (front == maxSize){ front = 0; } else { front = front % maxSize; } return this.arr[front]; } } public void showQueue(){ if (isEmpty()) { System.out.println("当前队列为空，没有数据"); return; } else { for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } } } 链表 概述 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 对比起线性结构插入、删除方便，查找操作复杂。链表有很多种不同的类型：单向链表，双向链表以及循环链表 分析 1. 创建一个节点类，编写属性，拥有数据域和指向下一个节点 2. 创建一个链表类，设置一些方法，如：添加、查找、删除等... 实现 class SingleLinkList{ // 初始化一个头结点，在这个单链表中头结点为空没有数据，作用为找到该链表 private HeroNode head = new HeroNode(0,"",""); public HeroNode getHead() { return head; } // 添加一个节点 public void add(HeroNode heroNode){ // 因为头结点不能改变，所以定义一个临时节点来指向每一个节点 HeroNode temp = head; while (true) { if (temp.next == null){ break; } temp = temp.next; } temp.next = heroNode; } // 反转链表 public void reverseLink(HeroNode head){ /* * 思路： * - 创建一个临时节点将头结点赋值给它，找到链表 * - 创建一个新的头结点，依次取下原链表的节点，将取下的节点挂在新节点的后面 * - 临时节点遍历每一个节点，当遍历到的时候，将新节点的next赋值给它，这样它就挂在了新头节点的后面 * - 最后遍历完以后，将新头结点的next赋值给原头结点，这样则实现了链表的反转 * */ HeroNode temp = head.next; HeroNode next = null; HeroNode n1 = new HeroNode(0,"",""); while (temp != null){ next = temp.next; temp.next = n1.next; n1.next = temp; temp = next; } head.next = n1.next; } // 通过编号添加节点 public void addByNo(HeroNode heroNode){ /* * 思路 * - 设置临时节点来遍历所有节点，遍历到每一个节点以后，判断当前遍历到的节点的下一个节点的值和添加的值 * - 大于则找到，添加到当前遍历节点的下一个 * - 现在存在的链表中有等于的值，则无法添加 * - 如果一直遍历，在链表现有的值中没有比其大的，则直接添加到最后一个 * */ HeroNode temp = head; boolean flag = false; while (true){ if (temp.next == null) break; if (temp.next.getNo() > heroNode.getNo()){ break; } else if (temp.next.getNo() == heroNode.getNo()){ flag = true; break; } temp = temp.next; } if (!flag){ heroNode.next = temp.next; temp.next = heroNode; } else { System.out.println("无法加入该编号的节点"); } } // 遍历链表 public void list(){ if (head.next != null) { HeroNode temp = head; while (true) { temp = temp.next; System.out.println(temp); if (temp.next == null) break; } } else { System.out.println("该链表为空"); return; } } } class HeroNode{ // 数据域 private int no; private String name; private String nickname; // 指向下一个节点 public HeroNode next; public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getNickname() { return nickname; } public void setNickname(String nickname) { this.nickname = nickname; } // 初始化一个节点，设置属性但初始化时其指向为空 public HeroNode(int no, String name, String nickname){ this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "datastructure.HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + '}'; } } 问题 通过编号添加节点，无法添加的问题 演示 public void addByNo(HeroNode heroNode){ HeroNode temp = head; boolean flag = false; while (true){ if (temp.next == null) break; if (temp.next.getNo() > heroNode.getNo()){ flag = true; break; } else if (temp.next.getNo() == heroNode.getNo()){ break; } temp = temp.next; } if (flag){ heroNode.next = temp.next; temp.next = heroNode; } else { System.out.println("无法加入该编号的节点"); } } 原因 通过这代码添加第一个节点时，flag永远都是false，这无法进行后面的添加操作，应当把当找到相应的节点的时候的flag改为false，并且如果编码相等时的flag为ture，后面的节点插入的代码也是flag为false则进行相应的节点插入 总结 就是一定要注意当用标志位时，一定要注意标志位的状态和在什么情况下进行处理，如果在条件筛选过程中，满足以后，标志位进行了改变，则如果要进行后续操作，一定要以筛选后标志位来进行处理。 循环链表 分析 1. 创建一个头结点 2. 添加链表的时候让新的节点指向头结点 实现 class JosefLink{ /* * 思路 * - 创建一个头结点 * - 加入新的节点的时候，让新的节点指向头结点 * - 创建一个临时变量来遍历链表，添加节点的时候添加到当前链表的后面并让新的节点指向头部 * */ private JosefNode first = null; public JosefNode getFirst() { return first; } public void addJosefNode(int nums){ JosefNode curBoy = null; for (int i = 0; i < nums; i++) { JosefNode boy = new JosefNode(i); if (i == 0){ first = boy; first.setNext(first); curBoy = first; }else { curBoy.setNext(boy); boy.setNext(first); curBoy = curBoy.getNext(); } } } public void listJosefLink(JosefNode first){ JosefNode temp = first; while (true){ System.out.println(temp.getNo()); if (temp.getNext() == first){ break; } temp = temp.getNext(); } } } class JosefNode{ private int no; private JosefNode next; public JosefNode(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public JosefNode getNext() { return next; } public void setNext(JosefNode next) { this.next = next; } } 栈 概述 栈（stack）又名堆栈，它是一种运算受限的线性表。只能在栈的栈顶进行操作，先进后出。 下面为了方便理解通过数组的方式来创建了一个栈，实现了一个计算器 分析 1. 创建一个数组 2. 设定一个指向来指向数组的最后，只能通过最后来进行操作 实现 /** * 首先要创建两个栈 * - 一个数据栈 * - 一个符号栈 * 在符号栈中要进行判断 * - 如果为空就直接放入 * - 如果栈中已经有了符号，并且要入栈的符号的优先级小于已有的符号 * - 就进行数据栈的数据出栈的操作和符号栈目前栈顶的符号出栈，进行运算，算出的结果，入数据栈 * - 再把当前扫描到的符号，入符号栈 * - 如果扫描到的符号大于目前符号栈的栈顶的符号，则直接入栈 * * 最后把剩下数据栈和符号栈中的出栈，运算，最后数据栈的栈顶得到的数据就是计算的结果 * */ public class CalaDemo { public static void main(String[] args) { Cala numStack = new Cala(10); Cala symbolStack = new Cala(10); String in = "7*3-2*4"; /* * 思路 * - 这里是将传入的字符串利用字符串的方法进行分割 * - 定义一个index分割每一个字符，入栈结束以后index++扫描下一个 * - 如果扫描到的是一个符号则进行上面说的进行判断 * - 因为判断中有出栈和压栈需要一个变量来保存结果 * */ int index = 0; int oper = ' '; int num1 = 0; int num2 = 0; int res = 0; char c = ' '; while (true){ // 扫描字符 c = in.substring(index, index + 1).charAt(0); // 扫描出的结果是符号 if (symbolStack.isOper(c)){ // 如果为空则直接加入 if (symbolStack.isEmpty()){ symbolStack.popStack(c); // 否则进行和当前符号栈中已经存在的符号进行比较 } else { // 如果当前扫描的符号小于栈顶的符号 if (symbolStack.compareOper(c)){ num1 = numStack.pushStack(); num2 = numStack.pushStack(); oper = symbolStack.pushStack(); res = numStack.resNum(num1, num2, oper); numStack.popStack(res); symbolStack.popStack(c); } else { symbolStack.popStack(c); } } } else { // 这里的c可能还是字符，要转为数字则需要进行减去48，依据Unicode编码 numStack.popStack(c- 48); } index++; if (index >= in.length()){ break; } } // 将符号栈中的剩下的所有压入数据栈中最后得到一个结果 while (true){ if (symbolStack.isEmpty()){ break; } else { num1 = numStack.pushStack(); num2 = numStack.pushStack(); oper = symbolStack.pushStack(); res = numStack.resNum(num1,num2,oper); numStack.popStack(res); } } numStack.listStack(); } } class Cala { /* * 思路 * - 通过数组来创建一个栈 * - 初始化一个变量为-1，当压入一个数据时向上移动一次，这样这个变量始终都是栈顶 * */ private int[] stack; private int top = -1; private int maxSize; public Cala(int maxSize) { this.maxSize = maxSize; stack = new int[maxSize]; } public boolean isEmpty(){ return top == -1; } public int getTop(){ return stack[top]; } public boolean isFull(){ return top == maxSize - 1; } public void popStack(int n){ if (isFull()) { System.out.println("已满，无法添加"); return; } else { top++; stack[top] = n; } } public int pushStack(){ if (isEmpty()){ throw new RuntimeException("当前栈为空，无法出栈"); }else { int value = stack[top]; top--; return value; } } public void listStack(){ if (isEmpty()){ System.out.println("目前空，无法出栈"); return; } while (top >= 0){ System.out.println(stack[top]); top--; } } public boolean isOper(char c){ return c == '+' || c == '/' || c == '*' || c == '-'; } public int priority(int c){ if (c == '*' || c == '/'){ return 1; } else if (c == '+' || c == '-') return 0; else return -1; } public boolean compareOper(char c){ if (priority(c) <= priority(getTop())){ return true; } else return false; } public int resNum(int num1, int num2, int oper){ int res = 0; switch (oper){ case '+': res = num2 + num1; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; } return res; } } 递归 概述 程序调用自身的编程技巧称为递归（ recursion）。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。一般来说，递归需要有边界条件、递归前进段和递归返回段。 递归就是自身调用自身的一个方法，本身是利用的栈，当递归完毕以后会回到当前的位置，下面用八皇后问题来演示 演示 public class Queen8 { /* * 思路 * - 通过一维数组来模拟八皇后中可能存在的解法 * - 通过总结规律arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])可以进行规则判定 * - 设定检查规则来判断下一个棋子应该放在哪里 * 注意 * - 一定要设定结束递归的判断条件，否则会出现栈溢出 * */ int max = 8; int[] arr = new int[max]; int count = 0; static int count2 = 0; public static void main(String[] args) { Queen8 queen8 = new Queen8(); queen8.check(0); System.out.println(queen8.count +" == "+ count2); } public void printArr(){ count++; for (int i : arr) { System.out.print(i + " "); } System.out.println(); } public boolean judgeArr(int n){ count2++; for (int i = 0; i < n; i++) { if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])){ return false; } } return true; } // 放下每一个棋子 public void check(int n){ /* * 思路 * - 这里当放完最后一个棋子以后，n=8是棋子已经放完结束递归 * - 这里是在for循环中进行递归，所以每一次递归进行了8次，尝试了当放下这个棋子以后，下一排及其后面的所有情况，成功则打印 * */ if (n == max){ printArr(); return; } for (int i = 0; i < max; i++) { arr[n] = i; if (judgeArr(n)){ check(n+1); } } } } 哈希表 概述 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。 下面是通过数组和链表来实现的，在Java的hashtable中是通过数组加红黑树来实现的 分析 1. 创建哈希表类 哈希表中的增加、删除等方法是通过调用链表类中的方法来实现的，因为本质上是在链表上操作 数组的作用在于定位 2. 创建链表类 3. 创建节点类 实现 class HashTable{ /* * 思路 * - 创建一个链表数组来定位每一条链表 * - 添加节点的时候，可以通过添加节点的no取模来定位到具体的某一条链表 * - 链表中的添加节点和前面实现的链表添加方法类似，这里不做过多赘述 * */ private int size; private EmpLinkList[] empLinkLists; public HashTable(int size) { this.size = size; empLinkLists = new EmpLinkList[size]; for (int i = 0; i < empLinkLists.length; i++) { empLinkLists[i] = new EmpLinkList(); } } public void addEmp(Employee emp){ int no = empNo(emp); empLinkLists[no].addEmp(emp); } public int empNo(Employee emp){ return emp.getId() % size; } public void listHashTable(){ for (int i = 0; i < empLinkLists.length; i++) { empLinkLists[i].listEmpLinkList(i); } } } class EmpLinkList{ private Employee head = null; public void addEmp(Employee emp){ if (head== null){ head = emp; return; } Employee tempEmp = head; while (true){ if (tempEmp.getNext() == null){ break; } tempEmp = tempEmp.getNext(); } tempEmp.setNext(emp); } public void listEmpLinkList(int no){ if (head == null) return; System.out.println("这是第"+no+"链表："); Employee tempEmp = head; while (true){ System.out.println(tempEmp.getId() +" "+tempEmp.getName()); if (tempEmp.getNext() == null){ break; } tempEmp = tempEmp.getNext(); } } } class Employee{ private Employee next; private int id; private String name; public Employee(int id, String name) { this.id = id; this.name = name; } public Employee getNext() { return next; } public void setNext(Employee next) { this.next = next; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } } 插入排序 概述 插入排序，一般也被称为直接插入排序。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中。 分析 1. 将每个数字与现在存在的数字进行比较 2. 比他小就继续往前走直到找到比它大的数字 3. 找到比它大的数字将这个数字放在当前找到的位置，然后循环 实现 /* * 思路 * - 将每一个数字与数组中的剩下的数字进行比较判断 * - 大于继续往前走 * - 小于放在当前移动到的位置 * - 不符合的数字会整体后移，找到位置放入后，数组中的元素没有发生改变 * */ public void insertSort(int[] arr){ for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int index = i-1; while (index >= 0 && temp < arr[index] ){ arr[index+1] = arr[index]; index--; } arr[index+1] = temp; } } 归并排序 概述 归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 经典的以空间换取时间的做法 分析 1. 将现有的数组以中间进行递归分割 2. 分割以后就行排序，存入到一个临时数组 3. 最后将这个临时数组复制给原数组 实现 /* * 思路 * - 先将数组以中间进行递归分割 * - 将分割后的数组进行排序比较 * - 将排序后的数组存入临时数组 * - 双指向比较，小的先入，当一边存入完毕后，把另一边的所有剩下的存入临时数组 * - 将临时数组复制给原数组 * */ public void mergeSort(int[] arr, int left, int right, int[] temp){ /* * 思路 * - 这里进行递归分割*/ if (left < right){ int mid = (left+right) / 2; mergeSort(arr,left,mid,temp); mergeSort(arr,mid+1,right,temp); merge(arr,left,mid,right,temp); } } /* * 思路 *- 这里要传入原数组和数组的左、中、有和一个临时数组进行分割的效果 *- 传入的数组进行两边的指针比较，分别存入临时数组 * - 谁先存入完毕，将另一边的剩下的所有的存入临时数组 * - 最后进行临时数组的复制给原数组 * */ public void merge(int[] arr, int left, int mid, int right, int[] temp){ int i = left; int j = mid + 1; int t = 0; while (i <= mid && j <= right){ if (arr[i] < arr[j]){ temp[t] = arr[i]; t++; i++; } else { temp[t] = arr[j]; t++; j++; } } while (i <= mid){ temp[t] = arr[i]; t++; i++; } while (j <= right){ temp[t] = arr[j]; t++; j++; } t = 0; int tempLeft = left; while (tempLeft <= right){ arr[tempLeft] = temp[t]; t++; tempLeft++; } } } 快速排序 概述 快速排序（Quicksort）是对冒泡排序算法的一种改进。 冒泡排序这里没有进行介绍，是最简单的排序，用两个for循环进行暴力排序。 下面的排序采用的是递归的方法 分析 1. 找到数组的中间值（这里的中间值不是排序后的中间值，原数组的中间值） 2. 设定两个指向传入数组的最左边和最右边 3. 两边分别和中值进行比较，左边如果比中值大就向前移动一个 4. 同理，右边如果比中值小，就向前移动一个 5. 当找到不满足前面两个条件的数字是，两两交换达到排序的目的 实现 /* * 思路 * - 传入的数组进行排序 * - 找到中值，设定两个指向为传入数组的最左边和最右边 * - 当左边比中值大的时候向前移动，右边比中值小的向前移动 * - 当不满足条件停止的时候，两个指向两两相互交换 * - 最后进行递归 * - 左递归 * - 有递归 * */ public void quickSort(int[] arr, int left, int right){ int l = left; int r = right; int pivot = arr[(left+right) / 2]; int temp = 0; while ( l < r){ while (arr[l] < pivot){ l++; } while (arr[r] > pivot){ r--; } if (l > r) break; temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; if (arr[r] == pivot){ r--; } if (arr[l] == pivot){ l++; } } if (l == r){ l++; r--; } if (left < r) quickSort(arr,left,r); if (right > l) quickSort(arr,l,right); } 基数排序 概述 基数排序（radix sort）属于“分配式排序”（distribution sort），基于桶排序，设定10个桶来以一定条件来装入数组的数字，然后取出。 分析 1. 设定10个桶 2. 规则为取模以后 3. 不断的进行放入桶 4. 最后将每一个桶中的数字取出赋值给原数组 实现 /* * 思路 * - 设定10个桶 * - 找出原数组最大数字 * - 分别将个、十、百等上的数字取出，放入桶中 * - 将桶中的数字取出，赋值给原数组 * - 放出的次数，取决于最大数字的最高位 * */ public void radixSort(int[] arr){ int[][] bucket = new int[10][arr.length]; // 这里还需要定义一个数组来存储每一个桶中存放了多少个数字 // 这样就可以直到在赋值给原数组时需要遍历的次数 int[] bucketCount = new int[10]; int max = arr[0]; for (int i : arr) { if (i > max){ max = i; } } // 技巧： 这里通过将数字转换为字符串的形式，取出最大数字的长度，也就是最高位 int maxLength = (max + "").length(); for (int i = 0,n = 1; i < maxLength; i++, n *= 10) { for (int j = 0; j < arr.length; j++) { int bucketElement = arr[j] / n % 10; bucket[bucketElement][bucketCount[bucketElement]] =arr[j]; bucketCount[bucketElement] ++; } int index = 0; for (int j = 0; j < bucketCount.length; j++) { if (bucketCount[j] != 0){ for (int k = 0; k < bucketCount[j]; k++) { arr[index] = bucket[j][k]; index++; } } // 每次遍历完都要将存储桶中个数的数组上的数字清零，避免后面如果再次进行桶排序的时候 // 有可能这次这个桶中并没有存入数字，如果不清零则会进行遍历赋值 bucketCount[j] = 0; } } } 选择排序 概述 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 分析 1. 找出最小的放入 2. 依次找剩下最小的放入 实现 /* * 思路 * - 将每一个数字与后面的进行比较 * - 小于交换 * */ public void selectSort(int[] arr){ int temp = 0; for (int i = 0; i < arr.length; i++) { for (int j = i+1; j < arr.length; j++) { temp = arr[i]; if (arr[j] < temp){ temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } 希尔排序 概述 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort） 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。 分析 1. 设置步长 2. 比较，前面大于后面，交换 3. 折半步长 4. 当步长小于1的时候，停止比较 5. 调用其他排序 实现 /* * 思路 * - 就行在插入排序前，先进行排序，但并不是最后的结果 * - 减少插入排序比较的时间 * */ public void shellSort(int[] arr){ int temp = 0; for (int gap = arr.length / 2; gap > 0 ; gap /= 2) { for (int i = 0; i < gap; i++) { if (arr[i] > arr[i+gap]){ temp = arr[i]; arr[i] = arr[i+gap]; arr[i+gap] = temp; } } } insertSort(arr); } public void insertSort(int[] arr){ for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int index = i-1; while (index >= 0 && temp < arr[index] ){ arr[index+1] = arr[index]; index--; } arr[index+1] = temp; } } 二分查找 概述 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 分析 1. 先找到数组的中点 2. 目标值与中点值比较 3. 二分，然后重复1、 2 实现 /* * 思路 * - 找到中点值 * - 目标值与中点值 * - 缩小寻找范围，继续找到缩小范围后的中点值 * - 比较 缩小 缩小 最后找到或返回空 * */ public class BinarySearch { public static void main(String[] args) { int[] arr = {1,3,4,5,66,77,87}; BinarySearch binarySearch = new BinarySearch(); int i = binarySearch.binarySearch(arr, 0, arr.length - 1, 77); System.out.println(i); } public int binarySearch(int[] arr, int left, int right, int findVal){ if (left > right) return -1; int mid = (left+right) / 2; if (findVal > arr[mid]){ return binarySearch(arr,mid+1,right,findVal); } else if (findVal < arr[mid]){ return binarySearch(arr,right,mid-1,findVal); } else { return mid; } } } 斐波那契查找 概述 斐波那契搜索(Fibonacci search) ， 斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。找到黄金分割点然后递归查找 分析 1. 创建一个斐波那契数列 2. 根据数列大小找到原数列的分割点 3. 目标值与其比较，缩小范围，继续找寻分割点 实现 /* * 思路 * - 先创建一个斐波那契数组 * - 1、1、2、3、5... * - 根据原数组找到在斐波拉契数列中最近的值 * - 创建一个临时数组，大小为在斐波拉契中找到的值，不够的以数组的最后一位进行补充 * - f[k] = f[k-1] + f[k-2] * - 不断与新的中点就行比较，找打了返回mid和high中较小的那一个 * - 因为临时数组的后面可能是补充的所以要返回较小的下标，为找到的数字 * */ public class FibonacciSearch { public static int MaxSize = 20; public static void main(String[] args) { FibonacciSearch fibonacciSearch = new FibonacciSearch(); int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13}; int i = fibonacciSearch.fibonacciSearch(arr, 6); System.out.println(i); } public int[] fi(){ int[] fi = new int[MaxSize]; fi[0] = 1; fi[1] = 1; for (int i = 2; i < fi.length; i++) { fi[i] = fi[i-1] + fi[i-2]; } return fi; } public int fibonacciSearch(int[] arr, int findVal){ int low = 0; int high = arr.length - 1; int k = 0; int[] fi = fi(); while (high > fi[k] - 1){ k++; } int[] temp = Arrays.copyOf(arr,fi[k]); for (int i = high+1; i < temp.length; i++) { temp[i] = arr[high]; } while (high >= low){ int mid = low + fi[k-1] - 1; if (findVal > temp[mid]){ low = mid + 1; k -= 2; } else if (findVal < temp[mid]){ high = mid - 1; k--; } else { return Math.min(mid, high); } } return -1; } } 插值查找 概述 插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。 分析 插值查找就是在二分查找的演技版，将找的中值进行了一次定位int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); 实现 public int insertSearch(int[] arr, int left, int right, int findVal){ if (left > right) return -1; // 核心代码 int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); if (findVal > arr[mid]){ return insertSearch(arr,mid+1,right,findVal); } else if (findVal < arr[mid]){ return insertSearch(arr,right,mid-1,findVal); } else { return mid; } } 数组二叉树 概述 父节点的左子节点为 2*n + 1 父节点的右子节点为 2*n + 2 第n个子节点的父节点为 （n-1) / 2 演示 class ArrBinaryTree{ private int[] arr; public ArrBinaryTree(int[] arr) { this.arr = arr; } public void perList(int index){ if (arr == null || arr.length == 0){ System.out.println("数组为空，停止遍历"); } System.out.println(arr[index]); if ((index * 2 + 1) < arr.length) perList(index * 2 + 1); if ((index * 2 + 2) < arr.length) perList(index * 2 + 2); } } 二叉树 概述 二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点 。 分析 1. 创建结点类 2. 创建一颗二叉树 3. 创建方法 实现 /* * 思路 * - 创建一个结点类 * - 采用递归的方法来遍历查找和删除 * */ class BinaryTree{ private TreeNode head; public BinaryTree(TreeNode head) { this.head = head; } public void perListBinaryTree(){ if (head == null) System.out.println("为空无法遍历"); else this.head.perList(); } public void inFixListBinaryTree(){ if (head == null) System.out.println("为空无法遍历"); else this.head.inFixList(); } public void sufFixListBinaryTree(){ if (head == null) System.out.println("为空无法遍历"); else this.head.sufFixList(); } public TreeNode perSearchBinaryTree(int no){ if (head == null) return null; else return this.head.perSearch(no); } public TreeNode inFixSearchBinaryTree(int no){ if (head == null) return null; else return this.head.inFixSearch(no); } public TreeNode sufFixSearchBinaryTree(int no){ if (head == null) return null; else return this.head.sufFixSearch(no); } public void delNodeBinaryTree(int no){ if (head != null){ if (head.getNo() == no){ head = null; }else { head.deleteNode(no); } }else { System.out.println("该树为空，无法进行删除"); } } } class TreeNode { private int no; private String name; private TreeNode left; private TreeNode right; public TreeNode(int no, String name) { this.no = no; this.name = name; } public void perList() { System.out.println(this.toString()); if (this.left != null) { this.left.perList(); } if (this.right != null) { this.right.perList(); } } public void inFixList() { if (this.left != null) { this.left.inFixList(); } System.out.println(this.toString()); if (this.right != null) { this.right.inFixList(); } } public void sufFixList() { if (this.left != null) { this.left.sufFixList(); } if (this.right != null) { this.right.sufFixList(); } System.out.println(this.toString()); } public TreeNode perSearch(int no) { if (this.no == no) return this; TreeNode res = null; if (this.left != null) { res = this.left.perSearch(no); } if (this.right != null) { res = this.right.perSearch(no); } return res; } public TreeNode inFixSearch(int no) { TreeNode res = null; if (this.left != null) { res = this.left.perSearch(no); } if (this.no == no) return this; if (this.right != null) { res = this.right.perSearch(no); } return res; } public TreeNode sufFixSearch(int no) { TreeNode res = null; if (this.left != null) { res = this.left.perSearch(no); } if (this.right != null) { res = this.right.perSearch(no); } if (this.no == no) return this; return res; } public void deleteNode(int no) { if (this.left != null && this.left.getNo() == no) { this.left = null; return; } if (this.right != null && this.right.getNo() == no) { this.right = null; return; } if (this.left != null) { this.left.deleteNode(no); } if (this.right != null) { this.right.deleteNode(no); } } } 二叉平衡树 概述 又被称为AVL树（有别于AVL算法），且具有以下性质： 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。 分析 1. 建立线索二叉树 2. 平衡左右两边树的高度 3. 左旋转和右旋转也可以双旋转 - 当符合右旋转的条件时 - 如果它的左子树的右子树高度大于它的左子树的高度 - 先对当前这个结点的左节点进行左旋转 - 在对当前结点进行右旋转的操作即可 实现 /* * 思路 * - 采用递归的方法添加结点 * - 平衡树，本身是有有序 * - 不允许有高度差如果有高度差则会进行旋转 * - 右旋转和左旋转 * - 如果左右两棵树高度差过大则会进行双旋转 * */ class AVLTreeNode{ int no; AVLTreeNode left; AVLTreeNode right; public AVLTreeNode(int no) { this.no = no; } public int leftHigh(){ if (this.left == null){ return 0; } else { return this.left.high(); } } public int rightHigh(){ if (this.right == null){ return 0; } else { return this.right.high(); } } public int high(){ return Math.max(this.left == null? 0 : this.left.high(),this.right == null? 0 : this.right.high()) + 1; } public void addNode(AVLTreeNode node){ if (this.no > node.no){ if (this.left == null){ this.left = node; } else { this.left.addNode(node); } } else { if (this.right == null){ this.right = node; } else { this.right.addNode(node); } } } public void infixList(){ System.out.printf("%4d",this.no); if (this.left != null) this.left.infixList(); if (this.right != null) this.right.infixList(); } // 右旋转 public void avlTree(){ if ((this.rightHigh() - this.leftHigh() ) > 1){ AVLTreeNode temp = new AVLTreeNode(this.no); temp.left = this.left; temp.right = this.right.left; this.no = this.right.no; this.right = this.right.right; this.left = temp; } } @Override public String toString() { return "AVLTreeNode{" + "no=" + no + '}'; } } 赫夫曼树 概述 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 分析 1. 创建有序的结点数组 2. 取出数组中最小的两个值 3. 创建一个父结点，指向这两个节点 4. 移除两个小的结点 5. 将父节点加入结点 6. 排序 7. 最后就数组中只剩下一个父节点 实现 /* * 思路 *- 创建二叉树节点类 * - 数据域和左右两个指向域 * - 继承接口 -- Comparable 来重写其中的排序规则 * - 创建一个二叉树类 * - 二叉树本身是将有序的数组转换得到 * - 设置一个新的list来存储每一个节点 * - 将数组的值用创建出的新的节点来保存 * - 取出最小的两个为左右两个叶子节点，新建一个父节点来创建一颗简单的二叉树 * - 从list中移除取出的两个左右节点并加入新的父节点 * - 排序 * - 重复上面的操作，直到list中只存在一个节点停止 * - 编写主方法，测试 * - 编写一个前序遍历的方法，输出结果验证 * */ class HuffmanTree{ public HuffmanTreeNode huffmanTree(int[] arr){ List list = new ArrayList<>(); HuffmanTreeNode leftNode = null; HuffmanTreeNode rightNode = null; for (int i : arr) { list.add(new HuffmanTreeNode(i)); } while (list.size() > 1){ Collections.sort(list); leftNode = list.get(0); rightNode = list.get(1); HuffmanTreeNode parent = new HuffmanTreeNode(leftNode.value + rightNode.value); parent.left = leftNode; parent.right = rightNode; list.remove(leftNode); list.remove(rightNode); list.add(parent); } return list.get(0); } } class HuffmanTreeNode implements Comparable{ int value; HuffmanTreeNode left; HuffmanTreeNode right; public HuffmanTreeNode(int value) { this.value = value; } public void infixList(){ System.out.printf("%3d",this.value); if (this.left != null){ this.left.infixList(); } if (this.right != null){ this.right.infixList(); } } @Override public int compareTo(HuffmanTreeNode o) { return this.value - o.value; } @Override public String toString() { return "HuffmanTreeNode{" + "value=" + value + '}'; } } 赫夫曼编码 /* * 思路 * - 压缩 * - 先创建一个赫夫曼二叉树 * - 将传入的字符统计出每一个出现的次数 * - 节点中数据域由data和weight属性，其中data代表字符，weight代表出现的次数 * - 设置每一个叶子结点的赫夫曼编码 * - 左边为"0" 右边为"1" * - 生成整个字符完整的赫夫曼编码 * - 遍历传入的字符，一一对应拼接到一个字符串上 * - 将生成的完整赫夫曼编码进行压缩 * - 以8字节为一组，进行补码成十进制 * - 解压 * - 得到数组和对应的赫夫曼编码表，将获得的压缩后的数组进行转化成二进制 * - 得到的数组，进行反编码获得初始的赫夫曼完整编码 * - 在数组最后的一个数字前进行补码截取后8位 * - 数组的最后一个数字直接拼接到字符串上 * - 根据传过来的赫夫曼编码表，新建一个解码表 * - 传过来的赫夫曼编码表的key为新表的value，value为新表的key * - 根据新建的解码表解码得到的完整赫夫曼编码 * - 从第一个字符开始扫描，截取完整编码 * - 把截取到的字符串与新建的解码表对应，如果有则从下一个继续扫描 * - 如果没有则增长扫描的字符串，直到有对应的为止 * - 输出得到的数组 * */ class HuffManTreeCode { static Map huffmanMap = new HashMap(); static StringBuilder stringBuilder = new StringBuilder(); public void decodeFile(String filePath,String outPath) throws Exception{ FileInputStream is = new FileInputStream(filePath); FileOutputStream os = new FileOutputStream(outPath); byte[] b = new byte[is.available()]; is.read(b); byte[] bytes = huffmanZip(b); ObjectOutputStream oos = new ObjectOutputStream(os); oos.writeObject(bytes); oos.writeObject(huffmanMap); is.close(); os.close(); oos.close(); } public void unZipFile(String filePath,String outPath) throws Exception{ FileInputStream is = new FileInputStream(filePath); ObjectInputStream ois = new ObjectInputStream(is); byte[] bytes =(byte[]) ois.readObject(); Map huffmanCodes = (Map) ois.readObject(); byte[] decode = decode(huffmanCodes, bytes); FileOutputStream os = new FileOutputStream(outPath); os.write(decode); is.close(); ois.close(); os.close(); } public byte[] huffmanZip(byte[] bytes){ List nodes = getNode(bytes); HuffManCodeNode node = huffmanTree(nodes); getCodes(node); StringBuilder stringBuilder = new StringBuilder(); for (byte b : bytes) { stringBuilder.append(huffmanMap.get(b)); } byte[] huffmanZip = zip(stringBuilder); return huffmanZip; } public String byteToBitString(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; } } public byte[] decode(Map huffmanMap,byte[] huffmanBytes){ StringBuilder stringBuilder = new StringBuilder(); for(int i = 0; i < huffmanBytes.length; i++) { byte b = huffmanBytes[i]; boolean flag = (i == huffmanBytes.length - 1); stringBuilder.append(byteToBitString(!flag, b)); } Map byteHashMap = new HashMap<>(); for (Map.Entry entry: huffmanMap.entrySet()){ byteHashMap.put(entry.getValue(),entry.getKey()); } List list = new ArrayList<>(); for (int i = 0; i < stringBuilder.length(); ) { int count = 1; boolean flag = true; Byte b =null; while (flag){ String s1 =stringBuilder.substring(i, i + count); b = byteHashMap.get(s1); 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; } public void getCodes(HuffManCodeNode node) { this.getCodes(node, "", stringBuilder); System.out.println("生成的赫夫曼编码表为："); for (Map.Entry entry : huffmanMap.entrySet()) { int c = entry.getKey(); char s = (char) c; System.out.println(" 字符为：" + s + " " + "编码为：" + entry.getValue()); } System.out.println("<=================>"); } public StringBuilder huffmanCode(String content) { byte[] bytes = content.getBytes(); List nodes = getNode(bytes); HuffManCodeNode node = huffmanTree(nodes); getCodes(node); StringBuilder stringBuilder = new StringBuilder(); for (byte b : bytes) { stringBuilder.append(huffmanMap.get(b)); } return stringBuilder; } public byte[] zip(String content){ StringBuilder stringBuilder = huffmanCode(content); return this.zip(stringBuilder); } public byte[] zip(StringBuilder huffmancode){ int len = (huffmancode.length()+7) / 8; byte[] by = new byte[len]; int index = 0; for (int i = 0; i < huffmancode.length(); i+=8) { String s; if (i+8 > huffmancode.length()){ s = huffmancode.substring(i,huffmancode.length()); } else { s = huffmancode.substring(i, i + 8); } by[index] =(byte) Integer.parseInt(s,2); index++; } return by; } /* * 生成对应赫夫曼编码 * */ public void getCodes(HuffManCodeNode node, String code, StringBuilder stringBuilder) { StringBuilder stringBuilder1 = new StringBuilder(stringBuilder); stringBuilder1.append(code); if (node != null) { if (node.data == null) { getCodes(node.left, "0", stringBuilder1); getCodes(node.right, "1", stringBuilder1); } else { huffmanMap.put(node.data, stringBuilder1.toString()); } } } /* * 统计每一个符号出现的次数 * */ public List getNode(byte[] bytes ) { ArrayList codeNodes = new ArrayList<>(); HashMap counts = new HashMap<>(); for (byte b : bytes) { counts.merge(b, 1, Integer::sum); } /*Integer count = counts.get(b); *if (count == null){ counts.put(b,1); } else { counts.put(b,count+1); }*/ for (Map.Entry entry : counts.entrySet()) { codeNodes.add(new HuffManCodeNode(entry.getKey(), entry.getValue())); } return codeNodes; } /* * 生成一个赫夫曼树 * */ public HuffManCodeNode huffmanTree(List nodes) { Collections.sort(nodes); while (nodes.size() > 1) { HuffManCodeNode leftNode = nodes.get(0); HuffManCodeNode rightNode = nodes.get(1); HuffManCodeNode parent = new HuffManCodeNode(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parent); Collections.sort(nodes); } return nodes.get(0); } } 堆排序 概述 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构 并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 分析 1. 每一个结点和其子节点比较，大的为父节点 2. 调整传入数组的前半部分，排序 实现 public class HeapSort { public static void main(String[] args) { int[] arr ={2,232,1,21,44,0}; heapSort(arr); System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr){ int temp = 0; for (int i = arr.length/2 - 1; i >= 0; i--) { adjustHeap(arr,i,arr.length); } } public static void adjustHeap(int[] arr, int i, int length){ int temp = arr[i]; // j = i*2 + 1 i的左结点 // arr[j] < arr[j+1] 左结点和有结点比较 // 大的值和父结点交换 for (int j = i*2 + 1; j < length; j = j *2 + 1) { if (j+1 < length && arr[j] < arr[j+1]){ j++; } if (temp < arr[j]){ arr[i] = arr[j]; i = j; } else { break; } } // 如果左右结点没有比父节点大还是原值 arr[i] = temp; } } 图 概述 图（Graph）结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行（自动机）等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。 分析 下面实现以二维数组的方式实现图 深度优先搜索 1. 输出当前结点 2. 找到当前的相邻结点 3. 通过相邻结点找到下一个节点，直到没有连接为止，回溯到初始位置，重复 广度优先搜索 1. 输出当前节点 2. 找到相邻结点输出 3. 继续寻找当前节点相邻结点输出，为空 4. 找寻相邻结点的相邻结点输出 实现 /* * 思路 * - 找到当前节点的相邻结点 * */ public int getNext(int j ){ for (int i = 0; i < arrayList.size(); i++) { if (edge[j][i] > 0) return i; } return -1; } /* * 思路 * - 根据找到的相邻结点 * */ public int getNextByIndex(int v1, int v2){ for (int i = v2 + 1; i < arrayList.size(); i++) { if (edge[v1][i] > 0 ){ return i; } } return -1; } /* * 思路 深度优先搜索 * - 输出当前节点 * - 设置当前节点已经被访问过，不在被访问 * - 找到下一个连接节点 * - 如果没有输出过，则输出，并遍历，找寻下一个连接结点 * - 如果已经输出过，则寻找当前结点的下一个连接结点，判断 * - 重复递归判断 * */ private void graphListDFS(boolean[] dfs, int i){ System.out.println(getVertexByIndex(i)); dfs[i] = true; int w = getNext(i); while (w != -1){ if (!dfs[w]){ graphListDFS(dfs,w); } w = getNextByIndex(i,w); } } public void graphListDFS(){ for (int i = 0; i < arrayList.size(); i++) { if (!isVisited[i]) graphListDFS(isVisited,i); } } /* * 思路 广度优先搜索 * - 输出当前结点 * - 设置当前结点被访问过 * - 将当前输出过的节点添加到队列中 * - 找寻当前结点的相邻结点并输出 * - 移除队列中的最后 * - 找寻下一个当前结点连接的节点 * - 没有输出过则输出，并设置为被访问过 * - 输出过则寻找下一个当前结点的连接的节点 * - 将当前节点加入队列 * - 寻找下一个当前结点连接节点，如果没有则退出循环 * - 如果队列不为空，则继续将队列的最后一个移除并取出 * - 循环，直到队列为空，则说明当前传入的节点的所有能够到达的节点全部输出 * */ public void graphListBFS(boolean[] isVisited,int i){ int u; int w; System.out.println(getVertexByIndex(i)); LinkedList list = new LinkedList<>(); isVisited[i] = true; list.addFirst(i); while (!list.isEmpty()){ u = list.removeFirst(); w = getNext(u); while (w != -1){ if (!isVisited[w]){ System.out.println(getVertexByIndex(w)); isVisited[w] = true; list.addLast(w); } w = getNextByIndex(u,w); } } } public void graphListBFS(){ for (int i = 0; i < arrayList.size(); i++) { if (!isVisited[i]){ graphListBFS(isVisited,i); } } } 二分查找（非递归） 通过while循环来改变左右端点和中间端点的值，不断二分，然后不断比较 实现 public class BinarySearch { public static void main(String[] args) { int[] arr = {1,5,7,23,111,123,422}; int index = binarySort(arr, 1); System.out.println("index:" + index); } /* * 思路 * - 传入原数组和目标值 * - 找到中点，进行比较 * - 大于，右边二分 * - 小于左边二分 * - 不断二分直到截取到的数组只有一个数字 * - 是则返回当前下标 * - 不是则返回-1，代表该数组没有目标值，无法找到 * */ public static int binarySort(int[] arr, int target){ int left = 0; int right = arr.length-1; while (left <= right){ int mid = (left + right) / 2; if (arr[mid] == target){ return mid; } else if (target > arr[mid]){ left = mid + 1; } else { right = mid - 1; } } return -1; } } 分治算法 概述 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。 下面以汉诺塔的情况进行演示 分析 1. n个盘可以分为第n个盘和剩下的n-1个盘，整体来看成两个盘 2. 先将n-1个盘从a借助c移动到b 3. 在将第n个盘从a移动到c 4. 最后将b上的n-1个盘从b借助a移动到c 实现 public class Hanoi { // 统计需要移动的次数 static int count; public static void main(String[] args) { char a = 'a'; char b = 'b'; char c = 'c'; move(5,a,b,c); System.out.println(count); } public static void move(int num, char a, char b, char c){ count++; // 当只有一个盘的时候，直接从a移动到c if (num == 1){ System.out.println("第一个盘从："+a+"移动到"+c); } else { // 将n-1个盘从a借助c移动到b move(num -1, a, c, b); // 将最后一个盘从a直接移动到c System.out.println("将"+num+"从"+a+"移动到"+c); // 最后将b上的n-1个盘从b借助a移动到c move(num - 1, b, a, c); } } } 动态规划算法 概述 动态规划是求解决策过程最优化的过程。20世纪50年代初，在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。 将目前要得到的结果借助前面已经得到的结果作为一个参考，在前面得到的基础上进行规划，每一个问题不是相对独立的，是互相联系的。 下面以背包问题来演示，这里的一件物品只能放一次，也就是01问题，不限次数也是类似的方法和思想。 分析 1. 将物品依次加入，一开始只有一个物品，然后放入背包中 2. 不断加入，当加入新的物品的时候，判断如果加入这个物品后的价值是否能够比其上一种情况下的（也就是比其现在少一个物品的情况下）是否能够得到更优的解，相互比较，取最优的解 实现 /* * - 设定了每一个物品的价值和重量 * - 背包中每一个物品只能放一件 * */ public class KnapsackProblem { public static void main(String[] args) { int[] val = {1500, 3000, 2000}; int[] wight = {1, 4, 3}; int pack = 4; int[][] path = new int[val.length+1][pack+1]; // 创建数组来存储背包中放入物品以后的价值 int[][] v = new int[val.length+1][pack+1]; // 从第二行和第二列开始遍历，因此第一行和第一列的值都为0，则对于加入第一个物品可以放入背包时 // 可以参考前面没有物品可以放所得到的解 for (int i = 1; i < v.length; i++) { for (int j = 1; j < v[0].length; j++) { // 当前加入的物品一定要小于或等于背包当前的重量，这样才能够放入 if (j >= wight[i-1]){ // 在加入新的物品以后，尝试把它放入背包，并且把空余的位置放能够放下的物品 // 与和没有加入这个物品时，在这个重量下背包能够得到的最优解进行比较，如果大于，则将这个值 // 放放入v二维数组中 if (v[i-1][j] < val[i-1]+v[i-1][j-wight[i-1]]){ v[i][j] =val[i-1]+v[i-1][j-wight[i-1]]; // 创建这个数组来保存这个重量下得到最优解放入了哪些物品 // 这里是一定放入i-1这个物品的，剩下的重量则是用其他物品进行填充的 // 这个j可以参考v[i-1][j-wight[i-1]]放入的物品，这样就可以得到当时背包中放入的物品 path[i][j] = 1; } else { // 如果加入物品的解不能比不加入这个物品的解更优，则用上一个同样重量背包但是物品更少得解来赋值 v[i][j] =v[i-1][j]; } } else { // 如果放入的物品的重量大于背包的容量，则也是直接用上一个同样重量下得到的解 v[i][j] = v[i-1][j]; } } } // 输出 for (int[] ints : v) { for (int anInt : ints) { System.out.printf("%6d",anInt); } System.out.println(); } /* * 这里也可以输出patch数组，如果数组中的值为1，则进行输出，说明这个背包是组合的， * 遍历出的一维数组上的变量则为放入的物品，二维数组上的变量则可以参考前面遍历出的一维数组相同的变量 * 可以理解一下上面赋值所写的注释 * */ } } 贪心算法 概述 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 下面以电台的例子来演示，注意贪心算法的得到的解不一定是所有解中最优的解，贪心算法只是能帮助我们快速得到一个相对优的解，而且策略也很重要。 分析 1. 首先找到覆盖最多地区的电台 2. 将这个电台加入最后的选择中，然后移除所有地区中并集的部分 3. 将剩下的电台与剩下的所有的地区的集合找并集，选出并集最多的电台 4. 最后当所有地区的集合为空是，电台选择完毕 实现 public class Greedy { public static void main(String[] args) { HashMap> broadCasts = new HashMap<>(); // 创建5个电台，并添加所覆盖的地区 HashSet k1 = new HashSet<>(); HashSet k2 = new HashSet<>(); HashSet k3 = new HashSet<>(); HashSet k4 = new HashSet<>(); HashSet k5 = new HashSet<>(); k5.add("北京"); k5.add("上海"); k5.add("天津"); k2.add("广州"); k2.add("北京"); k2.add("深圳"); k3.add("成都"); k3.add("上海"); k3.add("杭州"); k4.add("上海"); k4.add("天津"); k1.add("杭州"); k1.add("大连"); broadCasts.put("k1",k1); broadCasts.put("k2",k2); broadCasts.put("k3",k3); broadCasts.put("k4",k4); broadCasts.put("k5",k5); // 创建一个集合来保存所有地区 HashSet allAreas = new HashSet<>(); allAreas.add("北京"); allAreas.add("上海"); allAreas.add("深圳"); allAreas.add("杭州"); allAreas.add("成都"); allAreas.add("大连"); allAreas.add("广州"); allAreas.add("天津"); // 创建一个临时变量来保存电台和所有地区集合的并集 HashSet tempArea = new HashSet<>(); // 创建一个集合来保存最后的电台选择 ArrayList list = new ArrayList<>(); // 下面是找到第一个覆盖最多地区的电台，并将它加入到最后的选择中 String maxKey = "k1"; for (String key : broadCasts.keySet()){ if (broadCasts.get(maxKey).size() < broadCasts.get(key).size()){ maxKey = key; } } // 如果所有地区的集合不为空，则一直进行加入电台的操作，直到没有地区没有被覆盖 while (allAreas.size() != 0){ for (String key : broadCasts.keySet()){ tempArea.clear(); HashSet area = broadCasts.get(key); tempArea.addAll(area); // 遍历所有电台，一次和地区集合求交集，最大的加入 tempArea.retainAll(allAreas); if (tempArea.size() > 0 && (maxKey == null || tempArea.size() > broadCasts.get(maxKey).size())) { maxKey = key; } } if (maxKey != null) { list.add(maxKey); allAreas.removeAll(broadCasts.get(maxKey)); } maxKey = null; } System.out.println(list); } } 迪杰斯特拉算法 概述 迪杰斯特拉算法(Dijkstra)是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 分析 1. 先找到当前结点（A）没有访问过的且距离最近的结点（B） 2. 根据找到的结点，找寻最开始的结点通过这个结点到达其他结点（C）的距离 - 如果比初始结点直接到达距离段，则更新距离表，并设置达到结点（C）的前驱结点为（B） - 如果没有则不进行改变 3. 遍历所有结点 - 1的次数 实现 /* * 思路 * - 传入路径权值图和开始的点 * - 创建三个数组 * - 当前这个节点是否已经访问过 * - 到达这个结点的前驱结点是什么 * - 从开始节点到达这个结点所需要的距离为 * - 将dis进行初始的赋值 * - 找到开始结点能够达到的最近节点 * - 使用广度优先查找，找出这个新找到的结点能够到达最近的结点 * - 循环直到达到所有能够到达的节点（通过其他节点中转也能达到的节点） * */ public static int[] djs(int[][] matrix, int start){ int[] isVisited = new int[matrix.length]; int[] preVertex = new int[matrix.length]; isVisited[start] = 1; Arrays.fill(preVertex, start); for (int i = 1; i < matrix.length; i++) { int min = 65535; int next = 0; for (int j = 0; j < matrix.length; j++) { if (isVisited[j] != 1 && matrix[start][j] < min){ min = matrix[start][j]; next = j; } } isVisited[next] = 1; for (int j = 0; j < matrix.length; j++) { if (j == next || matrix[next][j] > 65534 || isVisited[j] == 1){ continue; } if (matrix[start][j] > matrix[start][next] + matrix[next][j]){ matrix[start][j] = matrix[start][next] + matrix[next][j]; preVertex[j] = next; // j = 1 next = 0 } } } System.out.println(Arrays.toString(preVertex)); return matrix[start]; } Floyd算法 Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似 分析 1. 初始设置所有结点的前驱结点为当前结点 2. 判断从A结点到其他结点时，如果经中间结点是否会减少距离 - 有则更新距离表和前驱结点表 - 没有则不更新 3. 三嵌套循环，遍历每一种情况 实现 public static int[][] Floyd(int[][] matrix){ char[][] pre = new char[matrix.length][matrix.length]; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { if (i == 0){ pre[i][j] = 'A'; } if (i == 1){ pre[i][j] = 'B'; } if (i == 2){ pre[i][j] = 'C'; } if (i == 3){ pre[i][j] = 'D'; } if (i == 4){ pre[i][j] = 'E'; } if (i == 5){ pre[i][j] = 'F'; } if (i == 6){ pre[i][j] = 'G'; } } } for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { int len = 0; for (int k = 0; k < matrix.length; k++) { len = matrix[j][i] + matrix[i][k]; if (matrix[j][k] > len){ matrix[j][k] = len; pre[j][k] = pre[i][k]; } } } } return matrix; } 骑士周游 概述 规定棋盘的大小，每次骑士只能按照日字前后左右移动，最后移动的结果为将棋盘所有棋格都遍历过，则成功，否则失败。 实现 /* * 思路 * - 设置当前位置已经访问过 * - 找出当前位置下一步能够行走的所有情况，存储在一个list中 * - 将list中的第一种情况取出，判断能走的下一步能否行走 * - 如果可以则递归 * - 不能则在while循环中取出list中的下一种情况，直到list为空跳出循环 * - 递归结束条件，如果棋盘中的每一个棋格都走过，则说明成功 * - 否则继续递归判断 * * */ public static void traversalChessboard(int[][] chessBoard, int row, int column, int step){ chessBoard[row][column] = step; isVisited[row * X + column] = true; ArrayList ps = nextArr(new Point(column, row)); /* * 优化 * - 将所有能够到达的情况进行，排序 * - 排序的规则是： * - 能够在棋盘上行走距离最少的在前面 * */ ps.sort(((o1, o2) -> { return nextArr(o1).size() - nextArr(o2).size(); })); while (!ps.isEmpty()){ Point point = ps.remove(0); if (!isVisited[point.y * X + point.x]){ traversalChessboard(chessBoard,point.y,point.x,++step); } } if (step < X * Y && !finished){ chessBoard[row][column] = 0; isVisited[row * X + column] = false; } else { finished = true; } } public static ArrayList nextArr(Point curPoint){ ArrayList ps = new ArrayList(); //创建一个 Point p1 = new Point(); //表示马儿可以走 5 这个位置 if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) { ps.add(new Point(p1)); } //判断马儿可以走 6 这个位置 if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) { ps.add(new Point(p1)); } //判断马儿可以走 7 这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } //判断马儿可以走 0 这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } //判断马儿可以走 1 这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } //判断马儿可以走 2 这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } //判断马儿可以走 3 这个位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } //判断马儿可以走 4 这个位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } KPM算法 概述 KMP算法是一种改进的字符串匹配算法，KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。 分析 1. 目标字符串中进行建立一个索引表 2. 将目标字符串和比对字符串进行比对 - 当比对不成功时，根据建立的索引表移动 实现 * 思路 * - 根据目标字符串的前缀后缀比对建立索引表 * - 字符搜索时，比对失败后，根据索引表移动 * */ public int searchString(String str1, String str2, int[] next){ for (int i = 0,j = 0; i < str2.length(); i++) { while (j > 0 && str2.charAt(i) != str1.charAt(j)){ j = next[j-1]; } if (str2.charAt(i) == str1.charAt(j)) j++; if (j == str1.length()) return i - j + 1; } return -1; } public int[] getNext(String target){ int[] next = new int[target.length()]; for (int i = 1,j = 0; i < target.length(); i++) { while (j> 0 && target.charAt(i) != target.charAt(j)){ j = next[j -1]; } if (target.charAt(i) == target.charAt(j)) j++; next[i] = j; } return next; } 普里姆算法 概述 普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。 分析 1. 遍历每一种情况 2. 以当前点出发，设置当前点已被访问过 3. 遍历已访问过的点到没有访问过的距离，找到最小的输出并设置这个点以被访问 实现 public void prim(graph graph,int v){ int[] isVisited = new int[graph.verxs]; isVisited[v] = 1; int h1 = -1; int h2 = -1; int minWight = 10000; for (int i = 1; i < graph.verxs; i++) { for (int j = 0; j < graph.verxs; j++) { for (int k = 0; k < graph.verxs; k++) { if (isVisited[j] == 1 && isVisited[k] == 0 && graph.wight[j][k] < minWight){ minWight = graph.wight[j][k]; h1 = j; h2 = k; } } } System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWight); isVisited[h2] = 1; minWight = 10000; } }