数据结构与算法

程序 = 数据结构 + 算法

数据结构：树、链表、图等

线性结构

数组、队列、链表和栈

非线性结构

二维数组，多维数组，广义表，树结构，图结构

稀疏数组

稀疏数组的好处时压缩数组

在这里插入图片描述

二维数组 转 稀疏数组的思路

遍历原始的二维数组，得到有效数据的个数 sum

根据sum 就可以创建稀疏数组 sparseArr int[sum + 1] [3]

将二维数组的有效数据数据存入到稀疏数组

稀疏数组转原始的二维数组的思路

先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11] [11]

在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.

public class SparseArray {public static void main(String[] args) {int[][] chessArr = new int[11][11];chessArr[1][2] = 1;//1表示是黑子chessArr[2][3] = 2;//2表示是白子chessArr[4][5] = 1;//遍历原始的二维数组，得到有效数据的个数 sumint sum = 0;for (int[] row : chessArr) {for (int date : row) {if (date != 0) sum++; //算出多少个棋子System.out.printf("%d\t", date);}System.out.println();}System.out.printf("棋盘上的棋子个数%d个", sum);System.out.println("----------------------");//根据sum 就可以创建稀疏数组 sparseArr int[sum + 1] [3]//sparseArr数组第一列为存储原始数组的 行 列 棋子个数 列数规定所有指定用3int[][] sparseArr = new int[sum + 1][3];int count = 0; //定义一个整数赋值给sparseArr数组sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if (chessArr[i][j] != 0) {count++;sparseArr[count][0] = i; //i表示棋盘中的行sparseArr[count][1] = j; //j表示棋盘中的列sparseArr[count][2] = chessArr[i][j];}}}for (int[] row : sparseArr) {for (int date : row) {System.out.printf("%d\t", date);}System.out.println();}System.out.println("----------------");System.out.println("将稀疏数组转化为二维数组");//先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11] [11]int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];for (int i = 0; i < sparseArr[0][2]; i++) {chessArr2[sparseArr[i + 1][0]][sparseArr[i + 1][1]] = sparseArr[i + 1][2];}for (int[] row : chessArr2) {for (int date : row) {System.out.printf("%d\t", date);}System.out.println();}//将稀疏函数每行数据存入文件IO再取出变成二维数组 作业}}

IO流

队列

队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

环形队列

问题分析并优化

目前数组使用一次就不能用， 没有达到复用的效果将这个数组使用算法，改进成一个环形的队列取模：%（这里当rear小于maxsize取余时就是本身，这是环形队列设计的关键）

说明

这里的rear和front不同与上面的队列形式，初始值都为0.

而且这里设计是空出一个位，所有公式(rear+1)%maxsize =front 中假如数组长度为7,即maxSize=7

判断为满的话就是当rear在数组的最后一位arr[6]时 (6+1)%7=0即为环形数组满值

(rear+maxsize-front)%maxsize 同理求出这个环形队列的有效个数为

总结：

不管是普通队列还是环形队列，里面的添加数据都是rear尾标识在变，取出则是front头标识在变。环形队列不同与普通队列的是，它可以做到复用前面的数据位，通过rear=(rear+1) % maxsize 的方式可以在超出队列maxsize的时候回到队列首位置 ，%取余计算就是环形队列的实现关键

链表（封装类LinkedList）

单链表介绍

1.头结点：

（1）数据结构中，在单链表的开始结点之前设立一个节点称之为头结点，头结点的数据域可以不存储任何信息，也可以存储链表的长度等附加信息，头结点的指针域存储指向第一个结点的指针（即第一个结点的存储位置）。

（2）作用：方便链表的操作，减少代码量，举个例子，要知道在链表中插入，删除一个元素是更改这个结点上一个结点的指针域的位置来实现的，那么怎么样来对第一个结点来进行这些操作，有，但是麻烦，不如引入一个头结点来的方便。总之，引入头结点就可以很少的考虑到一些特殊情况，减少代码量。

头指针

注意注意注意

（1）头指针是指链表中 ，指向第一个结点的指针。

这一点很重要

（2）头指针具有标识作用，所以常常会用头指针冠以链表的名字。所以你定义一个链表，那么链表的名字一般就是这个链表的头指。

链表是有序的列表，但是它在内存中的存储如下（实际在内存中的存储）

逻辑结构示意图如下

总结

链表是以结点的方式来存储的，链式存储每个节点包含data域，next域：指向下一个节点如图：发现在内存中链表的各个节点不一定是有序存储的链表分带头节点和不带头结点的链表，根据实际需求来确定

单链表的应用：

第一步：在添加英雄时，直接添加到链表的尾部

public class singleLikedListDemo {public static void main(String[] args) {heroHead heroHead1 = new heroHead(1, "陈泽培", "大帅哥");heroHead heroHead2 = new heroHead(1, "陈椒盐", "大美女");singleLikedList likedList = new singleLikedList();likedList.addHero(heroHead1);likedList.addHero(heroHead2);likedList.show();}}class singleLikedList {private heroHead head = new heroHead(0, "", ""); // 当作头节点 不赋值不移动public void addHero(heroHead heroHead) {heroHead temp = head;while (true) {if (temp.next == null) {break;}temp = temp.next;}temp.next = heroHead;}public void show() {if (head.next == null) {// 当头节点head.next为null时证明链表为空System.out.println("头指针为空,链表不存在");return;}heroHead temp = head;while (true) {if (temp.next == null) {break;}temp = temp.next;System.out.println(temp);}}}class heroHead {public int no;public String name;public String nickName;public heroHead next; // 指向下个链表节点英雄对象public heroHead() {}// 创建heroHead的构造函数public heroHead(int hero_no, String hero_name, String hero_nickName) {this.no = hero_no;this.name = hero_name;this.nickName = hero_nickName;}@Overridepublic String toString() {return "heroHead{" +"no=" + no +", name='" + name + '\'' +", nickName='" + nickName + '\'' +'}';}}

第二步：根据排名插入到指定位置

如果有这个排名，则添加失败，并给出提示

public void addHeroOrder(HeroHead heroHead) {boolean flag = false; // 声明一个变量，默认传入对象编号不存在HeroHead temp_hero = head; // 定义临时变量，为头节点的下一个链表目标while (true) {if (temp_hero.next == null) {// 判断链表为空,则直接插入到尾部break;}if (temp_hero.next.no == heroHead.no) {flag = true;break;} else if (temp_hero.next.no > heroHead.no) {break;}temp_hero = temp_hero.next;}if (flag){System.out.println("编号已经存在");return;}else {heroHead.next=temp_hero.next;temp_hero.next=heroHead;}}

第三步：修改节点

public void updateHero(HeroHead heroHead){boolean hero_exists = false; //创建变量标记，是否存在HeroHead temp_hero = head.next; //创建指向头节点的临时指针if (temp_hero==null) {//头节点下一个为空，则链表不存在(只有头节点)System.out.println("链表为空");return;}while (true){if (temp_hero==null) {//下一个对象为空，则当前对象为链表末尾break;} else if (temp_hero.no==heroHead.no) {hero_exists = true; //号码存在可以进行修改break;}else {//否则继续遍历temp_hero=temp_hero.next;}}if (hero_exists){temp_hero.name= heroHead.name;temp_hero.nickName= heroHead.nickName;}else {System.out.println("英雄编号不存在");}}

第四步：删除节点

public void delete(int heroNum) {boolean hero_exists = false;HeroHead temp_hero = head;if (temp_hero.next == null) {System.out.println("链表为空");return;}while (true) {if (temp_hero.next == null) {break;} else if (temp_hero.next.no == heroNum) {/*单向链表 用头指针指向的下一个节点的num去判断,就可以直接将当前指针指向下下个节点如果用当前节点的num去匹配的话，很难找到上一个节点的头指针位置*/hero_exists = true;break;} else {temp_hero = temp_hero.next;}}if (hero_exists) {temp_hero.next = (temp_hero.next).next;// 指向下下个对象} else {System.out.println("对象不存在");}}

面试题

// 统计链表存在的有效节点数(注意的是不把头节点计算进去)public int sumNode() {int node = 0;HeroHead temp_sum_node = head.next;if (head.next == null) {return 0; // 链表只有头节点 有效节点为0}while (true) {if (temp_sum_node != null) {node++;temp_sum_node = temp_sum_node.next;} else {break; // 到达尾部}}return node;}

// 查找单链表中倒数第K个节点public void findRearNode(int k) {if (k<=0) {System.out.println("请输入正确数字");return;}int count = 0;// 计数// 计算出有效节点HeroHead temp_sum_node = head.next;HeroHead find_rear_node = head.next;if (head.next == null) {return; // 链表只有头节点 有效节点为0}while (true) {if (temp_sum_node != null) {count++;temp_sum_node = temp_sum_node.next;} else {break; // 到达尾部}}count = count - k + 1;// 通过计算倒数k个是顺数多少个，用一个变量记录while (true) {count--;if (count == 0) {System.out.println(find_rear_node);break;}find_rear_node = find_rear_node.next;}}

//链表反转public void reverseLink(HeroNode hero){if (hero.next==null || (hero.next).next==null) {System.out.println("链表达不到反转要求");return;}HeroNode reverse_link = new HeroNode(0,"",""); //定义一个反转节点进行节点摘取的存放HeroNode cur = heroNode.next; //heroNode原始链表HeroNode next = null;while(cur!=null){//当前对象为空则到达链表尾部//1.存放当前节点的.next对象防止移动后丢失next = cur.next;//2.将cur.next指向reverse_link.next 就可以达到移动的目的 // 首次为null，后续变成上一个curcur.next = reverse_link.next;//3.再将reverse.next指向当前摘取下来的节点reverse_link.next=cur;//4.最后移动指针，将当前的cur.next对象变成curcur = next;}//5.将原来的头节点再指向reverse_link的头指针节点heroNode.next=reverse_link.next;}//遍历就可以理解2、3的思路

打印逆序列表

上面的题的要求就是逆序打印单链表.

方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议

2.方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.

举例演示栈的使用 Stack

栈的基本认识

import java.util.Stack;public class StackDemo {//队列是先进先出 栈是先进后出public static void main(String[] args) {Stack<String> stack = new Stack<>();stack.push("tom");stack.push("jem");stack.push("dog");while (stack.size()>0) {System.out.println(stack.pop());}}}

//链表的逆序打印public void reversePrint(HeroNode hero){if (hero.next==null||(hero.next).next==null) {System.out.println("链表达不到逆序打印要求");return;}Stack<HeroNode> stack_node = new Stack<>();HeroNode current_node = hero.next;//将链表中的节点存入栈中while(current_node!=null){stack_node.push(current_node);current_node=current_node.next;//current移动到下一个节点}//利用栈的先进后出的特点将栈中对象输出while (stack_node.size()>0) {System.out.println(stack_node.pop());}}

合并两个有序的单链表，合并之后链表仍然有序

首先，定义一个ListNode类来表示每个链表节点，包含一个val值和next指向下一个节点的指针。然后，定义一个Solution类来表示解决问题的方法mergeTwoLists，接收两个参数l1和l2分别表示要合并的两个有序单链表头节点，声明一个指向一个虚拟头节点head的cur指针。在while循环中，重复以下操作：如果l1的val小于l2的val，则将cur的next指向l1，并将l1移动到其下一个节点；否则将cur的next指向l2，并将l2移动到其下一个节点。然后将cur移动到它的下一个节点。最后，如果l1不为空，则cur的next指向l1；如果l2不为空，则cur的next指向l2。返回head.next即为合并后的有序单链表头节点。

public NodeOrder order(NodeOrder val1, NodeOrder val2) {if (val1 == null) return val2;if (val2 == null) return val1;while (val1 != null && val2 != null) {if (val1.num > val2.num) {current_node.next = val2;val2 = val2.next;} else if (val1.num < val2.num) {current_node.next = val1;val1 = val1.next;}current_node=current_node.next; /移动当前指针对象}if (val1 == null) current_node.next = val2;if (val2 == null) current_node.next = val1;return node;}

双向链表

管理单向链表的缺点分析:

1.单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

2.单向链表不能自我删除(找到删除的previous节点使用node.next=(node.next).next)，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会)。

3.分析了双向链表如何完成遍历，添加，修改和删除的思路

public void addHero(Node hero) {Node temp_node = head.next;while (true) {if (temp_node == null) {temp_node.next = hero;hero.previous=temp_node;break;}temp_node = temp_node.next;}}public void delete(int heroNum) {boolean hero_exists = false;Node temp_hero = head;if (head.next == null) {System.out.println("链表为空");return;}while (true) {if (temp_hero == null) {break;} else if (temp_hero.no == heroNum) {/*单向链表 用头指针指向的下一个节点的num去判断,就可以直接将当前指针指向下下个节点如果用当前节点的num去匹配的话，很难找到上一个节点的头指针位置*/hero_exists = true;break;} else {temp_hero = temp_hero.next;}}if (hero_exists) {temp_hero.previous.next=temp_hero.next;temp_hero.next.previous=temp_hero.previous;} else {System.out.println("对象不存在");}}public void updateHero(Node Node){boolean hero_exists = false; //创建变量标记，是否存在Node temp_hero = head.next; //创建指向头节点的临时指针if (temp_hero==null) {//头节点下一个为空，则链表不存在(只有头节点)System.out.println("链表为空");return;}while (true){if (temp_hero==null) {//下一个对象为空，则当前对象为链表末尾break;} else if (temp_hero.no== Node.no) {hero_exists = true; //号码存在可以进行修改break;}else {//否则继续遍历temp_hero=temp_hero.next;}}if (hero_exists){temp_hero.name= Node.name;temp_hero.nickName= Node.nickName;}else {System.out.println("英雄编号不存在");}}public void showNode() {Node temp_node = head;if (temp_node.next== null) {//链表判断是否为空System.out.println("链表为空");return;}while (true) {if (temp_node.next == null) {break;}temp_node = temp_node.next;System.out.println(temp_node);}}

双链表按序号添加

public void addHeroNum(Node hero) {Node temp_node = head.next;if (head.next == null) {System.out.println("空链表");return;}while (true) {if (temp_node == null) {break;} else if (temp_node.no == hero.no) {System.out.println("编号已存在");break;} else if (temp_node.no > hero.no) {temp_node.previous.next = hero;hero.next = temp_node;temp_node.previous = hero;break;}temp_node = temp_node.next;}}

单向环形链表

Josephu(约瑟夫、约瑟夫环) 问题

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束

class CircleLinkedList {Boy first = new Boy(-1);// 定义一个指针指向首个节点 用来保存地址public void addBoy(int num) {if (num < 1) {System.out.println("请输入正确人数");return;}Boy current_boy = new Boy(0);for (int i = 0; i < num + 1; i++) {Boy boy = new Boy(i);if (i == 1) {first = boy;boy.next = first; //自环current_boy = first;} else {current_boy.next = boy;boy.next = first; // first是规定第一个节点 这一步让每一个都指向first节点成环current_boy = boy;}}}/*** @param startNum 表示从第几个小孩开始数数* @param countNum 表示数几下* @param nums表示最初有多少小孩在圈中*/public void outBoy(int startNum, int countNum, int nums) {if (startNum < 1 || countNum < 1 || startNum > nums) {System.out.println("参数错误");return;}// 找到链表的最后一个节点和首节点做到出圈Boy rear_boy = first;while (true) {if (rear_boy.next == first) {//通过addBoy()中first=boy(1)首节点break;}rear_boy = rear_boy.next;//通过while循环判断下一个节点为首节点后拿到} //首节点的后一个节点// 将rear_boy和first_boy移动startNum - 1位for (int i = 0; i < startNum - 1; i++) {//第几位开始：因为自身开始数数所以是startNum-1first = first.next;rear_boy = rear_boy.next;}//开始计数将小屁孩出圈while (rear_boy != first) {for (int i = 0; i < countNum - 1; i++) {//同理上面first = first.next;rear_boy = rear_boy.next;}System.out.println(first.num); //first成为被提出的小孩 rear_boy则是要跟着首位rear_boy.next = first.next;first = first.next;}}

栈（封装类Stack）

栈的介绍

栈的英文为(stack)

栈是一个先入后出(FILO-First In Last Out)的有序列表。

栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的 一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元 素最先删除，最先放入的元素最后删除

图解方式说明出栈(pop)和入栈(push)的概念

栈的应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。

二叉树的遍历。

图形的深度优先(depth 一 first)搜索法。

利用数组模拟栈

public class ArrayStackDemo {public static void main(String[] args) {ArrayStack stack = new ArrayStack(7);stack.pop(13);stack.pop(14);stack.pop(-2);stack.pop(1314520);System.out.println(stack.push());stack.list();}}class ArrayStack {public int top; //栈顶public int[] stack; //array数组模拟栈public int maxsize; //maxSize栈最大容量//构造方法public ArrayStack(int maxsize) {this.maxsize = maxsize;stack = new int[maxsize];top = -1; //栈顶默认为-1位置}//判断栈满public boolean isFull() {return top == maxsize - 1;}//判断栈空public boolean isEmpty() {return top == -1;}//入栈public void pop(int pro) {//先判断栈满if (isFull()) {System.out.println("栈满，无法继续加入");return;}//栈没有满的话先 top++ 然后将stackP[top] = pro;top++;stack[top] = pro;}//出栈public int push() {//判断栈空if (isEmpty()) {throw new RuntimeException("栈空无法出栈数据");}//将出栈数组返回，然后将top--栈顶下降int pro = stack[top];stack[top] = 0;top--;return pro;}//遍历栈元素public void list() {//判断栈空if (isEmpty()) {throw new RuntimeException("栈空无法出栈数据");}for (int i = maxsize - 1; i >= 0; i--) {System.out.printf("开始遍历出stack[%d]的是%d", i, stack[i]);System.out.println("--------");}}}

利用链表模拟栈

public class LinkedListStackDemo {}class LinkedListStack {public int top = -1;//栈顶stackNode stackNode = new stackNode(0);public int maxSize; //控制链表最大容量模拟栈stackNode current_node = stackNode; //设置当前节点stackNode current_node_list = stackNode; //设置当前节点供list方法使用public LinkedListStack(int maxSize) {this.maxSize = maxSize;}//判断栈满public boolean isFull() {return top == maxSize - 1;}//判断栈空public boolean isEmpty() {return top == -1;}//入栈public void pop(stackNode node) {//先判断栈满if (isFull()) {throw new RuntimeException("栈满，无法继续加入");}current_node.next = node;current_node = current_node.next;top++;}//出栈,不像链表栈只能出最后一个（先进后出，后进先出的原则）public stackNode push() {//判断栈空if (isEmpty()) {throw new RuntimeException("栈空，无法出栈数据");}for (int i = 0; i <= top; i++) {//这里top是比节点node少一位的，所有for循环时要<=topstackNode = stackNode.next; //这里不能用current_node遍历，因为当前current_node已经在赋值的时候指到最后一个节点位置了}top--;return stackNode;}//遍历栈元素public void list() {//判断栈空if (isEmpty()) {throw new RuntimeException("栈空,无法出栈数据");}while (true) {if (current_node_list.next == null) {break;}current_node_list = current_node_list.next;System.out.println(current_node_list);}}}

calculator 练习（加括号判断）

public class Calculator {public static void main(String[] args) {String expression = "100+200-6+3*2";ArrayStack2 numStack = new ArrayStack2(10);ArrayStack2 opeStack = new ArrayStack2(10);int index = 0;int num1 = 0;int num2 = 0;int opr = 0;int result = 0;char ch = ' ';String tmp = "";while (true) {ch = expression.substring(index, index + 1).charAt(0);if (opeStack.isOperation(ch)) {if (!opeStack.isEmpty()) {if (opeStack.isPriority(ch) <= opeStack.isPriority(opeStack.peek())) {num1 = numStack.pop();num2 = numStack.pop();opr = opeStack.pop();result = numStack.isCalculate(num2, num1, opr);numStack.push(result);opeStack.push(ch);} else {opeStack.push(ch);}} else {opeStack.push(ch);}} else {tmp += ch;//判断不是运算符后，应该再继续判断字符中下一个是否也为数字，先进行拼接再入栈（可能会出现指针越界）if (index == expression.length() - 1) {numStack.push(Integer.parseInt(tmp));} else {if (opeStack.isOperation(expression.substring(index + 1, index + 2).charAt(0))) {//判断是下一个是否还是数字，数字则先不入栈继续拼接，直到当前的下一个为运算符时将tmp入栈numStack.push(Integer.parseInt(tmp));tmp = "";}}}index++;if (index == expression.length()) {break;}}while (true) {if (opeStack.isEmpty()) {break;}num1 = numStack.pop();num2 = numStack.pop();opr = opeStack.pop();result = numStack.isCalculate(num2, num1, opr);numStack.push(result);}System.out.println("表达式为：" + expression + "结果为：" + numStack.pop());}}class ArrayStack2 {public int top; // 栈顶public int[] stack; // array数组模拟栈public int maxsize; // maxSize栈最大容量// 构造方法public ArrayStack2() {}public ArrayStack2(int maxsize) {this.maxsize = maxsize;stack = new int[maxsize];top = -1; // 栈顶默认为-1位置}public int peek() {return stack[top];}// 判断栈满public boolean isFull() {return top == maxsize - 1;}// 判断栈空public boolean isEmpty() {return top == -1;}// 入栈public void push(int pro) {// 先判断栈满if (isFull()) {System.out.println("栈满，无法继续加入");return;}// 栈没有满的话先 top++ 然后将stackP[top] = pro;top++;stack[top] = pro;}// 出栈public int pop() {// 判断栈空if (isEmpty()) {throw new RuntimeException("栈空无法出栈数据");}// 将出栈数组返回，然后将top--栈顶下降int pro = stack[top];stack[top] = 0;top--;return pro;}// 遍历栈元素public void list() {// 判断栈空if (isEmpty()) {throw new RuntimeException("栈空无法出栈数据");}for (int i = maxsize - 1; i >= 0; i--) {System.out.printf("开始遍历出stack[%d]的是%d", i, stack[i]);System.out.println("--------");}}// 运算优先级方法public int isPriority(int ope) {if (ope == '*' || ope == '/') {return 1;} else if (ope == '+' || ope == '-') {return 0;} elsereturn -1;}// 判断是否为运算符方法public boolean isOperation(char ope) {return ope == '*' || ope == '/' || ope == '+' || ope == '-';}// 运算方法public int isCalculate(int num1, int num2, int ope) {int result = 0;switch (ope) {case '+':result = num1 + num2;break;case '-':result = num1 - num2;break;case '/':result = num1 / num2;break;case '*':result = num1 * num2;break;default:break;}return result;}}

栈的三种表达式

前缀表达式

中缀表达式

后缀表达式 逆波兰表达式

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后

举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

逆波兰表达式的计算器模拟

import java.util.ArrayList;import java.util.List;import java.util.Stack;public class BoLangNotation {public static void main(String[] args) {//创建一个数字计算的字符串，变成后缀表达式//中缀表达式：2+3-6*8/2 后缀表达式：6 8 * 2 / 2 3 + -String expression = "6 8 * 2 / 2 3 + -"; //用空格分开，等下直接split分割取出System.out.println(calculate(aString(expression)));}public static List<String> aString(String expression) {String[] split_result = expression.split(" ");List<String> list = new ArrayList<>();for (String s : split_result) {list.add(s);}return list;}public static int calculate(List<String> list) {Stack<String> stack = new Stack<>();//将list遍历，过滤数字和运算符号for (String item : list) {if (item.matches("\\d+")) {//正则表达式匹配数字的作用stack.push(item);} else {//不是数字，则取出栈顶前二进行运算int num1 = Integer.parseInt(stack.pop());int num2 = Integer.parseInt(stack.pop());int result = 0;//判断运算符switch (item) {case "*":result = num2 * num1;break;case "/":result = num2 / num1;break;case "-":result = num2 - num1;break;case "+":result = num2 + num1;break;default:throw new RuntimeException("运算符错误");}stack.push("" + result);}}return Integer.parseInt(stack.pop());}}

中缀表达式转换为后缀表达式

思路理解

1)大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。

2)初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；

从左至右扫描中缀表达式；

3)遇到操作数时，将其压 s2；

4)遇到运算符时，比较其与 s1 栈顶运算符的优先级：

1.如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

2.否则，若优先级比栈顶运算符的高，也将运算符压入 s1；

3.否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4.1)与 s1 中新的栈顶运算符相比较；

5)遇到括号时：

如果是左括号“(”，则直接压入 s1

如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃

6)重复步骤 2 至 5，直到表达式的最右边

7)将 s1 中剩余的运算符依次弹出并压入 s2

8)依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

中缀转后缀表达式

import java.util.ArrayList;import java.util.List;import java.util.Stack;public class ChangeExpression {public static void main(String[] args) {String infix = "1+((2+3)*4)-5";System.out.println(changeExpression(infix));System.out.println(parseSuffixExpression(changeExpression(infix)));System.out.println(calculator(parseSuffixExpression(changeExpression(infix))));}public static List<String> changeExpression(String infix) {List<String> suffix = new ArrayList<>();String tmp = "";// 用于拼接连续的数字char ch; // 接收当前字符串取出的字符int index = 0; // 字符串索引do {// 判断是否为数字还是运算符if ((ch = infix.charAt(index)) < 47 || (ch = infix.charAt(index)) > 58) {// 判断ch是否存在47和大于58suffix.add("" + ch);index++;} else {while (index < infix.length() && (ch = infix.charAt(index)) >= 47 && (ch = infix.charAt(index)) <= 58) {// ch大小存在[47,58]区间则是数字而且不是最后一位 判断连续数字出现情况tmp += ch;index++;}suffix.add(tmp);tmp = "";}} while (index < infix.length());return suffix;}public static List<String> parseSuffixExpression(List<String> list) {// 创建一个栈和一个集合，因为创建两个栈时，一个栈没有弹栈的操作所有可以用集合替代Stack<String> stack = new Stack<>();List<String> suffix_list = new ArrayList<>();// 先用正则表达式\\d+判断取出数字直接存入集合中for (String item : list) {if (item.matches("\\d+")) {suffix_list.add(item); // 数字直接存入栈中} else {if (item.equals("(")) {stack.push(item); // 左括号直接入栈} else if (item.equals(")")) {// 如果是右括号while (!stack.peek().equals("(")) {// 将栈运算符存入集合中suffix_list.add(stack.pop());}stack.pop(); // 再将栈顶(出栈} else {if (!stack.empty() && Operation.getValue(stack.peek()) > Operation.getValue(item)) {suffix_list.add(stack.pop());}stack.push(item);}}}while (!stack.empty()) {suffix_list.add(stack.pop());}return suffix_list;}public static int calculator(List<String> list) {Stack<String> stack = new Stack<>();int result = 0;for (String item : list) {if (Operation.isOperation(item.charAt(0))) {int num1 = Integer.parseInt(stack.pop());int num2 = Integer.parseInt(stack.pop());result = Operation.isCalculate(num2, num1, item.charAt(0));stack.push(result + "");} else {stack.push(item);}}return result;}}class Operation {private static int add = 1;private static int sub = 1;private static int mul = 2;private static int div = 2;public static int getValue(String operation) {int result = 0;switch (operation) {case "+":result = add;break;case "-":result = sub;break;case "*":result = mul;break;case "/":result = div;break;default:// System.out.println("不存在该运算符");break;}return result;}public static int isCalculate(int num1, int num2, int ope) {int result = 0;switch (ope) {case '+':result = num1 + num2;break;case '-':result = num1 - num2;break;case '/':result = num1 / num2;break;case '*':result = num1 * num2;break;default:break;}return result;}public static boolean isOperation(char ope) {return ope == '*' || ope == '/' || ope == '+' || ope == '-';}public static boolean isOperation(String ope) {return ope == "*" || ope == "/" || ope == "+" || ope == "-";}}

递归

应用场景

概念

简单的说:递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁

调用机制

递归能解决什么样的问题

1.各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大赛)

2.各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.

3.将用栈解决的问题–>递归代码比较简洁

递归需要遵守的规则

1.执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

2.方法的局部变量是独立的，不会相互影响, 比如 n 变量

3.如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.

4.递归必须向退出递归的条件逼近，否则就是无限递归,出现 StackOverflowError

5.当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或 者返回时，该方法也就执行完毕

迷宫问题

public class Recursion {public static void main(String[] args) {//创建地图int[][] map = new int[8][7];//创建边墙for (int i = 0; i < 8; i++) {//列map[i][0] = 1;map[i][6] = 1;}for (int i = 0; i < 7; i++) {//行map[0][i] = 1;map[7][i] = 1;}map[3][1] = 1;map[3][2] = 1;// map[2][2] = 1;// map[1][2] = 1;for (int[] ints : map) {for (int i : ints) {System.out.print(i + " ");}System.out.println();}System.out.println("-----------------");setWay(map, 1, 1);for (int[] ints : map) {for (int i : ints) {System.out.print(i + " ");}System.out.println();}}/*** 如果小球可以到达map[6][5]，则说明通路找到* 约定：当map[i][j]为0表示该点没有走过，1的时候为墙；2的时候表示一个通路；3表示该点探测过了，但是不通* 走迷宫时候的策略：下 右 上 左，如果该点走不通在回溯* @param map 地图* @param i 起始x位置* @param j 起始y位置* @return*/public static boolean setWay(int[][] map, int i, int j) {if (map[6][5] == 2) {return true;}if (map[i][j] != 0) {//重点判断map[i][j]==2时，因为这是需要递归一次走通的不考虑自己标记某个带你为2return false;} else {map[i][j] = 2;//先假设map[i][j]=2时if (setWay(map, i + 1, j)) {//向下走if判断setWay()方法为ture，则直接return truereturn true;} else if (setWay(map, i, j + 1)) {return true;} else if (setWay(map, i - 1, j)) {return true;} else if (setWay(map, i, j - 1)) {return true;} else {map[i][j] = 3;return false;}}}}

对迷宫问题的讨论

小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化测试回溯现象思考: 如何求出最短路径? 思路代码实现.

八皇后

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、 同一列或同一斜线上，问有多少种摆法**(92)**。

解题思路

1.第一个皇后先放第一行第一列

2.第二个皇后放在第二行第一列，然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都 放完，找到一个合适

3.继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确 解

4.当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解， 全部得到.

5.然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤

6.示意图:

public class Queen {int max = 8;//设计一位数组模拟二维数组,因为可以把数组的下标当作行数,数组表示列数int[] arr = new int[max];static int count = 0;public static void main(String[] args) {Queen Queen = new Queen();Queen.check(0);System.out.println(count);}//递归逆溯public void check(int n) {//表示放置第几个皇后if (n == max) {//判断当n++递加到arr数组的最大size，则到达棋版最后一行print();return;}for (int i = 0; i < arr.length; i++) {//无论从第n行开始，先放第i=0列arr[n] = i;if (judge(n)) {check(n + 1); //因为每一行都有自己的for循环,当最初的行结束这次递归，则继续for循环做到回溯}//冲突直接同行下个列坐标}}//查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放完的皇后冲突//判断当前坐标和之前的坐标是否是同列同一横线(同行不考虑因为n在后面是递增的)public boolean judge(int n) {//目前n表示第n+1个皇后for (int i = 0; i < n; i++) {//i<n则是检查n个皇后前面的皇后是否与现在的皇后冲突//第一个条件：判断是否在同一列//第二个条件：判断是否在同一斜线，如果在同一斜线当前行-行的绝对值 = 当前列- 列的绝对值//因为n是递增的所以一定不同一行if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) {return false;}}return true;}//打印数组方法public void print() {count++;for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}}

排序算法

介绍

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程

排序的分类：

1.内部排序:

指将需要处理的所有数据都加载到**内部存储器(内存)**中进行排序。

2.外部排序法：

数据量过大，无法全部加载到内存中，需要借助**外部存储(文件等)**进行排序。

3.排序算法的分类：

算法的时间复杂度

度量一个程序(算法)执行时间的两种方法

事后统计的方法

这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所 得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。

事前估算的方法

通过分析某个算法的时间复杂度来判断哪个算法更优.

时间频度

基本介绍

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。[举例说明]

—举例说明-忽略常数项

结论:

2n+20 和 2n 随着 n 变大，执行曲线无限接近, 20 可以忽略3n+10 和 3n 随着 n 变大，执行曲线无限接近, 10 可以忽略

举例说明-忽略低次项

结论:

2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近, 可以忽略 3n+10n^2+5n+20 和 n^2 随着 n 变大,执行曲线无限接近, 可以忽略 5n+20

时间复杂度

1.一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。 记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。

2.T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同，但时间复杂 度相同，都为 O(n²)。

3.计算时间复杂度的方法：

用常数 1 代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1

修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²

去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

常见的时间复杂度

常数阶 O(1)

对数阶 O(log2n)

线性阶 O(n)

线性对数阶 O(nlog2n)

平方阶 O(n^2)

立方阶 O(n^3)

k 次方阶 O(n^k)

指数阶 O(2^n)

上述代码整体执行消耗的时间为:T(n)=2n3+2n2+2n+1

可是当一个结构太过复杂的话，把每一层循环次数都算出来会很麻烦，所以只需要找出算法中基本语句(执行次数最多/对运算时间影响最大的)

上面T(n)/f(n)极限值为不等于零的常数，则称f(n)是T(n)是同数量级函数/同阶(即为T(n)中最高阶的位n^3),所以这个表达式可以写成:n无穷大时, T(n)/n3=2n3/n^3=2(高数中的知识无穷大时抓大头，最高次幂的其余值可忽略不计)

int i=1;

while(i<=n){

i=i*2;

这道题的时间复杂度T(n):

第1次循环：1*2=2

第2次循环：2*2=2^2

第3次循环：22*2=23

第x次循环：2x-1*2=2x

所以n=2^x, x取无穷大时为 n=2^x —>x=log2^n

空间复杂度

//数组前后替换简单实现public class test1 {public static void main(String[] args) {int[] array = new int[0];for (int i = 0; i < array.length; i++) {if (i <= array.length / 2) {int temp = array[i];array[i] = array[array.length - i - 1];array[array.length - 1] = temp;}}

这里的空间复杂度看temp变量，这里的temp可视为在原地工作长度不需要被限制，所以空间复杂度为S(n)=O(1)

//两个数组一个数组为空，并且把另一个不为空的数组倒序装入int[] array1 = new int[n];int[] array2 = new int[n];for (int i = 0; i < array1.length; i++) {array2[array1.length - i - 1] = array1[i];}}

这里空间复杂度需要看空数组，空数组长度为array1.length为n，所以空间复杂度为S(n)=O(n)

算法的空间复杂度

基本介绍

1.类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是 问题规模 n 的函数。

2.空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的 临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，例 如快速排序和归并排序算法, 基数排序就属于这种情况

3.在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品 (redis, memcache)和算法(基数排序)本质就是用空间换时间.

冒泡排序

基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒

优化：

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在 排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排 序写好后，在进行)

import java.text.SimpleDateFormat;import java.util.Date;public class BubbleSort {public static void main(String[] args) {//测试冒泡排序的速度int[] arrs = new int[800000];for (int i = 0; i < 800000; i++) {arrs[i] = (int) (Math.random() * 800000);//[0-800000)的随机数}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String dateStr1 = simpleDateFormat.format(date1);System.out.println("排序前的时间是：" + dateStr1);bubbleSort(arrs);Date date2 = new Date();String dateSte2 = simpleDateFormat.format(date2);System.out.println("排序后的时间：" + dateSte2);// print(arrs);}public static void bubbleSort(int[] arr) {boolean judge = false;for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {//前一位大于后一位arr[j] = arr[j] + arr[j + 1];arr[j + 1] = arr[j] - arr[j + 1];arr[j] = arr[j] - arr[j + 1];judge = true;}}if (!judge) {break;} else {judge = false;}}}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

选择排序

基本介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的

基本思想

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值， 与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2] 交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值， 与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

import java.util.Random;public class SelectSort {public static void main(String[] args) {int[] arr = {2, 31, 32, -4, 21, 1230, -21, 0, 1};print(selectSort(arr));}public static int[] selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int minIndex = i; //假设最小数索引int min = arr[i]; //假设最小为首位for (int j = i + 1; j < arr.length; j++) {//假设首位最小比较首位以外的数if (arr[minIndex] > arr[j]) {//select更小minIndex = j;min = arr[j];}}if (minIndex != i) {arr[minIndex] = arr[i];arr[i] = min;}}return arr;}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

插入排序

插入排序的介绍

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序的思想

插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

public class InsertSort {public static void main(String[] args) {int[] arr = {34, 101, 32, 1};int insertVal = 0;int insertIndex = 0;for (int i = 1; i < arr.length; i++) {insertVal = arr[i];insertIndex = i - 1;//这里insertIndex >= 0下标防止越界,arr[insertIndex] > insertVal则是数值比当前数值大的后移//模拟i=2时数组里面数值的变化过程, 34，101,101,1-->34,34,101,1——>32,34,101,1while (insertIndex >= 0 && arr[insertIndex] > insertVal) {arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}if (insertIndex + 1 != i) {arr[insertIndex + 1] = insertVal; //因为在上面while判断最后还会自减一次，所有这里要+1}}print(arr);}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

希尔排序

介绍

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

示意图

public class ShellSort {public static void main(String[] args) {int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};// shellSort(arr);shellSortPlus(arr);print(shellSortPlus(arr));}//交换法public static void shellSort(int[] arr) {for (int gap = arr.length / 2; gap > 0; gap /= 2) {for (int i = gap; i < arr.length; i++) {for (int j = i - gap; j >= 0; j -= gap) {if (arr[j] > arr[j + gap]) {arr[j + gap] = arr[j] + arr[j + gap];arr[j] = arr[j + gap] - arr[j];arr[j + gap] = arr[j + gap] - arr[j];}}}print(arr);System.out.println();}}//移动法public static int[] shellSortPlus(int[] arr) {int j;int tmp;for (int gap = arr.length / 2; gap > 0; gap /= 2) {for (int i = gap; i < arr.length; i++) {j = i;tmp = arr[i];if (arr[j] < arr[j - gap]) {//像插入排序，条件为true的话 隔gap进行比较进行移动while (j - gap >= 0 && tmp < arr[j - gap]) {arr[j] = arr[j - gap];j -= gap;}arr[j] = tmp; //j-=gap 和上面的arr[j] = arr[j - gap];形成数值替换}}}return arr;}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

快速排序

介绍

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

**快速排序（java实现）这里用的另外一个博主的快排

栈溢出就是缓冲区溢出的一种。由于缓冲区溢出而使得有用的存储单元被改写,往往会引发不可预料的后果。程序在运行过程中，为了临时存取数据的需要，一般都要分配一些内存空间，通常称这些空间为缓冲区。如果向缓冲区中写入超过其本身长度的数据，以致于缓冲区无法容纳，就会造成缓冲区以外的存储单元被改写，这种现象就称为缓冲区溢出。缓冲区长度一般与用户自己定义的缓冲变量的类型有关。

public class QuickSort {public static void main(String[] args) {} /*** @param arr 传入的数组* @param low 左边最小数，也是一开始的基准数 * @param high 最右边*/public static void quickSort(int[] arr,int low,int high) {int i, j, temp, t;if (low >= high) {//这里用到了>=,在判断low=high时就结束此方法和阻止下一次递归return; //减少栈的占用空间尽可能防止栈溢出(所以这里加上=号判断更好)}i = low;j = high;//temp就是基准位temp = arr[low];while (i < j) {//先看右边，依次往左递减 找到比基准位小的数while (temp <= arr[j] && i < j) {j--;}//再看左边，依次往右递增 找到比基准位大的数while (temp >= arr[i] && i < j) {i++;}//如果满足条件则交换if (i < j) {t = arr[j];arr[j] = arr[i];arr[i] = t;}}//最后将基准为与i和j相等位置的数字交换 arr[low] = arr[i];arr[i] = temp;//当i = j 的时候//递归调用左半数组quickSort(arr, low, j - 1);//递归调用右半数组quickSort(arr, j + 1, high);}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}

归并排序

介绍

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

说明:

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。

归并排序思想示意图2-合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

public class MergeSort {public static void main(String[] args) {// int[] arr = new int[30];// for (int i = 0; i < arr.length; i++) {// arr[i] = (int) (Math.random() * 100);// }int[] arr= {8,4,5,7,1,3,6,2};int[] tmp = new int[arr.length];mergeSort(arr, 0, arr.length - 1, tmp);print(arr);}//拆分+合并public static void mergeSort(int[] arr, int left, int right, int[] tmp) {if (left < right) {int mid = (left + right) / 2;//左边递归拆分mergeSort(arr, left, mid, tmp);//递归方法入栈，后进先执行，由l:0 r:1 -> l:2 r:3 -> l:0 r:3//右边递归拆分mergeSort(arr, mid + 1, right, tmp);//45 67 47//合并数组merge(arr, left, right, mid, tmp);}}/*** @param arr 原始数组* @param left 左边序列的初始索引* @param mid 中间索引* @param right 右边索引* @param tmp 做中转的数组*///合并 传入left和right以及辅助的mid，通过大小排序到tmp数组中，最后又通过left和right赋值到原先数组public static void merge(int[] arr, int left, int right, int mid, int[] tmp) {int l = left;int r = mid + 1;int index = 0;while (l <= mid && right >= r) {//判断分成两部分的首位哪个小，小的存入tmp[]数值中if (arr[l] < arr[r]) {tmp[index] = arr[l];index++;l++;} else {tmp[index] = arr[r];index++;r++;}}//当只有一部分的到达了数组限制，另一部分可能存在剩余while (l <= mid) {tmp[index] = arr[l];index++;l++;}while (right >= r) {tmp[index] = arr[r];index++;r++;}//临时数组拷贝到原来数组index = 0; //索引置零System.out.println("left为：" + left + "\tright为：" + right);while (left <= right) {//排序成功的tmp[]数组，通过传入的left和right确定对应原先数组的位置进行替换arr[left] = tmp[index];index++;left++;}}public static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

基数排序

基数排序(桶排序)介绍:

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾 名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的**：将整数按位数切割成不同的数字，然后按每个位数分别比较

基数排序的思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class RadixSort {public static void main(String[] args) {int[] arrs = {53, 3, 542, 748, 14, 214};//需要一个二维数组和一个一位数组//一维数组的目的是标记1-10位数桶下面的元素数量int[] bucketElementCount = new int[10];//二维数组来记录各位数下的存放位置，bucketElement[拆分下来1-10的位数桶][通过索引存放具体的元素位置]int[][] bucketElement = new int[10][bucketElementCount.length];// //第1轮取出需要遍历数组的个元素个位// for (int i = 0; i < arrs.length; i++) {// int digitOfElement = arrs[i] / 1 % 10; //获取到个位// //通过取出的个位，存入对应的二维数组中// //bucketElementCount[digitOfElement]他就是用来标记数量的，第一次取得digitOfElement的初始值为0,所以每次需要+1计数// bucketElement[digitOfElement][bucketElementCount[digitOfElement]] = arrs[i];// bucketElementCount[digitOfElement] += 1; //相同个位不会出现覆盖=将索引后移// }// int index = 0;// //存入二维数组桶中后，再依次取出// for (int i = 0; i < bucketElementCount.length; i++) {// //判断通过个位存储的各位置,排除空桶// if (bucketElementCount[i] != 0) {//for (int j = 0; j < bucketElementCount[i]; j++) {//这里使用了bucketElement来计数进行赋值//arrs[index] = bucketElement[i][j];//index++;//}//bucketElementCount[i] = 0;//如果使用完这个一位数组的i位，就需要将其置零，不然会出先数值下标越界// }// }// System.out.println(Arrays.toString(arrs));//// //第2轮取出需要遍历数组的个元素个位// for (int i = 0; i < arrs.length; i++) {// int digitOfElement = arrs[i] / 10 % 10; //获取到个位// //通过取出的个位，存入对应的二维数组中// //bucketElementCount[digitOfElement]他就是用来标记数量的，第一次取得digitOfElement的初始值为0,所以每次需要+1计数// bucketElement[digitOfElement][bucketElementCount[digitOfElement]] = arrs[i];// bucketElementCount[digitOfElement] += 1; //相同个位不会出现覆盖=将索引后移// }// index = 0; //重新置零，第2轮重新使用// //存入二维数组桶中后，再依次取出// for (int i = 0; i < bucketElementCount.length; i++) {// //判断通过个位存储的各位置,排除空桶// if (bucketElementCount[i] != 0) {//for (int j = 0; j < bucketElementCount[i]; j++) {//这里使用了bucketElement来计数进行赋值//arrs[index] = bucketElement[i][j];//index++;//}//bucketElementCount[i] = 0;// }// }// System.out.println(Arrays.toString(arrs));//// //第3轮取出需要遍历数组的个元素个位// for (int i = 0; i < arrs.length; i++) {// int digitOfElement = arrs[i] / 100 % 10; //获取到个位// //通过取出的个位，存入对应的二维数组中// //bucketElementCount[digitOfElement]他就是用来标记数量的，第一次取得digitOfElement的初始值为0,所以每次需要+1计数// bucketElement[digitOfElement][bucketElementCount[digitOfElement]] = arrs[i];// bucketElementCount[digitOfElement] += 1; //相同个位不会出现覆盖=将索引后移// }// index = 0; //重新置零，第3轮重新使用// //存入二维数组桶中后，再依次取出// for (int i = 0; i < bucketElementCount.length; i++) {// //判断通过个位存储的各位置,排除空桶// if (bucketElementCount[i] != 0) {//for (int j = 0; j < bucketElementCount[i]; j++) {//这里使用了bucketElement来计数进行赋值//arrs[index] = bucketElement[i][j];//index++;//}//bucketElementCount[i] = 0;// }// }// System.out.println(Arrays.toString(arrs));//找到规律后通过for循环总和int max = arrs[0];for (int i = 1; i < arrs.length - 1; i++) {if (arrs[i] > max) {max = arrs[i];}}//转化为字符串求位数int maxLength = (max + "").length();for (int k = 0, n = 1; k < maxLength; k++, n *= 10) {for (int i = 0; i < arrs.length; i++) {int digitOfElement = arrs[i] / n % 10; // '/'去余 '%'取余bucketElement[digitOfElement][bucketElementCount[digitOfElement]] = arrs[i];bucketElementCount[digitOfElement] += 1;}int index = 0;for (int i = 0; i < bucketElementCount.length; i++) {if (bucketElementCount[i] != 0) {for (int j = 0; j < bucketElementCount[i]; j++) {arrs[index] = bucketElement[i][j];index++;}bucketElementCount[i] = 0;}}System.out.println(Arrays.toString(arrs));}}}

排序算法对比

查找算法

顺序(线性)查找二分查找/折半查找插值查找斐波那契查找

线性查找算法

有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】

要求: 如果找到了，就提示找到，并给出下标值。

public class SequenceSearch {public static void main(String[] args) {int[] arr = {1, 2, 4, 4, 5, 6, 7, 8, 9, 10};int findVal = 7;for (int i = 0; i < arr.length - 1; i++) {if (arr[i] == findVal) {System.out.println("查找的数值是数组的第" + (i + 1) + "");}}}}

二分查找

请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

二分查找的思路分析:

1.首先确定该数组的中间的下标：mid = (left + right) / 2

2.然后让需要查找的数 findVal 和 arr[mid] 比较

findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找

findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找

findVal == arr[mid] 说明找到，就返回

3.什么时候结束递归

找到就结束递归

递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出

import java.util.ArrayList;public class BinarySearch {public static void main(String[] args) {int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 8, 9};System.out.println(binarySearch(arr, 0, arr.length - 1, 7));}public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal) {if (left > right) {return new ArrayList<>();// 没有就床褥一个空的ArrayList集合回去}int mid = (left + right) / 2;if (findVal > arr[mid]) {return binarySearch(arr, mid + 1, right, findVal);} else if (findVal < arr[mid]) {return binarySearch(arr, left, mid - 1, findVal);} else {ArrayList<Integer> findList = new ArrayList<>();findList.add(mid);// 先把确定存入list中int tmp = mid;// 当进入这个else证明mid=findVal,因为前提数组是有序的，所以相同的findVal必然会出现在这个数的左边或者右边while (true) {if (left < 0 || arr[tmp - 1] != findVal) { // 当检查左边到达边界或者下一个已经不是则没有findValbreak;}// 如果有则加入集合继续考虑还是否存在findList.add(tmp - 1);tmp -= 1;}tmp = mid;while (true) {if (right > arr.length - 1 || arr[tmp + 1] != findVal) { // 当检查左边到达边界或者下一个已经不是则没有findValbreak;}// 如果有则加入集合继续考虑还是否存在findList.add(tmp + 1);tmp += 1;}return findList;}}}

插值查找

插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 findVal

插值查找的注意事项：

1.对于数据量比较大，关键字发布较为均匀的查找表来说，采用插值查找方法，速度较快。

2.对于关键字发布不均匀的查找表来说，此方法不一定比折半查找要好。

import java.util.ArrayList;public class InsertValueSearch {public static void main(String[] args) {int[] arr = new int[100];for (int i = 0; i < 100; i++) {arr[i] = i + 1;}System.out.println(insertValueSearch(arr, 0, arr.length - 1, 0));}public static int insertValueSearch(int[] arr, int left, int right, int findVal) {if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {return -1;}int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);if (findVal > arr[mid]) {return insertValueSearch(arr, mid + 1, right, findVal);} else if (findVal < arr[mid]) {return insertValueSearch(arr, left, mid - 1, findVal);} else {return mid;}}}

参考链接