java数据结构与算法（再版）（二）-阿里云开发者社区

链表（Linked List）

链表的介绍

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

上图小结：

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

单链表（带头结点）逻辑结构示意图如下（他只是逻辑上有序的，但是物理上他不是有序的）

单链表的创建思路

添加（创建）

1.先创建一个head头节点，作用就是表示单链表的头

2.后面我们每添加一个节点，就直接加入到链表的后面

遍历：

1.通过一个辅助变量遍历，帮助遍历整个链表

不考虑编号问题的写法

完整代码

public class SingleListLinkedDemo {
    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.AddHero(hero1);
        singleLinkedList.AddHero(hero2);
        singleLinkedList.AddHero(hero3);
        singleLinkedList.AddHero(hero4);
        //显示英雄
        singleLinkedList.ShowLinkedList();
    }
}



//定义一个SingleLinkedList管理英雄
class SingleLinkedList{
//创建一个头节点，头节点不能动否则就无法找到其他的节点
    private HeroNode Head = new HeroNode(0,"0","");

    //创建一个辅助变量来管理头节点
    //添加节点到链表当中
    //1.不考虑编号添加的时候全部添加到节点的末尾
    //2.通过循环找到循环的末尾
    public void AddHero(HeroNode heroNode){
        HeroNode tmp = Head;
        //通过循环找到链表的末尾
        while (tmp.next != null) {
            //如果是链表的末尾那么就直接结束循环
            //然后将节点后移
            tmp = tmp.next;
        }
        tmp.next = heroNode;
    }

    public void ShowLinkedList(){
        //用头节点来判断下一个存不存在
        if (Head.next == null){
            System.out.println("链表为空，没有数据");
            return;
        }

        //因为头节点不能动所以只能用一个辅助变量来遍历
        HeroNode tmp = Head;
        while (tmp.next != null) {
            //一定要记得将节点下移不然就会死循环
            tmp = tmp.next;
            System.out.println(tmp.toString());
        }
    }



}


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;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

考虑编号问题的思路

首先找到要添加节点的位置，我们需要一个辅助变量（指针来作为插入数据的前一个数据），通过遍历来实现
当找到位置后就通过新的节点.next = temp.next来指向4的位置
temp.next = 新的节点；

编号问题代码实现

public void addByOrder(HeroNode heroNode){
    //因为是单链表所以我们只能找要添加地方的前一个节点不然无法添加了
    //通过一个标识来判断是否要添加
    boolean flag = false;
    HeroNode tmp = Head;
    while(true){
        if (tmp.next == null){
            break;//当遍历完后就直接结束
        }else if (tmp.next.no > heroNode.no){
            //当遇到当前节点的next的no大于我们要插入的节点时就break
            break;
        }else if (tmp.next.no == heroNode.no){
            //说明已经放入过该编号了就要改变flag的值
            flag = true;
            break;
        }
        tmp = tmp.next;//一定要向后移动一位
    }
    //然后判断flag的状态
    if (flag){
        System.out.println("准备加入的编号"+heroNode.no+"已经存在了");
    }
    heroNode.next = tmp.next;//新节点的next指向tmp.next
    tmp.next = heroNode;//之前的的节点指向新的节点
}

修改信息

思路+完整代码

这里有几个小细节，首先这个变量指向的是头节点的下一个节点，而不是头节点，这样比较快一点

如果这里还用tmp.next的话最后一个的next就是null就直接break了，有一个节点就不会被操作，所以这里只能是tmp ==null就代表遍历完了。

public void upData(HeroNode NewHeroNode){
        boolean flag = false;
        if (Head.next == null){
            System.out.println("链表为空，不能修改");
            return;
        }
        //还是要用一个临时变量来作为辅助
        HeroNode tmp = Head.next;
        while(true){
            if (tmp == null){
                //如果这里还用tmp.next的话最后一个的next就是null就直接break了，所以这里只能是tmp ==null就代表遍历完了
                break;
            }
            else if (tmp.no == NewHeroNode.no){
                flag=true;
                break;
            }
            tmp = tmp.next;//继续往下移动
        }
        if (flag){
        tmp.name = NewHeroNode.name;
        tmp.nickName = NewHeroNode.nickName;
    }else {
            System.out.println("你要修改的"+NewHeroNode.no+"不存在");
        }
    }

删除信息

思路

我们先找到需要删除的这个节点的前一个节点 temp
temp.next = temp.next.next
被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

注意的细节

首先tmp指向的必须是头节点如果指向的是Head.next那么第一个节点就会被跳过，就会删除不到

必须是tmp.next == null 如果不是那么在else if (tmp.next.no == no)中就会有空指针异常，应为在最后指针才会后移，所以当到林冲的时候指针没有移动如果是tmp == null 那么这里就不会break

public void del(int no){
        HeroNode tmp = Head;
        boolean flag = false;
        while (true){
            if (tmp.next == null){
                break;
            }else if (tmp.next.no == no){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if (flag){
            tmp.next = tmp.next.next;//这里的tmp.next就是3指向了null
        }else {
            System.out.println("你要删除的节点不存在"+"---"+no);
        }

单链表算法问题

查找单链表的倒数第k个【新浪面试题】

思路：

接收head节点，同时接收一个index
index，表示的是倒数第index个节点
先把链表重头到尾遍历一次，等到总长度getlength
得到size后，我们从链表的第一个开始遍历（size - index）个，就可以得到
如果找到了就返回该节点，否则就是null

完整代码

public static HeroNode FindLastIndexNode(HeroNode head, int index){
    //index表示的是第几个节点
    //先把链表从头到位遍历一次，得到size
    //然后在返回（size - index）的位置的节点
    int size = getLength(head);
    if (head.next == null){
        //空节点直接返回空
        return null;
    }else if (index < 0 || index > size ){
        return null;
    }
    //这里用一个辅助变量来接受后面的节点
    HeroNode temp = head.next;
    for (int i = 0; i < (size - index) ; i++) {
        //让指针往下移，找到我们要找的位置
        temp = temp.next;
    }
    return temp;
}

//计算链表的长度
public static int getLength(HeroNode head){
        int len = 0;
        //判断是否为空，如果为空的话就直接返回
        if (head.next == null){
            return 0;
        }
        HeroNode node  = head.next;
        while (node != null){
            len++;
            node = node.next;
        }
        return len;
    }

单链表反转（腾讯面试题，有点难度）

思路：

先创建一个reverseHead的新节点，遍历每一个节点，然后取出每一个节点
将取出的节点放到reverse的最前端，先取出来的往后放
然后将head.next = reverseHead.next;

完整代码

public static void ReverseNode(HeroNode head) {
        if (head.next == null || head.next.next == null) {
            System.out.println("链表为空，无法反转");
            return;
        }
        //创建一个新的头节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        HeroNode tmp = head.next;
        HeroNode next = null;//这里要有next如果取出来一个节点没有指向的话链表会断掉,指向当前tmp的下一个节点
        while (tmp != null) {
            next = tmp.next;//让next指向下一个节点，作为保留变量
            tmp.next = reverseHead.next;//这里的=不能看做赋值而是要看作指向，就意味着tmp.next原来的指向发生了改变，指向了null       
            reverseHead.next = tmp;//然后reverse.next在指向tmp。
            tmp = next;//tmp指针向后移动
        }
        head.next = reverseead.next;
    }

单链表从尾到头打印链表（百度的面试题）

思路：

方式一：可以先将数组反转，然后在依次的打印出节点，但是不推荐，因为这样会破环原有的数据结构。
方式二：利用栈的先进先出的特点，将每一个元素压栈，然后依次弹出就是倒序打印了

完整的代码实现

public static void ReverseOut(HeroNode hero){
        Stack<HeroNode> stack = new Stack<>();
        HeroNode tmp = hero.next;
        while (tmp != null){
            stack.add(tmp);
            tmp = tmp.next;
        }
        while (stack.size() > 0){
            HeroNode reverseHero = stack.pop();
            System.out.println(reverseHero);
        }
    }

合并两个有序链表

思路：

首先先创建一个新的节点，用新的节点将两个链表连起来
比较两个节点的大小，如果有一个节点比前一个节点大那么就用创建的节点连接，新的节点向后移动
最后加判断，防止两个链表的长度不一致，有的遍历完了有的确没有遍历完，最后直接让新节点的下一个节点等于没有遍历完的节点

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       ListNode pre = new ListNode(-1),p = pre;
       ListNode p1 = list1;
       ListNode p2 = list2;
       while(p1 != null && p2 != null){
           if(p1.val >= p2.val){
               p.next = p2;
               p2 = p2.next;
           }else{
               p.next = p1;
               p1 = p1.next;
           }
           p = p.next;
       }
       if(p1 != null){
           p.next = p1;
       }if(p2 !=null){
           p.next = p2;
       }
       p1 =null;
       p2 = null;
       p = null; 
       System.gc();
       return pre.next;
    }

删除链表中的元素

!思路：

首先要考虑全是重复的元素怎么删除

第二还要创建一个辅助变量来进行移除

另外还要注意一些小细节

完整代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
         while(head != null && head.val == val ){
          head = head.next;
        }//这里是为了防止元素一致的
        if(head == null){
            return head;
        }//要先把元素一致的元素删除在返回，应为如果head本身是null的话前面就不会执行了，如果前面的语句放到返回语句的后面的话，下面的while语句就会报错，因为此时的这里head已经为null了
        ListNode tmp = head;
        while(tmp.next != null){
            if(tmp.next.val == val){
                tmp.next = tmp.next.next;
            }else{
                tmp =tmp.next;//因为前面用了tmp.next，这里就要判断一下否要移动，如果这里不加else那么当tmp已经为null在进行tmp.next !=null判断的时候就会报错，但是前面直接用tmp！=null继续判断当到最后一个节点的时候if语句就会报错。
            }
            
        }
        tmp = null;
        System.gc();
        return head;
    }
}

环形链表

思路：

这个问题可以类比为摩托车追小车

小汽车和自行车从跑道的起点同时出发
如果没有环道，那么小汽车永远离自行车而去
如果有环道，最终小汽车最终会追上自行车

如果是应用到代码当中，就创建两个辅助指针让他们同时指向head，其中让一个指针移动快一点，一个指针移动慢一点

如果是一个环的话那么这个最终这个快的就会追上这个慢的。

代码实现

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode last = head;
        ListNode first = head;
        while(first !=null && first.next != null ){
           last = last.next;
           first = first.next.next;
           if(last == first){
               return true;
           }
        }
        last = null;
        first = null;
        System.gc();
        return false;
    }
}

双向链表

分析双向链表的遍历，添加，修改，删除的操作思路

遍历和单向链表一样，但是双向链表可以从末尾向前遍历，也可从前向后遍历。

添加（默认添加到双向链表的末尾）：

就是将LastNode.next = NewNode;

NewNode.pre = LastNode;

修改和单链表的修改一样

删除

因为是双向链表，所以我们可以不用指向要删除链表的前一个，而是可以直接指向要删除的节点
就将DelNode.pre.next = DelNode.next;
Delnode.next.pre =DelNode.pre;

双向链表完整代码

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //双向链表的测试
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(7, "林冲", "豹子头");


        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.AddHero(hero1);
        doubleLinkedList.AddHero(hero2);
        doubleLinkedList.AddHero(hero3);
        doubleLinkedList.AddHero(hero4);
        //展示列表
        doubleLinkedList.ShowLinkedList();


    }
}


class DoubleLinkedList {
    //创建一个头节点，头节点不能动否则就无法找到其他的节点
    private HeroNode2 Head = new HeroNode2(0, "0", "");

    public HeroNode2 getHead() {
        return Head;
    }

    public void ShowLinkedList() {
        //用头节点来判断下一个存不存在
        if (Head.next == null) {
            System.out.println("链表为空，没有数据");
            return;
        }

        //因为头节点不能动所以只能用一个辅助变量来遍历
        HeroNode2 tmp = Head;
        while (tmp.next != null) {
            //一定要记得将节点下移不然就会死循环
            tmp = tmp.next;
            System.out.println(tmp.toString());
        }
    }

    //创建一个辅助变量来管理头节点
    //添加节点到双向链表当中
    //1.不考虑编号添加的时候全部添加到节点的末尾
    //2.通过循环找到循环的末尾
    public void AddHero(HeroNode2 heroNode) {
        HeroNode2 tmp = Head;
        //通过循环找到链表的末尾
        while (tmp.next != null) {
            //如果是链表的末尾那么就直接结束循环
            //然后将节点后移
            tmp = tmp.next;
        }
        tmp.next = heroNode;
        //新的节点的前一个节点指向tmp
        heroNode.pre = tmp;
    }

    //修改节点信息，双向链表几乎和单链表的一样
    //根据no来修改人物信息，no不能动
    public void upData(HeroNode NewHeroNode) {
        boolean flag = false;
        if (Head.next == null) {
            System.out.println("链表为空，不能修改");
            return;
        }
        //还是要用一个临时变量来作为辅助
        HeroNode2 tmp = Head.next;
        while (true) {
            if (tmp == null) {
                //如果这里还用tmp.next的话最后一个的next就是0就直接break了，所以这里只能是tmp ==null就代表遍历完了
                break;
            } else if (tmp.no == NewHeroNode.no) {
                flag = true;
                break;
            }
            tmp = tmp.next;//继续往下移动
        }
        if (flag) {
            tmp.name = NewHeroNode.name;
            tmp.nickName = NewHeroNode.nickName;
        } else {
            System.out.println("你要修改的" + NewHeroNode.no + "不存在");
        }
    }
    //双向链表删除节点，可以不用找到前一个节点而是可以直接找到要删除的节点
    public void del(int no) {

        HeroNode2 tmp = Head.next;
        boolean flag = false;
        while (true) {
            if (tmp == null) {//已经找到链表最后的后一个了
                break;
            } else if (tmp.no == no) {
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if (flag) {
          tmp.pre.next = tmp.next;
          //如果我们正好要删除的节点是最后一个
          if (tmp.next != null){
              //那么这里的tmp.next就会报错（因为此时的tmp为null），所以这里要加上条件判断
              tmp.next.pre = tmp.pre;
          }
        } else {
            System.out.println("你要删除的节点不存在" + "---" + no);
        }
    }


}

class HeroNode2 {
    public int no;
    public String name;
    public String nickName;
    public HeroNode2 next;
    //指向前一个节点
    public HeroNode2 pre;

    public HeroNode2(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode2{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

双向链表有序添加元素

public void AddByOrder(HeroNode2 heroNode2){
         HeroNode2 tmp = Head;
         while (true){
             if (tmp.next == null){
                 break;
             }
             //如果寻找的是当前节点的话那么。就会写四个指向的语句这样就会形成闭环，就会死循环
             if (heroNode2.no <= tmp.next.no){
                 break;
             }
             tmp = tmp.next;
         }
    
        if (tmp.next == null){
            tmp.next = heroNode2;
            heroNode2.pre = tmp;
            return;
        }
        heroNode2.next = tmp.next;
        tmp.next = heroNode2;
        heroNode2.pre = tmp;
    }

约瑟夫问题分析

单向环形链表的实现

思路分析：

创建第一过节点，first让指向该节点，并形成闭环

后面当我们每创建一个新的节点，就把该节点，加入到已有的闭环中

遍历：

通过一个curboy（辅助变量），指向first节点

通过while循环来进行遍历，当curboy .next == first的时候就是已经遍历完成

生成环形链表完整代码

class CircleSingleLinked{
    //先设置一个头指针
    private Boy first = null;

    public void addBoy(int nums){
        //通过for循环来添加小孩
        //先对数据进行判断，必须至少有一个小孩
        if (nums < 1){
            System.out.println("nums的值不正确");
            return;
        }

        Boy curBoy  = null;//辅助指针
        for (int i =1 ; i <= nums ; i++) {
            //如果i==1 那么就将一个boy节点指向自己
            Boy boy = new Boy(i);
            if (i == 1){
               first = boy;
               first.setNext(boy);//构成环
                curBoy = first;//辅助指针指向第一个小孩
            }else {
                curBoy.setNext(boy);
                //后面加的人连上第一个小孩形成环状
                boy.setNext(first);
                //cur指针向后移动
                curBoy = curBoy.getNext();
            }
        }
    }

    public void showBoy(){
        if (first == null){
            System.out.println("没有小孩");
            return;
        }
        //通过
        Boy curBoy = null;
        curBoy = first;
        while (true) {
            System.out.println("小孩编号---" + curBoy.getNo());
            if (curBoy.getNext().getNo() == first.getNo()){
                break;
            }
            curBoy = curBoy.getNext();
        }
    }
}



class Boy{
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

小孩出圈问题

思路分析

根据用户的输入，生成一个小孩出圈的顺序

n = 5 , 即有5个人

k = 1, 从第一个人开始报数

m = 2, 数2下

首先创建两个指针一个头指针（first），一个为helper（始终在first的尾部，事先应该指向环形链表的最后这个节点）
当小孩开始数数的时候先让f，h移动k -1次（f,要在k之后，因为这里k刚好为1，所以不需要移动如果k为3，那么需要移动2次如下图）
当开始报数的时候，first和helper相继移动m-1次
然后在将first指针下移first = first.next;， help.next = first;(当2没有引用的时候gc自动将他回收)
这个时候小孩就会出圈

完整代码实现

public void showBoy(){
        if (first == null){
            System.out.println("没有小孩");
            return;
        }
        //通过辅助指针来遍历
        Boy curBoy = null;
        curBoy = first;
        while (true) {
            System.out.println("小孩编号---" + curBoy.getNo());
            if (curBoy.getNext().getNo() == first.getNo()){
                break;
            }
            curBoy = curBoy.getNext();
        }
    }
    /**
     *
     * @param StartNum 表示从第几个小孩开始数数*
     * @param endNum 表示数几下
     * @param nums 表示最初有几个小孩在圈中
     */
    public void countBoy(int StartNum, int endNum,int nums){
        if (StartNum < 1 || StartNum > nums || first == null){
            System.out.println("输入的参数有误");
        }
        //创建一个辅助指针helper
        Boy helper = first;
        while (true){
            //当helper指针的后一个是first时那么说明helper已经位于first之后
            if (helper.getNext() == first){
                break;
            }
            //如果不是那helper继续移动
            helper = helper.getNext();
        }
        //当小孩开始数数之前先让两指针移动，StartNum-1的次数
        for (int i = 0; i < StartNum - 1 ; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //小孩开始数数的时候让f,h移动endNum - 1 ,并且让小孩出圈
        while (true){
            if (helper == first){
                //当其他小孩都出圈后，就剩一个小孩，那么就结束循环
                break;
            }
            for (int i = 0; i < endNum - 1 ; i++) {
                //first要移动到要出圈小孩的位置
                first = first.getNext();
                helper = helper.getNext();
            }
            //要出圈的小孩
            System.out.println("出圈的小孩---------"+first.getNo());
            //让出圈的小孩出圈
            first = first.getNext();
            helper.setNext(first);

        }
        System.out.println("最后留在圈中的小孩"+helper.getNo());

栈

栈的引入

栈的介绍

栈的英文为（stack）
栈是一个先入后出（FILO模式）的有序列表
栈是限制线性列表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，允许插入的删除的一端，为变化的一端，称为栈顶（Top）,另外一端为固定的一端，称为栈底（Bottom）.
根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
出栈（pop）和入栈（push）

栈的应用场景

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

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

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

4)二叉树的遍历。

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

栈的快速入门

用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，接下来就用栈来模拟栈的出栈和入栈操作

实现栈的思路分析：

用数组来模拟出栈和入栈
先定义一个Top从-1开始，来表示栈顶
入栈的时候TOP++；Static[Top] = data;
出栈的时候value = Static[Top] ;Top--; return value

完整代码实现

class ArrayStack {
        private int Maxsize;
        private int[] Stack;
        private int Top = -1;

        //初始化

        public ArrayStack(int maxsize) {
            this.Maxsize = maxsize;
            Stack = new int[maxsize];
        }

        //判断是否为空
        private boolean isEmpty() {
            return Top == -1;
        }

        //判断是否为满
        private boolean isFull() {
            return Top == Maxsize - 1;
        }

        //入栈(push)
        public void push(int no) {
            //先判断是否为满
            if (isFull()) {
                System.out.println("栈已满，无法入栈");
                return;
            }
            Top++;
            Stack[Top] = no;
        }

        //出栈(pop)
        public int pop() {
            //判断是否为空
            if (isEmpty()) {
                throw new RuntimeException("栈为空，没有数据");
            }
            int value = Stack[Top];
            Top--;
            return value;
        }

        //展示栈（遍历）
        public void showStack() {
            //判断是否为空
            if (isEmpty()) {
                System.out.println("数组为空，无法遍历");
                return;
            }
            //循环
            for (int i = Top; i >= 0; i--) {
                System.out.printf("Stack[%d]=%d", i, Stack[i]);
                System.out.println();
            }
        }
    }

使用栈完成计算一个表达式结果

思路

1.先创建一个数栈（numStack）和一个符号栈(operatStack)

2.创建一个index的指针来进行扫描，如果是数字那么直接入数栈，如果是符号就入符号栈

3.入符号栈分两种情况

3.1当入符号栈的时候判断符号栈是否为空

3.1.1如果为空那么就直接入栈

3.1.2如果不为空那么，那先判断符号的优先级，如果扫描到的符号的优先级小于已入符号栈的符号的优先级，那么就先pop（）数栈的两个数字进行运算，然后在pop（）符号栈的符号然后进行运算，将运算的结果重新入栈，然后再将等了很久的符号入栈。

3.1.3如果扫描到的符号优先级小于已入栈的符号优先级，那么就直接加入符号栈中。

4.依次pop出栈中的数字和符号进行运算，将最后的运算结果放入数栈当中。

代码实现（在之前的栈新加一些功能）

//首先先创建两个詹，一个用于存放数字，一个用于存放符号
        ArrayStack NumberStack = new ArrayStack(10);
        ArrayStack operStack = new ArrayStack(10);
        //要计算的式子
            String s = "70+3-1";
            String keepNum = "";
        //设置一个扫描器
        int index = 0;
        //相加的数字
        int num1 = 0;
        int num2 = 0;
        //运算符
        int oper = 0;
        //要存入的字符
        char ch = ' ';//每次扫描都存入到char
        //结果
        int res = 0;
        while(true){
            //开始扫描,查看s中每一个字符
            ch = s.substring(index,index+1).charAt(0);
            //判断ch是什么如果是一个运算符就做相应的操作
            if (operStack.isOperate(ch)){
                if (!operStack.isEmpty()){
                    //如果不为空做相应的操作
                    //首先先判断符号的优先级,如果大于之前的运算符就直接放入，如果不是大于的话就先pop出一个符号和两个数进行运算；
                    int priority = operStack.priority(ch);
                    System.out.println(ch);
                    if (priority  <=  operStack.priority((char)operStack.showTop())){
                        oper = operStack.pop();
                        num1 = NumberStack.pop();
                        num2 = NumberStack.pop();
                        res = NumberStack.Cal(num1,num2, (char) oper);
                        //将运算结果放到数栈当中
                        NumberStack.push(res);
                        operStack.push(ch);
                    }else {
                        operStack.push(ch);
                    }
                }else {
                    //为空直接入栈
                    operStack.push(ch);
                }
            }else {
                //如果不是运算符的话就直接入数栈，并且这里要注意这里的 1 并不是真的意义上的一而是字符 字符1 对应的ASCII码是49 相差48
                //NumberStack.push(ch - 48);（这里有点问题）
                //思路这里当作一个多位数处理不能发现了数字就直接加入到数栈当中，先往下继续扫描，如果是数字那么就将两个数进行拼接
                //创建一个变量来进行字符串拼接
                //然后判断表达式中index后面的字符串是不是符号，如果不是就不能入栈，是才入栈
                /**
                如果没有这个keepNum变量来储存那么这个计算机就只能计算一位数
                例如不经过判断直接把字符加进去那么就只能做个位数计算
                
                **/
                keepNum += ch;
                if (index == s.length() -1){
                    //应为运算符最后就是数字，如何index到了最后一位就直接入栈
                    NumberStack.push(Integer.parseInt(String.valueOf(keepNum)));
                }else {
                    //往后面看一下是否为运算符如果是运算符就直接将前面的数入栈
                    if (operStack.isOperate(s.substring(index+1,index+2).charAt(0))){
                        NumberStack.push(Integer.parseInt(String.valueOf(keepNum)));
                        //这里把keepNum加进去后要重置keepNum;
                        keepNum = "";
                    }
                }

            }
            //判断是否扫描完成
            index++;
            if (index >= s.length()){
                break;
            }
        }
        //扫描完成后依次从中取出相应的符号和数字进行一次的计算
        num1 = NumberStack.pop();
        num2 = NumberStack.pop();
        oper = operStack.pop();
        res = NumberStack.Cal(num1,num2,(char) oper);
        NumberStack.push(res);
        System.out.println(NumberStack.showTop());
    }

class ArrayStack {
        private int Maxsize;
        private int[] Stack;
        private int Top = -1;


        //初始化

        public ArrayStack(int maxsize) {
            this.Maxsize = maxsize;
            Stack = new int[maxsize];
        }


        //判断是否为空
        public boolean isEmpty() {
            return Top == -1;
        }

        //判断是否为满
        public boolean isFull() {
            return Top == Maxsize - 1;
        }

        //入栈(push)
        public void push(int no) {
            //先判断是否为满
            if (isFull()) {
                System.out.println("栈已满，无法入栈");
                return;
            }
            Top++;
            Stack[Top] = no;
        }

        //出栈(pop)
        public int pop() {
            //判断是否为空
            if (isEmpty()) {
                throw new RuntimeException("栈为空，没有数据");
            }
            int value = Stack[Top];
            Top--;
            return value;
        }

        //展示栈（遍历）
        public void showStack() {
            //判断是否为空
            if (isEmpty()) {
                System.out.println("数组为空，无法遍历");
                return;
            }
            //循环
            for (int i = Top; i >= 0; i--) {
                System.out.printf("Stack[%d]=%d", i, Stack[i]);
                System.out.println();
            }
        }

        //设置每个符号的优先级，可以用人为操控
        public int priority(char oper){
            if (oper == '*' || oper == '/'){
                return 1;
            }else if (oper == '+' || oper == '-'){
                return 0;
            }else {
                return -1;//目前只计算+ - * /
            }
        }
        //判断是不是一个运算符
        public boolean isOperate(char val){
            if (val == '*' || val == '/' || val == '+' ||val == '-'){
                return true;
            }
            return false;
        }

        //计算方法
        public int Cal(int num1,int num2,char oper){
            int res = 0;
            switch (oper){
                case '*' :
                    res = num1 * num2;
                    break;
                case '-':
                    res = num2 - num1;//被减数先入栈，减数后入栈，所以要后面的减前面的
                    break;
                case '/':
                    res = num2/num1;
                    break;
                case '+':
                    res = num1 + num2;
                    break;
                default:
                    System.out.println("特殊错误");
                    break;
            }
            return res;
        }

        //增加一个方法可以看到栈顶的元素
        public int showTop(){
            return Stack[Top];
        }

前缀，中缀，后缀表达式

前缀表达式（波兰表达式）

前缀表达式又称波兰表达式，前缀表达式的运算符位于操作数之前
举例说明：(3+4) x5-6对应的前缀表达式- x 3 4 5 6

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
从右至左扫描，将6、5、4、3压入堆栈
遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

中缀表达式

中缀表达式就是常见的运算表达式，如(3+4)×5-6
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

后缀表达式

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
计算方法：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
再比如:4586082x/++-

正常表达式	逆波兰表达式
a+b	ab+
a+(b-c)	abc-+
a+(b-c)*d	abc-d*+
a+d*(b-c)	adbc-*+
a=1+3	a13+=

逆波兰计算器

我们完成一个逆波兰计算器，要求完成如下任务:

输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
只支持对整数的计算。
例如计算：(3+4) x5-6 ---->后缀表达式 == 3 4 + 5 x 6 -

思路：

先创建一个ArrayList来存放数字和符号，然后通过方法将ArrayList传入到stack中

从左到右进行扫描，将3和4压入栈

遇到+运算符，因此弹出4(栈顶)3(次栈顶)进行相加为7，7入栈

5入栈

继续扫描遇到+弹出5和7进行相乘为35，将35入栈

6入栈

遇到- 计算35-6的值，得29

public static void main(String[] args) {
        //先定义逆波兰表达式
        //(3+4)x5-6 ---> 3 4 + 5 x 6 -;

        //先定义一个表达式
        String ReverseExpression = "3 4 + 5 x 6 -";
        int res = Calculate(getString(ReverseExpression));
        System.out.printf("res=%d",res);
    }

    public static List<String> getString(String expression) {
        //先创建一个ArrayList,将每一个元素添加进去
        //通过空格隔开
        String[] spit = expression.split(" ");
        return new ArrayList<>(Arrays.asList(spit));
    }

    public static int Calculate(List<String> list) {
        /**
         * 从左至右扫描，将3和4压入堆栈；
         * 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
         * 将5入栈；
         * 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
         * 将6入栈；
         * 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
         */
        //先创建一个栈
        Stack<Integer> stack = new Stack<>();
        //扫描ArrayList，通过正则表达式
        for (String item : list) {
            if (item.matches("\\d+")) {
                //有至少一个数字就直接入栈
                stack.add(Integer.parseInt(item));
            } else {
                int res = 0;
                //因为除法和减法都是后弹出来的除/减第一个所以这么num1作为后弹出来的·
                int num2 = stack.pop();
                int num1 = stack.pop();
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                }else if (item.equals("x")){
                    res = num1 * num2;
                }else if (item.equals("/")){
                    res = num1/num2;
                }else {
                    throw new RuntimeException("无效符号");
                }
                //将res入栈
                stack.push(res);
            }

        }
        return stack.pop();
    }

结果为res = 29

递归

递归的应用场景

实际应用场景，迷宫问题(回溯)，递归(Recursion)

递归的概念

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

递归的调用机制

打印问题
阶乘问题

递归的调用规则

程序执行到一个方法的时候就开辟一块独立的空间（栈空间）。
每个空间的数据(局部变量)，是独立的。
当一个方法执行完毕的时候，或者是遇到return的时候，就会返回，遵守谁调用就将结果返回给谁，同时当方法执行完毕或者返回时候，该方法也执行完毕，只有上一个方法执行完毕（出栈）后，后面的方法才会继续执行。
递归必须向递归退出的条件无限逼近不然的话就会di di di下去了最后就会导致栈溢出。
如果方法中使用的是引用数据类型(比如数组)，就会共享该引用数据类型的数据。

//打印问题
    public static void test(int n) {
        if (n > 2) {
            test(n - 1);
        }
        System.out.println("n=" + n);
    }

//阶乘
public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
        }}

递归能解决的问题

各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
将用栈解决的问题-->第归代码比较简洁

递归迷宫问题

说明：

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

代码实现

public class MiGong {
    public static void main(String[] args) {
        //先初始化一个数组
        int[][] map = new int[8][7];
        //将第一行和第七行的每一列都用1来封上
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //第一列和第七列的每一行用1封上
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板
        map[3][1] = 1;
        map[3][2] = 1;


        //输出地图
        System.out.println("最开始的地图");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();

        }
        SetWay(map,1,1);
        System.out.println("小球走完后的---地图");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();

        }

    }


    //1.map表示地图
    //2.i, j 表示小球的坐标（1，1）
    //3.当map[6][5] =2的时候表示路已经找到结束
    //4.约定:当map[i][j] 为1 的时候表示围墙，为2的时候表示该路走过了，为3的时候表示该路走过了但是走不通
    //5.指定找路的步骤 上 --- 右 ---- 下 ---- 左

    /**
     * @param map 传入的地图
     * @param i   小球的横坐标
     * @param j   小球的纵坐标
     */
    public static boolean SetWay(int[][] map, int i, int j) {
        if (map[6][5] == 2){//如果终点已经走到了那么就直接结束
            return true;
        }else {
            if (map[i][j] == 0){
                //想尝试去走
                map[i][j] = 2;
                //走着的路线上 --- 右 ---- 下 ---- 左
                if (SetWay(map,i-1,j+1)){//往上走
                    return 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{
                    //如果这个路线都走不通那么就是死路返回3
                    map[j][i] = 3;
                    return false;
                }

                }else {//map[j][i] != 0 ,可能是1，2(表示已经走过了不用重复再走），3
                return false;
            }

        }

    }
}

八皇后问题（回溯算法）

问题介绍

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

八皇后问题算法分析

第一个皇后先放第一行第一列
第二个皇后放在第二行第一列、然后判断是否OK，如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应 arr 下标表示第几行，即第几个皇后，arr[i] = val , 每一个val对应的都是i+1个皇后，每一行对应一个皇后，放在第i+1行的第val+1列

完整代码加分析

public class Queue8 {
    //先初始化数组
    private int Max = 8;
    //保存皇后放置后的正确的位置 arr = {0,4,7,5,2,6,1,3}
    private int[] arr = new int[Max];
    private static int count = 0;
    private static int JudgeCount = 0;
    public static void main(String[] args) {
        new Queue8().Check(0);
        System.out.println("一共有"+count+"解法");
        System.out.println("一共回溯"+JudgeCount+"次");
    }



    //开始摆放
    private void Check(int n){
        //如果n == 8的时候就直接退出表明已经找了正确的放法
        if (n == Max){
            ShowSolution();//找到正确的放法后就输出答案
            return;
        }
        for (int i = 0; i < Max; i++) {
            //开始摆放棋子,把第一个皇后放在第一行的第一列
            arr[n] = i;
            if (judge(n)){
                Check(n+1);//这里是判断是否于遇上一个棋子产生冲突，
                // 如果与上一个产生了冲突那么这个位置就会在同行的基础上移动到下一列然后在继续判断直到不会参数冲突为止.
                //即在for循环中继续进行移动判断
            }
        }
    }
    //判断放置的位置是否正确
    /**
     *
     * @param n 表示第n个皇后
     * @return 是否和条件有冲突
     */
    private boolean judge(int n){
        JudgeCount++;
        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;
    }

    //写一个方法来展示每一种解法
    private void ShowSolution(){
        count++;
        for (int i = 0; i < Max; i++) {
            System.out.print(arr[i]+ " ");
        }
        System.out.println();
    }

排序算法

排序算法的介绍

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

内部排序：

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

外部排序法：

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

常见的排序算法

冒泡排序

基本介绍

冒泡排序（Bubble Sorting）的基本思想是：

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

冒泡排序实例

我们将五个无序的数：3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。

小结冒泡排序的规则

一共进行数组的大小-1次大的循环
每一趟排序的次数在逐渐的减少
如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序（优化）

代码实现（未优化版）

public class Bubble {
    public static void main(String[] args) {
        //创建好要排序的数组
        int[] arr = new int[]{3, 9, -1, 10, -2};
        int tmp = 0;
        //直接再用一个for循环将他括起来
        //时间复杂度O(n^2)
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 -j; i++) {
                if (arr[i] > arr[i + 1]) {//减1就是为了防止arr[i+1]数组越界
                    tmp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = tmp;
                }
            }
            System.out.printf("第%d趟排序的数组",j+1);
            System.out.println(Arrays.toString(arr));
        }



        //由于后面for都是一样的arr.length - 1-1只是每一次都是相继减1所以可以把for循环套起来
        /*
         for (int i = 0; i < arr.length - 1 - 0; i++) {
                if (arr[i] > arr[i + 1]) {//减1就是为了防止arr[i+1]数组越界
                    flag = true;
                    tmp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = tmp;
                }
            }
            System.out.printf("第1趟排序的数组",j+1);
        //减2因为10已经排过了就不用继续参与进来排序
        for (int i = 0; i < arr.length - 1-1; i++) {
            int tmp = 0;
            if (arr[i] > arr[i+1]){//减1就是为了防止arr[i+1]数组越界
                tmp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = tmp;
            }
        }
        System.out.println("第二趟排序的数组");
        System.out.println(Arrays.toString(arr));

        for (int i = 0; i < arr.length - 1-2; i++) {
            int tmp = 0;
            if (arr[i] > arr[i+1]){//减1就是为了防止arr[i+1]数组越界
                tmp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = tmp;
            }
        }
        System.out.println("第3趟排序的数组");
        System.out.println(Arrays.toString(arr));

        for (int i = 0; i < arr.length - 1-3; i++) {
            int tmp = 0;
            if (arr[i] > arr[i+1]){//减1就是为了防止arr[i+1]数组越界
                tmp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = tmp;
            }
        }
        System.out.println("第4趟排序的数组");
        System.out.println(Arrays.toString(arr));
         */
    }

}

代码实现（优化版）

public class Bubble {
    public static void main(String[] args) {
        //创建好要排序的数组
        int[] arr = new int[]{3, 9, -1, 10, 20};
        int tmp = 0;
        //直接再用一个for循环将他括起来
        //时间复杂度O(n^2)
        //优化的先创建一个flag,来表示是否交换，如果有趟都没有交换就直接结束循环
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if (arr[i] > arr[i + 1]) {//减1就是为了防止arr[i+1]数组越界
                    flag = true;
                    tmp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = tmp;
                }
            }
            System.out.printf("第%d趟排序的数组",j+1);
            System.out.println(Arrays.toString(arr));
            if (!flag){
                break;
            }else {
                flag = false;
            }
        }

这是冒泡排序所需要的时间

选择排序

基本介绍

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

选择排序思想

选择排序（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次，得到一个按排序码从小到大排列的有序序列。

选择排序小结：

选择排序一共有数组大小 -1轮排序

每一轮排序，又是一个循环。

循环规则：

先假定当前这个数就是最小数
然后和后面的每一个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标。
当遍历到数组的最后时，就得到本轮最小数和下标
就开始进行交换

代码实现（未优化）

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[]{101, 34, 119, 1};
        select(arr);

    }

    public static void select(int[] arr){
        //测试数组 {101, 34, 119, 1}
        //为了方便理解先进行一轮一轮排序来操作
        //首先我们先假定这个数组中的最小值就是第一个
        int minIndex = 0;
        int min = arr[minIndex];
        //进行循环比较找出真正的最小值
        //这里因为已经假定了一个所以为了不重复比较i就从1开始
        for (int i = 1+0; i < arr.length; i++) {
            //如果我们假定的最小值不是真正的最小值那么就把比较后的最小值作为我们的最小值
            if(min > arr[i]){
                min = arr[i];
                minIndex = i;
            }
            //如果找到了最小值就开始进行交换;
        }
        arr[minIndex] = arr[0];
        arr[0] = min;
        System.out.println("第一趟排序");
        System.out.println(Arrays.toString(arr));



        minIndex=1;
        min = arr[minIndex];
        for (int i = 2; i < arr.length; i++) {
            //如果我们假定的最小值不是真正的最小值那么就把比较后的最小值作为我们的最小值
            if(min > arr[i]){
                min = arr[i];
                minIndex = i;
            }
            //如果找到了最小值就开始进行交换;
        }
        arr[minIndex] = arr[1];
        arr[1] = min;
        System.out.println("第二趟排序");
        System.out.println(Arrays.toString(arr));//由于第二轮交换的时候，

        minIndex=2;
        min = arr[minIndex];
        for (int i = 3; i < arr.length; i++) {
            //如果我们假定的最小值不是真正的最小值那么就把比较后的最小值作为我们的最小值
            if(min > arr[i]){
                min = arr[i];
                minIndex = i;
            }
            //如果找到了最小值就开始进行交换;
        }
        arr[minIndex] = arr[2];
        arr[2] = min;
        System.out.println("第3趟排序");
        System.out.println(Arrays.toString(arr));//由于第二轮交换的时候，交换的时候有一个数字其实已经排好了，所以可以不用在交换
    }
}

代码实现（优化）

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[]{101, 34, 119, 1};
        select(arr);

    }

    public static void select(int[] arr){
        //测试数组 {101, 34, 119, 1}
        //为了方便理解先进行一轮一轮排序来操作
        //首先我们先假定这个数组中的最小值就是第一个
        for (int j = 0; j < arr.length -1; j++) {
            //找到规律后就可以直接嵌套一个循环
            int minIndex = j;
            int min = arr[minIndex];
            //进行循环比较找出真正的最小值
            //这里因为已经假定了一个所以为了不重复比较i就从1开始
            for (int i = 1+j; i < arr.length; i++) {
                //如果我们假定的最小值不是真正的最小值那么就把比较后的最小值作为我们的最小值
                if(min > arr[i]){
                    min = arr[i];
                    minIndex = i;
                }
                //如果找到了最小值就开始进行交换;
            }
            if (minIndex != j){
                //有可能有的元素位置是已经排好了的这个时候就可以不用在进行排序，所以这里加上判断就可以优化一下
                arr[minIndex] = arr[j];
                arr[j] = min;
            }
        }

这是选择排序排8w数据所需要的时间

插入排序

插入排序介绍

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

插入排序思想

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

插入排序图解

分部实现代码

public class InsertSort {
    public static void main(String[] args) {
        Insert(new int[] {101, 34, 119, 1});
    }

    public static void Insert(int[] arr){
        //为了方便理解我们一轮一轮来(同时方便我的理解)
        //测试数组{101, 34, 119, 1}
        //将数组的第一个值看作一个有序数组，他后面的为无序数组，从这个无序的数组中抽出第一个来进行插入
        //先储存要插入的值，
        int indexValue = arr[1];//第一个看作一个值的数组所以从第二个值开始比较插入
        int index = 1-1;
        while(index>=0 && indexValue < arr[index]){
            //index>=0就是为了防止索引越界，为-1;
            //indexValue < arr[index] 找到了待插入的数，就要让比待插入的数大的值往后移
            //同时也是为了退出循环
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = indexValue;//当while循环结束的时候，说明插入的位置找到index就要+1；
        System.out.println("第一轮排序");
        System.out.println(Arrays.toString(arr));


        indexValue = arr[2];//第一个看作一个值的数组所以从第二个值开始比较插入
        index =2-1;
        while(index>=0 && indexValue < arr[index]){
            //index>=0就是为了防止索引越界，为-1;
            //indexValue < arr[index] 找到了待插入的数，就要让比待插入的数大的值往后移
            //同时也是为了退出循环
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = indexValue;//当while循环结束的时候，说明插入的位置找到index就要+1；
        System.out.println("第2轮排序");
        System.out.println(Arrays.toString(arr));


        indexValue = arr[3];//第一个看作一个值的数组所以从第二个值开始比较插入
        index =3-1;
        while(index>=0 && indexValue < arr[index]){
            //index>=0就是为了防止索引越界，为-1;
            //indexValue < arr[index] 找到了待插入的数，就要让比待插入的数大的值往后移
            //同时也是为了退出循环
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = indexValue;//当while循环结束的时候，说明插入的位置找到index就要+1；
        System.out.println("第3轮排序");
        System.out.println(Arrays.toString(arr));
    }



}

完整代码

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        Insert(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void Insert(int[] arr){
        for (int i = 1; i < arr.length ; i++) {
            int indexValue = arr[i];
            int index = i-1;
            while (index>=0 && indexValue<arr[index]){
                arr[index+1] = arr[index];
                index--;
            }
            if (index+1 != i){
            arr[index+1] = indexValue;
        }
        }

插入排序大概我这里就是一秒钟，就可以完成

希尔排序

希尔排序的引入

简单插入排序存在的问题
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

希尔排序的介绍

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

希尔排序的思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。即就是将数组.length/2,进行分组。进行宏观调控

希尔排序图解

操作步骤：

初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

分步代码

public class ShellSort {
    public static void main(String[] args) {
        //{8,9,1,7,2,3,5,4,6,0}
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        Sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void Sort(int[] arr) {
        //为了方便理解，还是一步一步来实现
        //第一轮排序
        int tmp = 0;
        for (int i = 5; i < arr.length; i++) {
            //可以把i=5 i=6代入进去就能理解了 这个j-5是为了退出这一次内循环，进行下一次分组
            for (int j = i - 5; j >= 0; j -= 5) {
                //即相隔距离为 5 的元素组成一组,所以这里要j+5，j+x,x是看分成多少组
                if (arr[j] > arr[j + 5]) {
                    tmp = arr[j + 5];//小
                    arr[j + 5] = arr[j];//后面的位置是大的位置
                    arr[j] = tmp;//小的位置是小的
                }
            }
        }
        //第二轮，因为之前已经分为5组那么现在就是5/2为两组即相邻两个为一组
        for (int i = 2; i < arr.length; i++) {
            //可以把i=5 i=6代入进去就能理解了 这个j-2是为了退出这一次内循环，进行下一次分组
            for (int j = i - 2; j >= 0; j -= 2) {
                //即相隔距离为 2 的元素组成一组,所以这里要j+2，j+x,x是看分成多少组
                if (arr[j] > arr[j + 2]) {
                    tmp = arr[j + 2];
                    arr[j + 2] = arr[j];
                    arr[j] = tmp;
                }
            }
        }

        //第二轮，因为之前已经分为2组那么现在就是2/2 =1 所以就还有1组
        for (int i = 1; i < arr.length ; i++) {
            //可以把i=5 i=6代入进去就能理解了 这个j-1是为了退出这一次内循环，进行下一次分组
            for (int j = i-1; j >=0 ; j-=1) {
                //即相隔距离为 1 的元素组成一组,所以这里要j+1，j+x,x是看分成多少组
                if (arr[j] > arr[j+1] ){
                    tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
                }
            }
    }
}}

完整代码(交换式)

public static void Sort(int[] arr) {
        int tmp = 0;
     //跟据上面的分步代码就可以看出来，我们创建一个循环将整个排序嵌套，就可以完成交换式的希尔排序
        for (int grp = arr.length/2; grp >0 ; grp/=2) {
            for (int i = grp; i < arr.length; i++) {
                //可以把i=5 i=6代入进去就能理解了 这个j-5是为了退出这一次内循环，进行下一次分组
                for (int j = i - grp; j >= 0; j -= grp) {
                    //即相隔距离为 5 的元素组成一组,所以这里要j+5，j+x,x是看分成多少组
                    if (arr[j] > arr[j + grp]) {
                        tmp = arr[j + grp];//小
                        arr[j + grp] = arr[j];//后面的位置是大的位置
                        arr[j] = tmp;//小的位置是小的
                    }
                }
            }
        }
    //测试代码
    /**
     int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*800000);
        }
        String patter = "YYYY-MM-dd HH:mm:ss";
        DateFormat dateFormat = new SimpleDateFormat(patter);
        Date date1 = new Date();
        System.out.println(dateFormat.format(date1));
        Sort(arr);
        Date date2 = new Date();
        System.out.println(dateFormat.format(date2));
        **/

希尔排序（交换式）会比较慢

耗时4s排完8w的数据

建议希尔排序自己debug看一遍就会明白了

优化代码移动式

public static void ShellSort2(int[] arr){
    for (int gar = arr.length; gar >0 ; gar/=2) {
        //从第gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gar; i < arr.length ; i++) {
            int tmp = arr[i];
            int j= i;
            if (arr[i] < arr[j-gar]){
                while(j-gar >=0 && tmp < arr[j-gar]){
                    arr[j] = arr[j-gar];//移动
                    j-=gar;
                }
                arr[j] = tmp;//这里减去了相隔的距离
        }
    }
        //还是建议debug自己观看

移动式排800w的数据需要2s。

快速排序

快速排序法介绍

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

快速排序法示意图

快速排序图解+思路

分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（原因看后面解释）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换

交换之后的序列如下：

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：

3 1 2 5 4 6 9 7 10 8

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

接下来就是重复找基点，按照之前的排序进行就可以将整个数字

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        quick(arr,  0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }


    public static void quick(int[] arr, int left, int right) {
        //如果左边大于右边的话就是不合法的就直接返还
        if (left > right) {
            return;
        }
        //我们这里找基点一般从最左边开始
        //确定基准点
        int base = arr[left];
        //定义变量j指向最左边
        int i = left;
        //定义变量j指向最右边
        int j = right;
        //当j和i相等的时候就跳出循环
        while (j != i) {
            //先由i从右往左找到比基数小的，找到了就停下没有找到就继续找,这里必须要让j先移动，如果先让i移动的话
            while (arr[j] >= base && j < i) {
                //如果找不到比基数小的数那么就，j就继续移动
                j--;
            }
            //这里是找比基数大的，如果没有找到那么i就向前移动，找到了就停下
            while (arr[i] <= base && j < i) {
                i++;//从左往有检索
            }
            //交换两个数字
            int temp = arr[j];//这个是比基数小的数，先用变量保存下来，他现在是在左边
            arr[j] = arr[i];//arr[i]这个比基数大的数。现在在左边，要把他移动到右边去，所以就j的位置就变成比基点大的数
            arr[i] = temp;//i的位置就变成小的数
        }
        //当j,i相等的时候就，上面的while就会跳出循环，如果不成立那么那个while就会继续执行
        arr[left] = arr[j];//把相遇的元素赋值给基数的位置
        arr[j] = base;
        //递归来排左边的位置
        quick(arr,left,j-1);
        //递归排右边的位置
        quick(arr,i+1,right);
    }
}

快速排序为什么要从基准数位置的另一侧先开始查找

原因：从基准数位置的另一侧先开始查找，可以保证在两侧“探兵”相遇时，新基准值不会大于旧基准值(默认规则是升序排列)。

以 6 1 2 7 9为例

i先走走到i = 3 的时候满足了比基点大这一个准则，所以这个while循环就会退出进入到下一个循环

当 j 走到7的时候，前面那个条件是满足的但是他已经不能满足j> i 这个条件所以他就会在这里进行交换，但是这个时候的顺序7 1 2 6 9

所以在于当我们先从在边开始时，那么 i 所停留的那个位置肯定是大于基数6的，为了满足 i

所以这就是为什么要先从基点的另外一侧开始查找。

快速排序排800w的数据1s不到就能排完

归并排序

归并排序介绍

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

归并排序的思想

归并排序思想示意图2-合并相邻有序子序列（最后一个阶段）

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

这里是分别有两个指针，i，j。先比较j和i对应的值，如果 j 的值比i小那么 i 就放到临时数组中，j就向前移动一位，如果 i 的值比 j 小

那么就 i 对应的值放到临时数组当中去，如果j中已经没有数据了那么就按照顺序将i中后面的数据依次放进去。

完整代码实现

public class MargetSort {
    public static void main(String[] args) {
        int [] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random()*8000000);
        }
        int[] temp = new int[arr.length];
        long time1 = System.currentTimeMillis();
        mergeSort(arr,0, arr.length-1,temp);
        System.out.println(System.currentTimeMillis() - time1+"ms");
    }
    //分+合并的方法
    public static 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);
        }
    }

    /**
     * 
     * @param arr 排序的原始数组
     * @param left 数组的开始索引
     * @param mid 中间位置的索引
     * @param right 左边的索引
     * @param temp 临时的数组
     */
    public static void merge(int[] arr,int left,int  mid,int right,int[] temp){
        int i = left;//先初始化下标i
        int j = mid + 1;//这是第二部分数组的下标
        int t = 0;//临时数组的下标
        //1)先把左右两边（有序的数组）的数据按照规则填充到temp数组
        //直到左右两边都为有序序列，有一边处理完为止
        while (i <= mid && j <= right){
            //说明数组还没有排序完成
            if (arr[i] >= arr[j]){
                //当右边的数大于左边的数的时候，就把左边比右边小的数加入到临时数组中
                temp[t] = arr[j];
                t+=1;
                j+=1;
            }else {
                temp[t] = arr[i];
                t++;
                i+=1;
            }
        }
        //2)将剩下没有添加完的数据按顺序添加到temp中去
        while (i<=mid){
            temp[t] = arr[i];
            i++;
            t++;

        }
        while (j <= right){
            temp[t] = arr[j];
            t++;
            j++;
        }

        //3)将所以排好序的数组一次复制回原数组
        //注意，并不是拷贝所有
        int tempLeft = left;//临时的变量
        while (tempLeft <= right){
            arr[tempLeft] = temp[t];
            tempLeft+=1;
            t+=1;
        }
    }
}

归并排序同等800w数据他用了1064ms

基数排序

基数排序介绍

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

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

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

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

基数排序基本思想

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

基数排序图解

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。

数组的初始状态
arr = {53, 3, 542, 748, 14, 214}

说明：因为有个位数含10位数，所以就要准备10个桶来存放数字

第1轮排序：

将每个元素的个位数取出，然后看这个数应该放在哪个对应的桶（一个一维数组，在代码中用一个二维数组来表示10个桶）
按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）

第2轮排序：

将每个元素的十位数取出，然后看这个数应该放在哪个对应的桶(一个一维数组)
按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)

第3轮排序:

将每个元素百位数取出，然后看这个数应该放在哪个对应的桶(一个一维数组)
按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)

基数排序逐步代码

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }
    //基数排序方法
    public static void radixSort(int[] arr){
        //定义一个二维数组，表示10个桶，每一个桶就是一个二维数 组
        //说明
        //1.二维数组包含了10个一维数组
        //2.为了防止在放入数的时候，数据溢出，则每一个一维数组的长度就为arr.length
        //3.基数排序就是典型的空间换时间的算法。
        int[][] bucket = new int[10][arr.length];
        //创建一个一维数组来存放每一个桶中到底放了多少个元素
        //分别记录了10个桶中元素的个数
        int[] ElementCount = new int[10];
        //将要排序的数组中的数按个位数放入到桶中

        //第一轮(针对每一个元素的个位进行排序处理)
        for (int i = 0; i < arr.length; i++) {
            //获取数组中每一个元素的个位数，按照个位数对应的数字放入到对应桶中
            int digit = arr[i] /1 % 10;
            //说明：
            // ElementCount[digit]是初始的数组，没有加入数据之前默认每一个位置为0
            //所以ElementCount[digit]这个时候就为0，第一次加入进来数放在第一位
            //举个例子，如果第一次余了1，那么bucketCounts【1】的值是0，因此之前没有其他数余1,在一维数组（即第一个桶）的首位就会放一个数
            //然后ElementCount[digit]++，表示了第一个桶中，元素的个数为1
            bucket[digit][ElementCount[digit]] = arr[i];
            ElementCount[digit]++;
        }
        //依次将桶中的元素取出然后放入原数组中
        int index = 0;
        for (int k = 0; k < ElementCount.length; k++) {
            //遍历每一个桶查看桶的元素,先判断是否有元素，如果放了值就不是0
            if (ElementCount[k] != 0){
                //ElementCount[k]这里得到的时候桶中元素的个数通过ElementCount记录的，所以j只要遍历小于桶中数量就行
                for (int j = 0; j < ElementCount[k]; j++) {
                    arr[index] = bucket[k][j];
                    index++;
                }
                //每次取出来过后要将之前的用来计数每一个桶中的元素的数量进行一个清0！！！！
                ElementCount[k] = 0;
            }
        }
        System.out.println(Arrays.toString(arr));

        //==================================第二轮的处理==============================
        for (int i = 0; i < arr.length; i++) {
            //获取数组中每一个元素的十位数，按照十位数对应的数字放入到对应桶中
            int digit = arr[i] /10 % 10; //-> 748/10 = 74%10 = 4
            //说明：
            // ElementCount[digit]是初始的数组，没有加入数据之前默认每一个位置为0
            //所以ElementCount[digit]这个时候就为0，第一次加入进来数放在第一位
            //举个例子，如果第一次余了1，那么bucketCounts【1】的值是0，因此之前没有其他数余1,在一维数组（即第一个桶）的首位就会放一个数
            //然后ElementCount[digit]++，表示了第一个桶中，元素的个数为1
            bucket[digit][ElementCount[digit]] = arr[i];
            ElementCount[digit]++;
        }
        //依次将桶中的元素取出然后放入原数组中
        index = 0;
        for (int k = 0; k < ElementCount.length; k++) {
            //遍历每一个桶查看桶的元素,先判断是否有元素，如果放了值就不是0
            if (ElementCount[k] != 0){
                //ElementCount[k]这里得到的时候桶中元素的个数通过ElementCount记录的，所以j只要遍历小于桶中数量就行
                for (int j = 0; j < ElementCount[k]; j++) {
                    arr[index] = bucket[k][j];
                    index++;
                }
            }
            ElementCount[k] = 0;
        }
        System.out.println(Arrays.toString(arr));

        //=============================第三轮处理==============================
        for (int i = 0; i < arr.length; i++) {
            //获取数组中每一个元素的百位数，按照百位数对应的数字放入到对应桶中
            int digit = arr[i] /100 % 10; //-> 748/10 = 74%10 = 4
            //说明：
            // ElementCount[digit]是初始的数组，没有加入数据之前默认每一个位置为0
            //所以ElementCount[digit]这个时候就为0，第一次加入进来数放在第一位
            //举个例子，如果第一次余了1，那么bucketCounts【1】的值是0，因此之前没有其他数余1,在一维数组（即第一个桶）的首位就会放一个数
            //然后ElementCount[digit]++，表示了第一个桶中，元素的个数为1
            bucket[digit][ElementCount[digit]] = arr[i];
            ElementCount[digit]++;
        }
        //依次将桶中的元素取出然后放入原数组中
        index = 0;
        for (int k = 0; k < ElementCount.length; k++) {
            //遍历每一个桶查看桶的元素,先判断是否有元素，如果放了值就不是0
            if (ElementCount[k] != 0){
                //ElementCount[k]这里得到的时候桶中元素的个数通过ElementCount记录的，所以j只要遍历小于桶中数量就行
                for (int j = 0; j < ElementCount[k]; j++) {
                    arr[index] = bucket[k][j];
                    index++;
                }
            }
            ElementCount[k] = 0;
        }
        System.out.println(Arrays.toString(arr));

    }
}

完整代码

public class RadixSort {
    public static void main(String[] args) {
        //如果是8kw的数据
        //80000000 * 11 * 4 /1024/1024/1024 = 3.3g,直接导致堆内存爆炸
        int [] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random()*80000000);
        }
        int[] temp = new int[arr.length];
        long time1 = System.currentTimeMillis();
        radixSort(arr);
        System.out.println(System.currentTimeMillis() - time1+"ms");

    }
    //基数排序方法
    public static void radixSort(int[] arr){

        //根据规律我们就能开始处理
        //我们先找到这个数组中的最大位数，这决定了我们将要轮几次将这个数组排序完成
        //我们先假定第一个是最大的
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]){
                max = arr[i];
            }
        }
        //拿到max值的位数
        int length = (max + "").length();
        //定义一个二维数组，表示10个桶，每一个桶就是一个二维数组
        //说明
        //1.二维数组包含了10个一维数组
        //2.为了防止在放入数的时候，数据溢出，则每一个一位数组的长度就为arr.length
        //3.基数排序就是典型的空间换时间的算法。
        int[][] bucket = new int[10][arr.length];
        //创建一个一维数组来存放每一个桶中到底放了多少个元素
        //分别记录了10个桶中元素的个数
        int[] ElementCount = new int[10];
        //将要排序的数组中的数按个位数放入到桶中

        //通过一个for循环来执行，现在改第一轮的代码来实现
        for (int m = 0,n = 1; m < length ; m++,n*=10) {
            for (int i = 0; i < arr.length; i++) {
                //获取数组中每一个元素的对应的数位的值，按照对应的数字放入到对应桶中
                int digit = arr[i] / n % 10;
                //说明：
                // ElementCount[digit]是初始的数组，没有加入数据之前默认每一个位置为0
                //所以ElementCount[digit]这个时候就为0，第一次加入进来数放在第一位
                //举个例子，如果第一次余了1，那么bucketCounts【1】的值是0，因此之前没有其他数余1,在一维数组（即第一个桶）的首位就会放一个数
                //然后ElementCount[digit]++，表示了第一个桶中，元素的个数为1
                bucket[digit][ElementCount[digit]] = arr[i];
                ElementCount[digit]++;
            }
            //依次将桶中的元素取出然后放入原数组中
            int index = 0;
            for (int k = 0; k < ElementCount.length; k++) {
                //遍历每一个桶查看桶的元素,先判断是否有元素，如果放了值就不是0
                if (ElementCount[k] != 0){
                    //ElementCount[k]这里得到的时候桶中元素的个数通过ElementCount记录的，所以j只要遍历小于桶中数量就行
                    for (int j = 0; j < ElementCount[k]; j++) {
                        arr[index] = bucket[k][j];
                        index++;
                    }
                    //每次取出来过后要将之前的用来计数每一个桶中的元素的数量进行一个清0！！！！
                    ElementCount[k] = 0;
                }
            }

        }

堆排序（先看完二叉树）

堆排序介绍

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆大顶堆举例说明：

大顶堆特点：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点，i从0开始编号

小顶堆图示：

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点，i从0开始编号
一般升序采用大顶堆，降序采用小顶堆

堆排序的基本思想

堆排序的基本思想是:

将待排序序列构造成一个大顶堆（这个过程是反复进行的）
此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1 个元素重新构造成-一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。

图解

要求:给你一个数组{4,6,8,5,9}, 要求使用堆排序法，将数组升序排序。

.假设给定无序序列结构如下
此时我们从最后一个非叶子节点开始(叶结点自然不用调整,第一个非叶子结点arr.length/2-1=5/2-1=1 ,也就是下面的6结点) , 从左至右,从下至上进行调整。

找到6后，先让他的左右两个节点比较发现9比5大，不移动，然后在比较6，9，9比6大，就把9放到6的位置。

3.找到第二个非叶节点4,由于[4,9,8]中9元素最大, 4和9交换。

4.这时，交换导致了子根[4,5,6]结构混乱,继续调整, [4,5,6]中6最大,交换4和6。（这里还比较了左右节点谁比较大）

这个时候我们就将一个无序的序列构造成了一个大顶堆。

步骤二：

这个时候就要将末尾和第一个位置的元素进行交换，使末尾的元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换 ，得到第二大元素。如此反复进行交换、重建、交换。

1.将堆顶元素9和末尾元素4进行交换

2.重新调整结构,使其继续满足大顶堆定义

3.再将堆顶元素8与末尾元素5进行交换,得到第二大元素8

4.后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

最终我们得到了一个有序的序列。

完整代码

public class HeapSort {
    public static void main(String[] args) {
        int [] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random()*8000000);
        }
        long time1 = System.currentTimeMillis();
        heapSort(arr);
        System.out.println(System.currentTimeMillis() - time1+"ms");
    }
    public static void heapSort(int[] arr){
        int tem = 0;
        //分部完成
//        adjustHeap(arr,1,arr.length);
//        System.out.println("第一次调整"+ Arrays.toString(arr));//4,9,8,5,6
//        adjustHeap(arr,0,arr.length);//这里还没有找到最大值就不用减1
//        System.out.println("第二次调整"+ Arrays.toString(arr));
        //终极代码
        for (int i = arr.length / 2 - 1; i >= 0 ; i--) {
            adjustHeap(arr,i,arr.length);
        }
        /**
         * 将堆顶的元素与末尾的元素进行交换，将最大值“沉”到数组的末端，即数组长度减1
         * 重新调整结构使其满足大顶堆的结构，重复以上操作
         */
        for (int i = arr.length -1; i >0  ; i--) {
            tem = arr[i];
            arr[i] = arr[0];
            arr[0] = tem;
            adjustHeap(arr,0,i);//这里填0，是应为除开根节点以下的节点已经排序为大顶堆的样子了所以不用在调整，只需调整根节点即可，因为我们是从下往上调整，所以就填0.
        }

    }

    /**
     * 将一个数组（二叉树）调整成一个大根堆
     * 功能：完成将以i对应的非叶子结点的树调整成大顶堆
     * 举例int arr[]={4,6,8,5,9};=>i=1=> adjustHeap=>得到{4,9,8,5,6}
     * 如果我们再次调用adjustHeap 传入的是i=0=>得到{4,9,8,5,6}=> {9,6,8,5,4}
     *
     * @param arr    传入一个数组
     * @param i      表示第几个非子叶节点
     * @param length 表示数组的长度，这个长度是逐渐减少的应为找到一个最大的数之后，就不在管他，长度对应减一
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int tem = arr[i];//表示对应的非叶子节点的值
        for (int k = i * 2 + 1; k < length; k = i * 2 + 1) {
            //这里的k是对应非子叶节点的左子节点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;//非叶子节点的左右节点进行比较如果右节点大于左节点，那么k就要向右移动一位
            }
            if (tem < arr[k]){
                arr[i] = arr[k];//如果非叶子节点的左右节点比他大，那么就将大的值与其互换
                i = k;//然后将k的值赋给i
            }else {
                break;
            }
        }
        arr[i] = tem;//这里就是进行交换
    }
}

查找算法

查找算法介绍

在java中，我们常用的查找有四种:

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

线性查找

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

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

public class SeqSearch {
    public static void main(String[] args) {
        int[] arr = {11,12,11,13,14,15,17,20};
        System.out.println(seqSearch(arr, 11));
    }

    public static int seqSearch(int[] arr,int value){
        for (int i = 0; i < arr.length; i++) {
           if (value == arr[i]){
               return i;
           }

        }
        return -1;
    }


}

二分查找

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

二分查找思路

首先确定该数组的中间的下标
mid = (left + right) / 2
然后让需要查找的数 findVal 和 arr[mid] 比较
findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
findVal == arr[mid] 说明找到，就返回

什么时候我们需要结束递归.

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

未完善代码

public class binarySearch {
    public static void main(String[] args) {
        int[] arr = {1,8, 10, 89, 1000, 1234};
        System.out.println(TowSearch(arr, 0, arr.length - 1, 1000));

    }

    /**
     * 注意二分查找要求的数组是有序的
     * @param arr 要搜寻的数组
     * @param left 左边的指针
     * @param right 右边的指针
     * @param value 需要查找的值
     */
    public static int TowSearch(int[] arr,int left,int right,int value){
        if (left > right){
            return -1;
        }
        int mid = (left+right)/2;
        if (value > arr[mid]){
            //如果查找的值大于了中间的数那么就要向右进行递归
            return TowSearch(arr,mid+1,right,value);
        }else if (value < arr[mid]){
            //如果查找的值大于了中间的数那么就要向左进行递归
            return TowSearch(arr,left,mid-1,value);
        }else {
            return mid;
        }
    }

完善代码

public static List<Integer> TowSearch2(int[] arr, int left, int right, int value){
        if (left > right){
            return new ArrayList<>();
        }
        int mid = (left+right)/2;
        if (value > arr[mid]){
            //如果查找的值大于了中间的数那么就要向右进行递归
            return TowSearch2(arr,mid+1,right,value);
        }else if (value < arr[mid]){
            //如果查找的值大于了中间的数那么就要向左进行递归
            return TowSearch2(arr,left,mid-1,value);
        }else {
//            1.首先找到了那个mid后不用急着返回
//            2.先继续扫描mid的左右两边，然后用一个ArrayList的集合将所有复合条件的索引装起来然后返回
            //先创建一个ArrayList集合
            List<Integer> list = new ArrayList<>();
            int temp = mid+1;
            while (true){
                //如果找到了后就先向mid的右边扫描，看看是否有符合的数

                if (temp > right || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp+=1;
        }
            list.add(mid);
            temp = mid-1;
            while (true){
                //如果找到了后就先向mid的左边扫描，看看是否有符合的数
                if (temp < 0 || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp-=1;
            }
            return list;
    }
    }

插值查找（二分查找的一个改进）

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

int mid = low + (high - low) (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引*/

对应前面的代码公式：int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

插值查找的特点

（1）查找的序列必须有序

（2）对于数据量大的以及关键字分布均匀的有序序列来说，插值查找的速度较快。

（3）对于分布不均匀的有序序列来说，该算法不一定比二分查找要好。

如果对插值查找的公式推导感兴趣的话可以去这里看看

https://www.cnblogs.com/euler0525/p/16533592.html

完整代码

public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = {1,8, 10,89, 1000,1000,1234};
//        System.out.println(TowSearch(arr, 0, arr.length - 1, 1000));
        System.out.println(insetValueSearch(arr, 0, arr.length - 1, 1000));
    }

    public static int insetValueSearch(int[] arr, int left, int right, int value) {
        //先判断
        //value < arr[0] || value > arr[arr.length -1],提高效率，并且如果输入的数太大防止数组越界
        if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
        if (value > arr[mid]) {
            return insetValueSearch(arr, mid + 1, right, value);
        } else if (value < arr[mid]) {
            return insetValueSearch(arr, left, mid - 1, value);
        }else {
            return mid;
        }
    }
}

斐波那契(黄金分割法)查找

斐波那契(黄金分割法)原理:

斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列),如下图所示

对F(k-1)-1的理解：

首先由斐波那契数列的特性, f(k)=f(k-1)+f(k-2), 规定待排序列长度为f[k]-1是为了格式上的统一，以方便递归或者循环程序的编写

因为数组的下标都是从0开始的。

mid = low+F(k - 1) - 1的解释：

表中的数据是f[k]-1个，使用mid值进行分割又用掉一个，那么剩下f[k]-2个。正好分给两个子序列，每个子序列的个数分别是f[k-1]-1与f[k-2]-1个，格式上与之前是统一的。

在后续的分割区间并查找比对时, 当查找值key < temp[mid]时, k -= 1, 当查找值key > temp[mid]时, k-=2; 为什么会这样呢?

因为当我们计算完黄金分割点的时候，用黄金分割点的下标对应的值进行判断

如果key < temp[mid] 那么表明我们要查找的值在整个数组的左边那么就要到F[k-1] -1 这个序列里面找这个时候k-=1
如果key > temp[mid] 那么表明我们要查找的值在整个数组的右边那么就要到F[k-2] -1 这个序列里面找这个时候k-=2

完整代码实现

public class FibonacciSearch {

    public static int maxSize = 20;
    public static void main(String[] args) {
        int [] arr = {1,8, 10, 89, 1000, 1234};
        
        System.out.println("index=" + fibSearch(arr, 189));// 0
        
    }
    //因为后面我们mid=low+F(k-1)-1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列
    //非递归方法得到一个斐波那契数列
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
    
    //编写斐波那契查找算法
    //使用非递归的方式编写算法
    /**
     * 
     * @param a  数组
     * @param key 我们需要查找的关键码(值)
     * @return 返回对应的下标，如果没有-1
     */
    public static int fibSearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        int k = 0; //表示斐波那契分割数值的下标
        int mid = 0; //存放mid值
        int f[] = fib(); //获取到斐波那契数列
        //获取到斐波那契分割数值的下标，即新数组的长度
        while(high > f[k] - 1) {
            k++;
        }
        //因为 f[k] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]
        //不足的部分会使用0填充
        int[] temp = Arrays.copyOf(a, f[k]);
        //实际上需求使用a数组最后的数填充 temp
        //举例:
        //temp = {1,8, 10, 89, 1000, 1234, 0, 0}  => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
        for(int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        
        // 使用while来循环处理，找到我们的数 key
        while (low <= high) { // 只要这个条件满足，就可以找
            mid = low + f[k - 1] - 1;
            if(key < temp[mid]) { //我们应该继续向数组的前面查找(左边)
                high = mid - 1;
                //为甚是 k--
                //说明
                //1. 全部元素 = 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                //即 在 f[k-1] 的前面继续查找 k--
                //即下次循环 mid = f[k-1-1]-1
                k--;
            } else if ( key > temp[mid]) { // 我们应该继续向数组的后面查找(右边)
                low = mid + 1;
                //为什么是k -=2
                //说明
                //1. 全部元素 = 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
                //4. 即在f[k-2] 的前面进行查找 k -=2
                //5. 即下次循环 mid = f[k - 1 - 2] - 1
                k -= 2;
            } else { //找到
                //需要确定，返回的是哪个下标
                if(mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

如果还是不明白可以去看看这篇文章https://www.cnblogs.com/sha-Pao-Zi/p/16315064.html，注意这个查找也需要数列是有序的。

哈希表

哈希表的基本介绍

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

哈希表(散列)-应用实例

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的id时,要求查找到该员工的所有信息.

使用哈希表的具体思路分析

HashTable管理着每一个EmpLinkedList[]数字中的每一个对象，每一个EmpLinkedList又带有每一个员工的具体信息

完整代码

public class HashTabDemo {


    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);
        //写一个简单的菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add:  添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("del:删除雇员");
            System.out.println("exit: 退出系统");


            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建 雇员
                    emp emp = new emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("输入id");
                    id = scanner.nextInt();
                    hashTab.findByNo(id);
                    break;
                case "del":
                    System.out.println("输入id");
                    id = scanner.nextInt();
                    hashTab.delById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }

}


class HashTab {
    private EmpLinkedList[] empLinkedArray;
    private int size;

    public HashTab(int size) {
        this.size = size;
        empLinkedArray = new EmpLinkedList[size];
        //数组里面的对象没有初始化全部都是为null，这个时候就要初始化,添加EmpLinkedList对象
        for (int i = 0; i < size; i++) {
            empLinkedArray[i] = new EmpLinkedList();
        }
    }


    public void add(emp emp) {//添加员工
        empLinkedArray[HsFUN(emp.id)].add(emp);
    }

    public void list() {
        //展示每一个表的员工的信息
        for (int i = 0; i < empLinkedArray.length; i++) {
            empLinkedArray[i].list(i + 1);
        }
    }

    //写一个散列函数来计算每一个员工应该放到hash表中的数组链表的那个位置，这里就用取模法
    public int HsFUN(int no) {
        return no % size;
    }

    public void findByNo(int no) {
        emp emp = empLinkedArray[HsFUN(no)].findEmpById(no);
        if (emp == null) {
            System.out.printf("没有找到员工号为%d的员工", no);
            System.out.println();
        } else {
            System.out.println(emp.name);
        }
    }

    public void delById(int no) {
        empLinkedArray[HsFUN(no)].delById(no);
    }
}


//创建一个员工对象
class emp {
    public int id;
    public String name;
    public emp next;//默认为null

    public emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

class EmpLinkedList {
    //头指针这里直接指向第一个员工
    private emp head;

    //添加员工到列表
    public void add(emp emp) {
        if (head == null) {
            head = emp;//如果链表的一个为空的话那么，头节点就是第一个员工
            return;//这里务必要加上return否则的话这个链表的下一个节点就指向了自己在遍历的时候就会不断死循环
        }
        //用一个辅助指针变量
        emp temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = emp;
    }


    public void list(int no) {
        if (head == null) {
            System.out.println("第" + no + "条链表为空");
            return;
        }
        System.out.print("第" + no + "条链表信息为:");
        emp curEmp = head;
        while (curEmp != null) {
            System.out.printf("===>员工的id%d,姓名%s\t", curEmp.id, curEmp.name);
            curEmp = curEmp.next;//后移
        }
        System.out.println();
    }

    public emp findEmpById(int id) {
        if (head == null) {
            return null;
        }
        //创建一个辅助指针
        emp cur = head;
        while (true) {
            if (cur.id == id) {
                break;
            }
            if (cur.next == null) {
                cur = null;//如果下一个是空就直接结束
                break;
            }
            cur = cur.next;//向后移动,找到了就直接返回
        }
        return cur;

    }

    public void delById(int no) {
        boolean flag = false;
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        emp temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            } else if (temp.next.id == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.printf("你要删除的员工号%d不存在", no);
        } else {
            temp.next = temp.next.next;
        }

    }
}

树

树的引入

数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

链式存储方式的分析

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。

缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)）

树存储方式的分析

能提高数据存储，读取的效率, 比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

树的定义

树（tree）是n（n>= 0）个节点的有限集，当n = 0 时，称为空树。在任意一个非空树中，有如下特点：

1.有且仅有一个特定的称为根的节点。

2.当n > 1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又，是一个树，并称根的子树。

树的示意图

树的常用术语

节点
根节点
父节点
子节点
叶子节点 (没有子节点的节点)
节点的权(节点值)
路径(从root节点找到该节点的路线)
层
子树
树的高度(最大层数)
森林 :多颗子树构成森林

二叉树

二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

二叉树的子节点分为左节点和右节点。

特殊的二叉树

满二叉树

如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。（所有分支节点都有两个孩子）

完全二叉树

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

(前n-1层为满的。

最后一层不满，但是最后一层从左往右是连续的。)

二叉树的遍历

对下列二叉树进行遍历

前序遍历: 先输出父节点，再遍历左子树和右子树
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

小结: 看输出父节点的顺序，就确定是前序，中序还是后序

完整代码

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1,"宋江");
        HeroNode node1= new HeroNode(2,"吴用");
        HeroNode node2 = new HeroNode(3,"卢俊义");
        HeroNode node3  = new HeroNode(4,"林冲");
        HeroNode node4  = new HeroNode(5,"关胜");
        //手动设置节点
        root.setLeft(node1);
        root.setRight(node2);
        node2.setRight(node3);
        node2.setLeft(node4);


class BinaryTree{
    private HeroNode root;
    

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder(){
        if (this.root !=null){
        this.root.preOrder();
    }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public void infixOrder(){
        if (this.root != null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }

    }
    public void postOrder(){
        if (this.root != null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }

    }

class HeroNode{
    private int id;
    private String name;
    private HeroNode left;//默认为空
    private HeroNode right;


    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    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;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    //前序遍历
    public void preOrder(){
        //先输出根节点
        System.out.println(this);
        //在输出左节点
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
    //中序遍历
    public void infixOrder(){
        //先输出左节点
        if (this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infixOrder();
        }
    }

    //后续遍历
    public void postOrder(){
        if (this.left != null){
            this.left.postOrder();
        }
        if (this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序查找
    public HeroNode preSearch(int no){
        //先判断当前节点
        if (this.id == no){
            return this;
        }
        HeroNode curs = null;
        //如果不相等就向左前序递归查找
        if (this.left != null){
            curs = this.left.preSearch(no);
        }
        if (curs != null){//说明左子树找到了
            return curs;
        }
        if (this.right != null){
           curs  =  this.right.preSearch(no);
        }
        return curs;
    }

二叉树查找

二叉树查找的思路：

前序查找：

先判断当前节点是否是要查找的目标。
如果相等就直接返回当前节点
如果不是就判断左节点，如果左节点不为空就按前序递归查找，如果找到就返回
如果为空那么就查询右节点，如果右节点不为空那么，则继续前序递归查找，这个时候不管找没有找到都直接返回。

中序查找：

先判断当前节点的左节点是否为空如果不为空就按左递归中序查找。
找到了就直接返回，如果没有找到就和当前节点比较，否者就进行右递归进行中序查找。
如果找到了就直接返回没有找到就直接返回null。

后序查找：

先判断当前节点的左节点是否为空，如果不为空就按左递归的后序查找。
如果找到就直接返回如果没有找到，就判断当前右节点是否为空，如果不为空按照右递归的后序查找，找到了就直接返回。
如果都没有找到就比较当前节点。

前中后序查找代码

//前序查找
    public HeroNode preSearch(int no){
        //先判断当前节点
        if (this.id == no){
            return this;
        }
        HeroNode curs = null;
        //如果不相等就向左前序递归查找
        if (this.left != null){
            curs = this.left.preSearch(no);
        }
        if (curs != null){//说明左子树找到了,找到了就直接返回，没有找到就判断右节点是否为空不为空就进行右递归，如果右递归都没有找到就直接返回null
            return curs;
        }
        if (this.right != null){
           curs  =  this.right.preSearch(no);
        }
        return curs;
    }

    //中序查找
    public HeroNode infixSearch(int no){
        //如果左边节点不为空就进行左递归中序查找
        HeroNode cur = null;
        if (this.left != null){
           cur =  this.left.infixSearch(no);
        }
        if (cur !=null){
            return cur;
        }
        if(this.id == no){
            return this;//和当前节点比较，如果相等就直接返回
        }
        if (this.right != null){
            cur = this.right.infixSearch(no);//左节点没有找到进行右递归的中序查找
        }
        return cur;//不管找没有找到都直接返回
    }

    //后序查找
    public HeroNode postSearch(int no){
        HeroNode cur = null;
        if (this.left !=null){
            cur = this.left.postSearch(no);//向左递归的中序查找
        }
        if (cur != null){
            return cur;//如果找到了就直接返回
        }

        if (this.right != null){
            cur = this.right.postSearch(no);//如果左递归没有找到就判断右节点是否为空，如果不为空就进行右递归的后序查找
        }

        if (this.id == no){
            return this;//如果是就返回，没有就直接返回null
        }
        return cur;
    }

删除节点

要求：

如果删除的节点是叶子节点，则删除该节点
如果删除的节点是非叶子节点，则删除该子树.
测试，删除掉 5号叶子节点和 3号子树.

思路：

首先我们先判断根节点的左右节点是否为为空，如果是那么就等价将二叉树置空

因为二叉树是单项的，所以我们是判断当前节点的子节点是否是需要删除的节点，而不能去判断当前这个节点是不是需要删除的节点
如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left = null 并且返回（结束递归删除）;
如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null;，并且就返回（结束递归删除）；
2，3都没有删除子节点，那么我们就需要向左子树进行递归删除
如果第四步也没有删除节点，则应当向右子树进行递归删除

完整代码

    public void del(int no){
        if (this.root != null){
            if (this.root.getId() == no){
                this.root = null;
            }else {
                this.root.del(no);
            }
        }else {
            System.out.println("节点为空，无法删除");
        }
    }
/**
     * 1. 因为二叉树是单项的，所以我们是判断当前节点的子节点是否是需要删除的节点，而不能去判断当前这个节点是不是需要删除的节点
     * 2. 如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left = null 并且返回（结束递归删除）;
     * 3. 如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null;，并且就返回（结束递归删除）；
     * 4. 2，3都没有删除子节点，那么我们就需要向左子树进行递归删除
     * 5. 如果第四步也没有删除节点，则应当向右子树进行递归删除
     * @param no 要删除的节点
     */
    public void del(int no){
        //如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left = null 并且返回（结束递归删除）;
         if (this.left !=null && this.left.id == no ){
             this.left = null;
             return;
         }
         //如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null;，并且就返回（结束递归删除）；
         if (this.right != null && this.right.id == no){
             this.left = null;
         }
         //2，3都没有删除子节点，那么我们就需要向左子树进行递归删除
         if (this.left != null ){
             this.left.del(no);
         }

        //如果第四步也没有删除节点，则应当向右子树进行递归删除
        if (this.right != null ){
            this.right.del(no);
        }
    }
//二叉树-删除节点,保留子叶节点
public void del2(int no){
        //如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left = null 并且返回（结束递归删除）;
        if (this.left !=null && this.left.id == no ){
                //先判断要删除节点的左节点是否为空，不为空那么删除当前节点后，他的左子节点直接挂上，如果右节点也不为空，那么右子节点就直接挂在，之前左节点上
                HeroNode temp = this.left;
                if (this.left.left != null){
                    this.left = temp.left;
                    if (temp.right != null){
                        this.right.right = temp.right;
                    }
                }else{
                    this.right = temp.right;
                }
            return;
        }
        //如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null;，并且就返回（结束递归删除）；
        if (this.right != null && this.right.id == no){
            //先判断要删除节点的左节点是否为空，不为空那么删除当前节点后，他的左子节点直接挂上，如果右节点也不为空，那么右子节点就直接挂在，之前左节点上
            HeroNode temp = this.right;
            if (this.right.left != null){
                this.right = temp.left;
                if (temp.right != null){
                    this.right.right = temp.right;
                }
            }else{
                this.right = temp.right;
            }
            return;
        }
        //2，3都没有删除子节点，那么我们就需要向左子树进行递归删除
        if (this.left != null ){
            this.left.del(no);
        }

        //如果第四步也没有删除节点，则应当向右子树进行递归删除
        if (this.right != null ){
            this.right.del(no);
        }
    }

顺序存储二叉树

基本说明：

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看示意图。

要求:
右图的二叉树的结点，要求以数组的方式来存放 arr : [ ]
要求在遍历数组 arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

顺序存储二叉树的特点:

顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为 2 * n + 1
第n个元素的右子节点为 2 * n + 2
第n个元素的父节点为 (n-1) / 2
n : 表示二叉树中的第几个元素(按0开始编号如图所示)

完整代码

public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.infixOrder();

    }


}



class ArrBinaryTree {
    private int[] arr;

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder() {
        preOrder(0);
    }

    public void infixOrder() {
        infixOrder(0);
    }


    /**
     *
     */

    public void preOrder(int index) {
        //先判断数组是否为空，或者数组是否为0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历");
        }
        System.out.println(arr[index]);
        //向左遍历
        if ((index * 2) + 1 < arr.length) {
            preOrder((index * 2) + 1);
        }
        //向右遍历
        if ((index * 2) + 2 < arr.length) {
            preOrder((index * 2) + 2);
        }
    }

    public void infixOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历");
        }
        if ((index * 2) + 1 < arr.length) {
            infixOrder((index * 2) + 1);
        }
        System.out.println(arr[index]);
        //向右遍历
        if ((index * 2) + 2 < arr.length) {
            infixOrder((index * 2) + 2);
        }
    }

    public void postOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历");
        }
        if ((index * 2) + 1 < arr.length) {
            infixOrder((index * 2) + 1);
        }
        //向右遍历
        if ((index * 2) + 2 < arr.length) {
            infixOrder((index * 2) + 2);
        }
        System.out.println(arr[index]);
    }
}

线索化二叉树

线索化二叉树引入

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树

当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
但是 6, 8, 10, 14 这几个节点的左右指针，并没有完全的利用上.
如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办?
解决方案-线索二叉树

线索二叉树介绍

n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

一个结点的前一个结点，称为前驱结点
一个结点的后一个结点，称为后继结点（通过观看他们的数组排序对应元素的前后的值就是他们前驱和后驱节点，前驱节点放到左节点，后驱是放到右节点）。

总结：

若当前节点左指针域非空时，保留原指针不变；若左指针域为空时，添加该节点在相应遍历序列中前驱节点地址。
若当前结点右指针域非空时，保留原指针不变；若右指针域为空时，添加该节点在相应遍历序列中后继节点地址。

这里要注意一下，我们怎么判断左/右指针域指向的是原指针还是前驱/后继节点?

线索化：中序线索化二叉树，就按中序遍历，遍历的过程中在当前节点的左或右空指针域中添加前驱或后继节点。为了保留遍历过程中访问节点的前驱与后继关系，需要设置一个前一节点变量 pre 始终指向刚访问过的节点。就是要创建指向当前节点的前驱节点的指针。

在进行递归线索话的时候pre保留前一个节点。

完整代码

public void ThreadedTree(HeroNode2 Node){
        //如果Node 为空就不进行线索化
        if (Node == null){
            return;
        }
        //先线索化左子树
        ThreadedTree(Node.getLeft());


        //{8, 3, 10, 1, 14, 6}
        //如果是按照8来理解的话
        //当前的节点指向8，他的前驱节点就是null也就是pre
        //线索化当前节点
        if (Node.getLeft() == null){
            //让当前的节点的左节点指向前驱节点
            Node.setLeft(pre);
            //修改当前节点的类型指向是指向前驱节点
            Node.setLeftType(1);
        }
        //处理后续节点
        if (pre != null && pre.getRight() == null){
            //让前驱节点的右指针指向当前节点
            pre.setRight(Node);//相当于这里前驱节点pre从null --> 变为了8，这时的Node递归到了3的位置因为8的后驱是3所以这时8的右节点就指向Node(3)
            pre.setRightType(1);
        }
        //这里就要把递归前的pre指向8,如果把这个写在前面就会闭环
        pre = Node;
        //在线索化右子树
        ThreadedTree(Node.getRight());
    }

中序遍历线索二叉树

public void ThreadInfixOrder(){
        HeroNode2 heroNode2 = root;
        while (heroNode2 != null){
            //通过循环找到当前LeftType == 1 的节点，8
            //后面随着遍历而变化，因为当leftType == 1 时，说明该节点是按照线索化的
            //处理后序节点
            while (heroNode2.getLeftType() ==0){
                heroNode2 = heroNode2.getLeft();
            }
            System.out.println(heroNode2);
            while (heroNode2.getRightType() == 1){
               heroNode2 =heroNode2.getRight() ;
               System.out.println(heroNode2);
            }
            //这里就要替换成下一个节点
            heroNode2 = heroNode2.getRight();
        }
    }

前序线索二叉树

线索化：和中序线索化实现一样(把中序遍历改为先序遍历)。
因为遍历的顺序不一样，所以需要注意的先序和中序有个地方不一样，先序我们要判断是否是左子树/右子树在进行递归，不然会出现死递归。

判断是否是左子树(即不是前驱节点)：先序的遍历顺序是"根左右"，在对"左"节点进行遍历的时候当"左"节点没有左子树时，“左"节点的前驱节点就设置为"根"节点，此时在遍历”左“节点的"左"节点，就又会遍历"根节点”，就会形成死循环。

完整代码

public void PreThreadedTree(HeroNode2 Node){
        //如果Node 为空就不进行线索化
        if (Node == null){
            return;
        }
        //先线索化当前节点
        if (Node.getLeft() == null){
            Node.setLeft(pre);
            Node.setLeftType(1);
        }

        if (pre != null && pre.getRight() == null){
            pre.setRight(Node);
            pre.setRightType(1);
        }
        pre = Node;
        //线索化左节点,先序我们要判断是否是左子树/右子树在进行递归，不然会出现死递归
        //判断是否是左子树(即不是前驱节点)：先序的遍历顺序是"根左右"，在对"左"节点进行遍历的时候当"左"节点没有左子树时，“左"节点的前驱节点就设置为"根"节点，此时在遍历”左“节点的"左"节点，就又会遍历"根节点”，就会形成死循环。
        //
        if (Node.getLeftType() == 0){
        PreThreadedTree(Node.getLeft());
        }
        //线索化右节点
        if (Node.getRightType() == 0){
        PreThreadedTree(Node.getRight());
    }
    }
//遍历前序线索化二叉树
public void PreThreadedTreeOrder(){
        HeroNode2 heroNode2 = root;
        while (heroNode2 != null) {
            while (heroNode2.getLeftType() == 0){
                System.out.println(heroNode2);
                heroNode2 = heroNode2.getLeft();
            }
            System.out.println(heroNode2);
            while (heroNode2.getRightType() == 1){
                heroNode2 = heroNode2.getRight();
                System.out.println(heroNode2);
            }
            heroNode2 = heroNode2.getRight();
        }
    }

赫夫曼树（二叉树的一种）

基本介绍

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

赫夫曼树几个重要概念和举例说明

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
WPL最小的就是赫夫曼树

构建赫夫曼树的思路图解

给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树

构成赫夫曼树的步骤：

从小到大进行排序，每一个数据都能看作一个节点，每一个节点都能看作一颗最简单的二叉树，并且数据的大小作为他的权值
取出根节点最小的两颗二叉树
组成一颗新的二叉树，该新的二叉树的权值是前面两颗二叉树根节点权值的和
将新的二叉树的权值又与之前的数列进行排序不断重复 1-2-3-4的步骤，直到每一个树都被处理，就能得到一颗赫夫曼树。

图解：

1.先排序，然后找到权值最小的两个二叉树，在将两个根节点的权相加得到一个新的二叉树，再将这个二叉树的权值进行重新排序

2.排序好在与6构成一个新的节点，10然后在进行排序。

重复以上步骤

完整代码

public class huffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node  = creatHuffmanTree(arr);
        preOrder(node);


    }

    public static void preOrder(Node root){
        if (root != null){
            root.pre();
        }else {
            System.out.println("树为空，不能遍历");
        }
    }

    public static Node creatHuffmanTree(int[] arr){
        //先遍历arr数组
        //将数组的值构成一个节点
        //将每一个节点放入到ArrayList中进行排序
        //通过Collections来进行排序
        ArrayList<Node> arrayList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            arrayList.add(new Node(arr[i]));
        }
        while (arrayList.size() > 1) 
            //当列表中只剩一个根节点的时候就说明已经构成了一颗树
            Collections.sort(arrayList);
            //从数组中取出最小的两个数
            //然后组成一个新的节点
            Node LeftNode = arrayList.get(0);
            Node RightNode = arrayList.get(1);
            //两个节点相加组成一个新的节点
            Node parent = new Node(LeftNode.value + RightNode.value);
            parent.left = LeftNode;
            parent.Right = RightNode;
            //删除已经处理过的节点
            arrayList.remove(LeftNode);
            arrayList.remove(RightNode);
            //加入新的节点
            arrayList.add(parent);
        }
        return arrayList.get(0);
    }


}



//创建Node节点类
//实现一个Comparable接口，方便进行大小比较
//同时让Node对象持续排序Collections
class Node implements Comparable<Node>{
    int value;
    Node left;
    Node Right;

    //前序遍历
    public void pre(){
        System.out.println(this);
        if (this.left != null){
            this.left.pre();
        }
        if (this.Right != null){
            this.Right.pre();
        }
    }

    public Node(int value) {
        this.value = value;
    }


    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}

二叉排序树(BST)

需求：

给你一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加。

二叉排序树的介绍

二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

二叉排序树创建和遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ，创建成对应的二叉排序树为 :

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }

        binarySortTree.infixOrder();
    }
}



class BinarySortTree{
    private Node root;

    public void infixOrder(){
        if (root == null){
            System.out.println("二叉树为空不能遍历");
        }else {
            this.root.infixOrder();
        }
    }

    public void add(Node node){
        // 如果是一颗空树，则直接赋给root即可.
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

}


//先创建一个二叉树
class Node{
    int value;
    Node leftNode;
    Node rightNode;
    //添加节点
    public void add(Node node){
        //先判断节点是否为空
        if (node == null){
            return;
        }
        if (node.value < this.value){
            //如果大于就就添加到左节点
            if (this.leftNode != null){
                //判断当前左节点是否有子节点如果有就继续向左递归添加
                this.leftNode.add(node);
            }else {
                //没有就直接添加
                this.leftNode = node;
            }
        }else {
            if (this.rightNode != null){
                this.rightNode.add(node);
            }else {
                this.rightNode = node;
            }
        }

    }
    //中序遍历
    public void infixOrder(){
        if (this.leftNode != null){
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode !=null){
            this.rightNode.infixOrder();
        }
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑:

删除叶子节点 (比如：2, 5, 9, 12)
删除只有一颗子树的节点 (比如：1)
删除有两颗子树的节点. (比如：7, 3，10 )

情况1思路：

先去找到要删除的节点， targetNode
找到targetNode的父节点parent
确定targetNode是parent的左节点还是右节点
根据前面的情况来删除

1. 左节点：parent.left = null;
2. 右节点: parent.right = null;

情况2思路：

先去找到要删除的节点， targetNode
找到targetNode的父节点parent
确定targetNode 的子结点是左子结点还是右子结点
targetNode 是 parent的右节点还是左节点

1. 如果targetNode有左节点并且targetNode是parent的左节点：parent.left = targetNode.left;
2. 如果 targetNode 是 parent 的右子节点：parent.right = targetNode.left;
3. 如果targetNode 有右子结点并且 targetNode 是 parent 的左子结点：parent.left = targetNode.right;
4. 如果 targetNode 是 parent 的右子节点：parent.right = targetNode.right

情况3思路:

需求先去找到要删除的结点 targetNode
找到targetNode 的父结点 parent
从targetNode 的右子树找到最小的结点
用一个临时变量，将最小结点的值保存 temp = 11
删除该最小结点
targetNode.value = temp

完整代码

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5,1,9,2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }


        binarySortTree.del(10);
        binarySortTree.del(1);
        binarySortTree.del(2);
        binarySortTree.del(3);
        binarySortTree.del(5);
        binarySortTree.del(6);
        binarySortTree.del(7);
        binarySortTree.del(12);
//        binarySortTree.del(9);
        binarySortTree.infixOrder();
    }
}


class BinarySortTree {
    private Node root;

    //查找要删除的节点
    public Node Search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchTargetNode(value);
        }
    }

    //查找要删除节点的父节点
    public Node SearchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }

    }

    //删除节点
    public void del(int value) {
        if (root == null) {
            return;
        } else {
            //找到要删除的节点
            Node target = Search(value);
            //判断叶子节点是否为空
            if (target == null) {
                return;
            }
            //如果找到的节点没有父节点就表明是根节点，就直接置空当前节点
            if (root.leftNode == null && root.rightNode == null) {
                root = null;
                return;
            }
            //如果不为空就找到他的父节点
            Node parent = SearchParent(value);
            //判断删除的节点是否为叶子节点
            if (target.leftNode == null && target.rightNode == null) {
                //在判断要删除的节点是父节点的左节点，还是右节点
                if (parent.leftNode != null && parent.leftNode.value == target.value) {
                    parent.leftNode = null;
                } else if (parent.rightNode != null && parent.rightNode.value == target.value) {
                    parent.rightNode = null;
                }
            }else if (target.leftNode != null && target.rightNode != null){
                //表明左右都有节点，为第三种情况
                target.value  = delGetMinValue(target.rightNode);
            }else {
                //表示只有一个左节点或者是右节点
                if (target.leftNode !=null){ //表明要删除的节点有左节点
                    if (parent !=null){//这里还要判断一下parent是否为空，否则就会报空指针异常
                   //在判断是删除的节点是父节点的左边还是右边
                    if (parent.leftNode.value == target.value){
                        parent.leftNode = target.leftNode;
                    }else {
                        parent.rightNode = target.leftNode;
                    }}else {
                        root = target.leftNode;
                    }
                }else {
                    //这里就表明只有右节点
                    if (parent != null){
                    if (parent.leftNode.value == target.value){
                        parent.leftNode = target.rightNode;
                    }else {
                        parent.rightNode = target.rightNode;
                    }
                }else {
                        root = target.rightNode;
                    }
                }
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉树为空不能遍历");
        } else {
            this.root.infixOrder();
        }
    }

    public void add(Node node) {
        // 如果是一颗空树，则直接赋给root即可.
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    //向要删除的节点的右子节点找到最小的子节点，并且删除最小的节点,并且返回最小节点的值
    public int delGetMinValue(Node node){
        //用一个临时变量来接受找的那个节点
        Node tem = node;//应为后面要传入一个目标节点的右节点所以这里向左查找
        while (tem.leftNode !=null){
            tem = tem.leftNode;
        }
       del(tem.value);
        return tem.value;
    }

}


//先创建一个二叉树
class Node {
    int value;
    Node leftNode;
    Node rightNode;

    //查找要删除结点的父结点

    /**
     * @param value 要找到的结点的值
     * @return 返回的是要删除的结点的父结点，如果没有就返回null
     */
    public Node searchParent(int value) {
        if ((this.leftNode != null && this.leftNode.value == value) || (this.rightNode != null && this.rightNode.value == value)) {
            return this;
        } else {
            if (this.leftNode != null && this.value > value) {
                return this.leftNode.searchParent(value);//向左子树递归查找
            } else if (this.rightNode != null && this.value < value) {
                return this.rightNode.searchParent(value);//向右子树递归查找
            } else {
                return null;// 没有找到父结点
            }
        }
    }




    /**
     * @param value 希望删除的结点的值
     * @return 如果找到返回该结点，否则返回null
     */
    public Node searchTargetNode(int value) {
        if (this.value == value) {
            return this;
        }
        if (this.value > value) {
            //如果左节点为空就直接返回null
            if (this.leftNode == null) {
                return null;
            }
            //如果当前值小于根节点，就向左递归查找
            return this.leftNode.searchTargetNode(value);
        } else {
            if (this.rightNode == null) {
                return null;
            }
            //如果当前值大于根节点，就向右递归查找
            return this.rightNode.searchTargetNode(value);
        }
    }


    //添加节点
    public void add(Node node) {
        //先判断节点是否为空
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            //如果大于就就添加到左节点
            if (this.leftNode != null) {
                //判断当前左节点是否有子节点如果有就继续向左递归添加
                this.leftNode.add(node);
            } else {
                //没有就直接添加
                this.leftNode = node;
            }
        } else {
            if (this.rightNode != null) {
                this.rightNode.add(node);
            } else {
                this.rightNode = node;
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }




    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

平衡二叉树AVL

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.

左边BST 存在的问题分析:

左子树全部为空，从形式上看，更像一个单链表.
插入速度没有影响
查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
解决方案-平衡二叉树(AVL)

平衡二叉树的介绍：

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。
具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

怎么处理-进行左旋转：

创建一个新的节点，新的节点的值为旧树的根节点的值
把新节点的左子树设置为旧树的左子树
newNode.left = left;
把新节点的右子树设置为旧树的右子树的左子树
newNode.right = right.left;
把旧树的根节点的值设置为旧树的右子树的值
value = right.value;
把当前节点（指的是当前的根节点）的右子树设置为旧树的右子树的右子树
right = right.right
当前节点的左子树设置为新节点left = newNode;

在旋转之前我们还要求出树的高，左子树的高和右子树的高度差，如果差值的绝对值大于1那么就要进行左旋转

求高度代码

//遍历左子树的高度
    public int leftHeight(){
        if (this.leftNode == null){
            return 0;
        }
        return this.leftNode.height();
    }
//遍历右子树的高度
    public int rightHeight(){
        if (this.rightNode == null){
            return 0;
        }
        return this.rightNode.height();
    }
    //以当前根节点为起始点的树的高度
    public int height(){
        return Math.max(this.leftNode == null ? 0: this.leftNode.height(),this.rightNode == null ? 0: this.rightNode.height())+1;
    }

左旋转代码

public void leftRotate(){
        //1. 创建一个新的节点，新的节点的值为旧树的根节点的值
        Node1 node1 = new Node1(this.value);
        //2. 把新节点的左子树设置为旧树的左子树
        node1.leftNode = this.leftNode;
        //把新节点的右子树设置为旧树的右子树的左子树
        node1.rightNode = this.rightNode.leftNode;
        //把旧树的根节点的值设置为旧树的右子树的值
        this.value = this.rightNode.value;
        //把当前节点（指的是当前的根节点）的右子树设置为旧树的右子树的右子树
        this.rightNode = this.rightNode.rightNode;
        //当前节点的左子树设置为新节点
        this.leftNode = node1;
    }

右旋转

当左子树的高度大于右子树的高度的时候，这个时候就要进行右旋转

创建一个新的节点，新的节点的值为旧树的根节点的值
把新节点的右子树设置为旧树的右子树
newNode.right = right;
把新节点的右子树设置为旧树的左子树的右子树
newNode.left = left.right;
把旧树的根节点的值设置为旧树的左子树的值
value = left.value;
把当前节点（指的是当前的根节点）的左子树设置为旧树的左子树的左子树
left = left.left
当前节点的右子树设置为新节点
right = newNode;

右旋转代码

public void rightRotate(){
        //1. 创建一个新的节点，新的节点的值为旧树的根节点的值
        Node1 node1 = new Node1(this.value);
        //2. 把新节点的右子树设置为旧树的左子树
        node1.rightNode = this.rightNode;
        //把新节点的左子树设置为旧树的左子树的右子树
        node1.leftNode = this.leftNode.rightNode;
        //把旧树的根节点的值设置为旧树的左子树的值
        this.value = this.leftNode.value;
        //把当前节点（指的是当前的根节点）的左子树设置为旧树的左子树的左子树
        this.leftNode = this.leftNode.leftNode;
        //当前节点的右子树设置为新节点
        this.rightNode = node1;

    }

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL树.

问题分析出来: 在满足右旋转条件时，要判断
(1)如果根节点的左子树的右子树高度大于左子树的左子树时：
(2)就是对当前根节点的左子树，先进行左旋转，
(3)然后，在对当前根节点进行右旋转即可
否则，直接对当前节点（根节点）进行右旋转.即可.

双旋转判断代码

//当添加完后就继续判断是否右子树高度是否大于左子树
        if (this.rightHeight() - this.leftHeight() > 1){
            //就进行左旋转
            //判断如果当前条件满足左旋转，在判断当前节点的右子树的左子树高度是否大于右子树的右子树，如果大于就先对当前节点的左子树进行右旋转
            if (this.rightNode!= null &&this.rightNode.leftHeight() > this.rightNode.rightHeight()){
                this.rightNode.rightRotate();
                leftRotate();
            }else {
                leftRotate();
            }
            return;
        }
        //右旋转
        if (this.leftHeight() - this.rightHeight() > 1){
            //判断如果当前条件满足左旋转，在判断当前节点的左子树的右子树高度是否大于左子树的左子树，如果大于先对当前节点的右子树进行左旋转
            if (this.leftNode!= null&&this.leftNode.leftHeight() < this.leftNode.rightHeight()){
                this.leftNode.leftRotate();
                rightRotate();
            }else {
                rightHeight();
            }
        }
    }

多路查找树

二叉树的问题分析

二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)，就存在如下问题:

问题1：在构建二叉树时，需要多次进行i/o操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时，速度有影响
问题2：节点海量，也会造成二叉树的高度很大，会降低操作速度.

多叉树

在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）
2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。

2-3树应用案例

将数列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成2-3树，并保证数据插入的大小顺序。(演示一下构建2-3树的过程.)

插入规则:

2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。
对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则

{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20}

除了23树，还有234树等，概念和23树类似，也是一种B树。如图:

B树的介绍

B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上，B-tree就是指的B树。

B树的说明:

B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子
结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.
搜索有可能在非叶子结点结束。
其搜索性能等价于在关键字全集内做一次二分查找

B+树的介绍

B+树的说明:

B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
不可能在非叶子结点命中
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
更适合文件索引系统
B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然.

**B树的介绍

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

B树的说明:

B树定义了非叶子结点关键字个数至少为(2/3)M（阶数表示了一个结点最多有多少个孩子结点，一般用字母 M 表示阶数。），即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
从第1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高。

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

java数据结构与算法（再版）（二）

链表（Linked List）

链表的介绍

单链表的创建思路

完整代码

考虑编号问题的思路

编号问题代码实现

修改信息

删除信息

单链表算法问题

查找单链表的倒数第k个【新浪面试题】

单链表从尾到头打印链表（百度的面试题）

合并两个有序链表

删除链表中的元素

环形链表

双向链表

双向链表完整代码

双向链表有序添加元素

约瑟夫问题分析

单向环形链表的实现

生成环形链表完整代码

小孩出圈问题

完整代码实现

栈

栈的引入

栈的介绍

栈的应用场景

栈的快速入门

使用栈完成计算一个表达式结果

思路

代码实现（在之前的栈新加一些功能）

前缀，中缀，后缀表达式

前缀表达式（波兰表达式）

中缀表达式

后缀表达式

逆波兰计算器

递归

递归的应用场景

递归的概念

递归的调用机制

递归的调用规则

递归能解决的问题

递归迷宫问题

代码实现

八皇后问题（回溯算法）

问题介绍

八皇后问题算法分析

完整代码加分析

排序算法

排序算法的介绍

冒泡排序

基本介绍

冒泡排序实例

代码实现（未优化版）

代码实现（优化版）

选择排序

基本介绍

选择排序思想

代码实现（未优化）

代码实现（优化）

插入排序

插入排序介绍

插入排序思想

插入排序图解