Java数据结构与算法-java数据结构与算法（三）-阿里云开发者社区

Java数据结构与算法-java数据结构与算法（二）https://developer.aliyun.com/article/1469490

栈

我们这里将一个场景带入学习

请输入一个表达式

计算式:[722-5+1-5+3-3] 点击计算计算出结果

请问: 计算机底层是如何运算得到结果的？注意不是简单的把算式列出运算,因为我们看这个算式 7 2 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。----> 栈

栈的介绍

栈的英文为(stack)
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
图解方式说明出栈(pop)和入栈(push)的概念

入栈与出栈：栈数据结构的特性先入后出

栈的应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
二叉树的遍历。
图形的深度优先(depth 一 first)搜索法。

栈快速入门（数组模拟栈）

实现思路

详细的每一部分的思路都在代码的注释当中，想要详细理解可以参考代码中的注释

package com.hyc.DataStructure.Stack;
import java.util.Scanner;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Stack
 * @className: ArrayStackDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO 用数组来模拟栈
 * @date: 2021/12/23 18:08
 * @version: 1.0
 */
public class ArrayStackDemo {
    public static void main(String[] args) {
//测试一下 ArrayStack 是否正确
//先创建一个 ArrayStack 对象->表示栈
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true; //控制是否退出菜单
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            System.out.println("show: 表示显示栈");
            System.out.println("exit: 退出程序");
            System.out.println("push: 表示添加数据到栈(入栈)");
            System.out.println("pop: 表示从栈取出数据(出栈)");
            System.out.println("请输入你的选择");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈的数据是 %d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~~");
    }
}
class ArrayStack {
    //栈的最大长度
    private int MaxSize;
    //模拟栈 数据就放在这个数组里
    private int[] stack;
    // 等于栈顶 默认等于-1 代表最底部分
    private int top = -1;
    public ArrayStack() {
    }
    // 初始化栈
    public ArrayStack(int maxSize) {
        MaxSize = maxSize;
        stack = new int[maxSize];
    }
    //返回栈顶 只是显示 并不是 pop 不会改变栈的结构
    public int peek() {
        return stack[top];
    }
    //判断栈是否是满的
    public boolean isFull() {
        return top == MaxSize - 1;
    }
    //判断栈 是否是空的
    public boolean isempty() {
        return top == -1;
    }
    //将数据压入栈
    public void push(int data) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = data;
    }
    //    将数据取出栈
    public int pop() {
        if (isempty()) {
            throw new RuntimeException("栈是空的 无法取出");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //遍历栈 遍历的时候需要从栈顶开始显示数据
    public void list() {
        if (isempty()) {
            System.out.println("栈是空的");
        }
        //   从栈顶开始输出 其实就是倒序的输出数组 
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
}

小总结

这里我们用数组模拟了栈的一些基础操作，入栈出栈遍历内容，
除了使用数组，我们还可以使用链表来实现栈，这里我也写了这种写法有详细的注释，代码如下

package com.hyc.DataStructure.Stack;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Stack
 * @className: ListStackDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO 用链表来模拟栈
 * @date: 2021/12/23 18:23
 * @version: 1.0
 */
public class ListStackDemo {
    public static void main(String[] args) {
        listStack listStack = new listStack();
        listStack.push(5);
        listStack.push(6);
        listStack.push(9);
        System.out.println("出栈前");
        listStack.list();
        System.out.println("出栈后");
        System.out.println("出栈：" + listStack.pop());
        System.out.println("出栈：" + listStack.pop());
        listStack.list();
    }
}
class listStack {
    //创建一个头结点
    StackNode head = new StackNode(0);
    StackNode temp = head;
    //判断是否为空
    public boolean isempty() {
        return head.next == null;
    }
    //压入栈
    public void push(int value) {
        //创建节点对象
        StackNode newnode = new StackNode(value);
        //改变头节点指针的指向
        temp.next = newnode;
        //指针后移
        temp = temp.next;
    }
    //出栈
    public int pop() {
        if (isempty()) {
            throw new RuntimeException("栈空");
        }
        StackNode Before = head;
        //将 before 节点遍历到 temp也就是最后一个节点的上一个节点，让temp指针想前遍历
        while (true) {
            if (Before.next == temp) {
                break;
            }
            Before = Before.next;
        }
        //将before的下一个节点为空相当于出栈之后 删除引用
        Before.next = null;
        //取值
        int value = temp.data;
        //此时 before指向的这个节点就是上一个节点的位置，将temp前移动，重复操作实现出栈
        temp = Before;
        return value;
    }
    //遍历栈
    public void list() {
        //    判断非空
        if (isempty()) {
            System.out.println("栈是空的");
            return;
        }
        StackNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            System.out.println(temp.next.data);
            temp = temp.next;
        }
    }
}
//单向链表节点
class StackNode {
    // 数据
    public int data;
    //下一个节点
    public StackNode next;
    public StackNode(int data) {
        this.data = data;
    }
    //方便输出语句输出
    @Override
    public String toString() {
        return "StackNode{" +
                ", data='" + data + '\'' +
                ", next=" + next +
                '}';
    }
}

中缀表达式计算器

使用栈来实现综合计算器

计算机底层是如何处理这种公式的呢，思路如下

我们需要使用两个栈，一个记录数字，一个记录符号，根据这个栈的数据特性来通过符号和数据的出现规则来实现公式的计算

思路

1.通过一个index值（素引）,来遍历我们的表达式
2.如果我们发现是一个数字，就直接入数栈
3.如果发现扫描到是一个符号，就分如下情况
3.1如果发现当前的符号栈为空，就直接入栈
3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
于栈中的操作符，就直接入符号找。
4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
5.最后在数栈只有一个数字，就是表达式的结果
验证：3+2*6-2=13
这里我们就根据上面的思路实现接下来的思路

代码实现

package com.hyc.DataStructure.Stack;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Stack
 * @className: Calculator
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/24 20:39
 * @version: 1.0
 */
public class Calculator {
    public static void main(String[] args) {
        //  根据文章的思路 我们这里完成对一串计算只包含加减乘除的表达式运算操作
        String expression = "3+2*6-2";
        /** 计算思路 使用栈完成表达式的计算思路
         * 1.通过一个index值（素引）,来遍历我们的表达式
         * 2.如果我们发现是一个数字，就直接入数栈
         * 3.如果发现扫描到是一个符号，就分如下情况
         * 3.1如果发现当前的符号栈为空，就直接入栈
         * 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
         * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
         * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
         * 于栈中的操作符，就直接入符号找。
         * 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
         * 5.最后在数栈只有一个数字，就是表达式的结果
         * 验证：3+2*6-2=13
         * 这里我们就根据上面的思路实现接下来的思路
         * */
        // 创建两个栈 一个存放需要计算的数字 一个存放需要运算的符号
        ArrayCalStack numStack = new ArrayCalStack(10);
        ArrayCalStack operStack = new ArrayCalStack(10);
        //    定义相关变量
        int index = 0; //用于指针扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        //将每次扫描得到的char保存到ch
        char ch;
        //用于萍姐多位数
        String keepNums = "";
        //开始while 循环扫描表达式 expression
        while (true) {
            //    一次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //    判断ch 是什么（数字或者符号）之后进行操作
            if (operStack.isOper(ch)) {
                /*   如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
                 * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
                 * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
                 * 于栈中的操作符，就直接入符号找。*/
                //非空判断
                if (!operStack.isempty()) {
                    if (operStack.priotrity(ch) <= operStack.priotrity(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        //    把运算结果压入 数字栈
                        numStack.push(res);
                        // 之后将当前的符号压入栈 不然会缺失一个运算符号
                        operStack.push(ch);
                    } else {
                        //如果当前的操作符的优先级别大于栈中的操作符 就直接进入符号栈
                        operStack.push(ch);
                    }
                } else {
                    //    如果为空直接入符号栈
                    operStack.push(ch);
                }
            } else {
                //  如果是数字 就直接进入数字栈
                /*思路
                 * 这里我们要考虑到多位数 在处理多位数的时候
                 *  我们需要扫描这个数的下一位一直到找到下一个符号
                 * 这个时候我们定义一个字符串用于拼接找到的数
                 * */
                //    处理多位数
                keepNums += ch;
                //    如果ch已经是 expression 最后一位name就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNums));
                } else {
                    //    判断下一个字符是不是数字 ，如果是就继续向下判断 是运算符则入栈，这里我们要看的是结束的地方是不是符号
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        //如果最后一位事原酸父则如入栈 这里我们的操作变化就是 keepnums =1 或者是 keepnums = 123
                        numStack.push(Integer.parseInt(keepNums));
                        //    加入之后能讲 keepnunms清空 用于下一位的判断
                        keepNums = "";
                    }
                }
            }
            //    让 index +1 并判断是否扫描到expression 最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        //    当表达式扫描完毕，就循序的从数栈和符号栈中 pop出相应的数和符号，并且运行
        while (true) {
            //    如果符号为空，则计算到最后的结果，数栈中只有一个数字【结果】
            if (operStack.isempty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            //入栈
            numStack.push(res);
        }
        //    将数栈最后的数，pop出，就是结果
        int res2 = numStack.pop();
        System.out.printf("表达式%s = %d", expression, res2);
    }
}
/*
 *  应为要实现计算器 我们需要编写一些新的功能，
 * */
class ArrayCalStack {
    //栈的最大长度
    private int MaxSize;
    //模拟栈 数据就放在这个数组里
    private int[] stack;
    // 等于栈顶 默认等于-1 代表最底部分
    private int top = -1;
    public ArrayCalStack() {
    }
    // 初始化栈
    public ArrayCalStack(int maxSize) {
        MaxSize = maxSize;
        stack = new int[maxSize];
    }
    //返回栈顶 只是显示 并不是 pop 不会改变栈的结构
    public int peek() {
        return stack[top];
    }
    //判断栈是否是满的
    public boolean isFull() {
        return top == MaxSize - 1;
    }
    //判断栈 是否是空的
    public boolean isempty() {
        return top == -1;
    }
    //将数据压入栈
    public void push(int data) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = data;
    }
    //    将数据取出栈
    public int pop() {
        if (isempty()) {
            throw new RuntimeException("栈是空的 无法取出");
        }
        int value = stack[top];
        top--;
        return value;
    }
    //遍历栈 遍历的时候需要从栈顶开始显示数据
    public void list() {
        if (isempty()) {
            System.out.println("栈是空的");
        }
        //   从栈顶开始输出 其实就是倒序的输出数组
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
    /* 返回运算符的优先级 这个规则我们可以自己来设定 优先级使用数字来表示
     * 数字越大优先级约高
     * */
    public int priotrity(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;
        }
    }
    //    判断是不是一个字符
    public boolean isOper(char val) {
        return val == '*' || val == '/' || val == '+' || val == '-';
    }
    //    计算操作 用于执行运算
    public int cal(int num1, int num2, int 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:
                break;
        }
        return res;
    }
}

这里我们实现了基础的表达式运算，但是我们没有考虑的事

我们实现了基本计算，但是没有考虑小括号等
中缀表达式对我们来说是十分的好算的，但是对于计算机计算是不方便的，之后会给大家更新适合计算机计算的后缀表达式

中缀转后缀表达式逆波兰计算器实现

什么是前缀，什么中缀，什么是后缀？（理论加举例）

前缀

前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。

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

输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。

中缀

（或中缀记法）是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。

与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。

与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。

例：

（1）8+4-6*2用后缀表达式表示为：

8 4+6 2*-

（2）2*（3+5）+7/1-4用后缀表达式表示为：

235+*71/+4-

后缀

这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用械实现求值。对于表达式x:=(a+b)(c+d)，其后缀式为xab+cd+:=。

原表达式：a(b(c+d/e)-f)# / # 为表达式结束符号/

后缀式：abcde/+f-#

为运算符定义优先级：# ( + - * / **

-1 0 1 1 2 2 3

从原表达式求后缀式的规则为：

思路分析

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

1．从左至右扫描，将 3 和 4 压入堆栈；

2．遇到+运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈；

3．将 5 入栈；

4．接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；

5．将 6 入栈；

6．最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果

代码实现

public static void main(String[] args) {
        //定义逆波兰表达式
        //    测试
        String suffixExpression = "3 4 + 5 * 6 -";
        //    思路
        //    1. 先将 3 4 + 5 * 6 - 方法哦 ArrayList中
        //    2. 将 Arraylist 传递一个方法 遍历ArrayList 配合栈完成计算
        List<String> list = getListString(suffixExpression);
        System.out.println("rpnlist = " + list);
        int res = calculate(list);
        System.out.println("计算的结果是 = " + res);
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将一个逆波兰表达式的数据和运算符 依次放入Arraylist中
     * @date: 2021/12/25 18:09
     * @param suffixExpression
     * @return: java.util.List<java.lang.String> 将分割好的字符List 返回
     */
    public static List<String> getListString(String suffixExpression) {
        //  分割字符串 将后缀表达式的每一个字符取出
        String[] split = suffixExpression.split(" ");
        // 我们用list 来存储分割出来的表达式，这样之后我们就需要遍历即可
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
/**
     * @author 冷环渊 Doomwatcher
     * @context: 这个方法就是 逆波兰表达式的运算处理方法
     *  * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 -
     *  * 1） 从左至右扫描，将3和4压入栈
     *  * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈
     *  * 3） 将5 入栈
     *  * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5  = 35 将结果入栈
     *  * 5） 将6 入栈
     * @date: 2021/12/25 18:14
     * @param ls
     * @return: int 返回的是一个运算结果
     */
    public static int calculate(List<String> ls) {
        //创建栈 只需要一个栈即可
        Stack<String> stack = new Stack<>();
        //    遍历处理
        for (String item : ls) {
            // 这里我们用正则表达式来取出数字 和符号 如果是数字进行处理，如果符号做另外的处理
            if (item.matches("\\d+")) {
                //匹配的是数字
                stack.push(item);
            } else {
                //    如果是符号就 pop出两个数 运算之后结果入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)) {
                    res = num1 + num2;
                } else if ("-".equals(item)) {
                    res = num1 - num2;
                } else if ("*".equals(item)) {
                    res = num1 * num2;
                } else if ("/".equals(item)) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                //    把 res 入栈
                stack.push("" + res);
            }
        }
        //最后留在stack 中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }

这里我们用list加栈的方式实现了表达式的运算

需要注意的几点：

从中体会后缀表达式和中缀表达式的转换
计算上，后缀与中缀的区别

中缀转后缀表达式

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。所以我们需要用代码将中缀表达式处理成后缀表达式之后运算一劳永逸

思路

1.初始化两个栈元素安抚栈 s1 和存储中间结果的栈2
2.从左至右扫描中缀表达式
3.遇到操作数时将其压入s2
4.遇到运算符时比较其与s1栈顶的运算符优先级别：
1。如果s1为空或者栈顶运算符为左括号（则直接将此运算符压入栈
2.否则，若优先级别比栈顶运算符的高，也将运算符压入s1
3.否则将s1栈顶的于是暖夫弹出并且压入s2栈内再次转到 4.1与s1新的扎你当运算符比较
5.遇到括号时：
1.如果是左括号（，则直接压入s1
2.如果是右括号），则一次弹出s1栈顶的运算符，并且压入s2，直到遇到左括号位置，此时将一对括号丢弃
6.重复步骤 2-5 直到表达式最右边
7.将s1中剩余的运算符一次弹出并压入s2
8.依次弹出s2中的元素并且输出，结果逆序就是中缀表达式对应的后缀的表达式

思路举例

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下

因此结果为 :"1 2 3 + 4 × + 5 –"

编码

跟着思路来实现代码

代码实现

package com.hyc.DataStructure.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Stack
 * @className: PolandExpression
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 -
 * 1） 从左至右扫描，将3和4压入栈
 * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈
 * 3） 将5 入栈
 * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5  = 35 将结果入栈
 * 5） 将6 入栈
 * 最后 是 - 运算符 计算出 35-6  = 29 由此得出最后的结果
 *
 * 使用技术 这里我们用 java给我们提供的 Stack 和 ArrayList组合来实现计算器
 * @date: 2021/12/25 18:00
 * @version: 1.0
 */
public class PolandExpression {
    public static void main(String[] args) {
        //定义中缀表达式 ，转成后置表达式之后运算
        String expression = "1+((2+3)*4)-5";
        //拆成链表
        List<String> infixExpressionList = toinfixExpression(expression);
        System.out.println("中缀表达式对应的list=" + infixExpressionList);
        List<String> suffixexpression = parseSuffixExpressionList(infixExpressionList);
        System.out.println("后缀表达式对应的List" + suffixexpression);
        System.out.printf("expression=%d", calculate(suffixexpression));
        //定义逆波兰表达式
        //    测试
        String suffixExpression = "3 4 + 5 * 6 -";
        //    思路
        //    1. 先将 3 4 + 5 * 6 - 方法哦 ArrayList中
        //    2. 将 Arraylist 传递一个方法 遍历ArrayList 配合栈完成计算
        List<String> list = getListString(suffixExpression);
        System.out.println("rpnlist = " + list);
        int res = calculate(list);
        System.out.println("计算的结果是 = " + res);
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将 Arraylist[1,+,(,(,2,+,3,),*,4,),-,5]  转化成  Arraylist[1,2,3,+,4,*,5,-]
     *  转换思路：
     * 1. 初始化两个栈 元素安抚栈 s1 和存储中间结果的栈2
     * 2.从左至右扫描中缀表达式
     * 3.遇到操作数时 将其压入s2
     * 4.遇到运算符时 比较其与s1栈顶的运算符优先级别：
     *  1。如果s1为空 或者栈顶运算符为左括号（ 则直接将此运算符压入栈
     *  2.否则，若优先级别比栈顶运算符的高，也将运算符压入s1
     *  3.否则 将s1栈顶的于是暖夫弹出并且压入s2栈内 再次转到 4.1与s1新的扎你当运算符比较
     * 5.遇到括号时：
     *  1.如果是左括号（ ，则直接压入s1
     *  2.如果是右括号），则一次弹出s1栈顶的运算符，并且压入s2，直到遇到左括号位置，此时将一对括号丢弃
     * 6.重复步骤 2-5 直到表达式最右边
     * 7.将s1中剩余的运算符一次弹出并压入s2
     * 8.依次弹出s2中的元素并且输出，结果逆序就是中缀表达式对应的后缀的表达式
     *
     * @date: 2021/12/27 17:48
     * @param
     * @return: java.util.List<java.lang.String>
     */
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //    定义两个栈
        /*符号栈*/
        Stack<String> s1 = new Stack<>();
        /* S2 思路说明
         * 这里我们使用栈 在转换过程中我们不需要pop操作，而且这个s2 之后我们需要逆序输出操作很麻烦
         * 于是这里使用List来当作 s2 的数据存储结构
         * */
        List<String> s2 = new ArrayList<>();
        //    遍历 ls
        for (String item : ls) {
            //  如果是一个数字 那么就加入 S2（这里我们字符串加入 正则表达式来判断是不是一个数字）
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //    如果是 ）右括号 则一次弹出 s1栈顶的运算符 并且压入 s2 知道遇到左括号为止，完成前置的一系列操作之后将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                // 弹出（ 消除掉一组括号
                s1.pop();
            } else {
                /* 当 item 优先级小于等于s1 栈顶运算符的时候 将s1栈顶的运算符淡出并且加入到s2 中，再次重复思路中的第四个环节，与s1中的新栈顶运算符比较
                 *问题 我们缺少一个比较优先级高低的方法
                 * */
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //    之后将 itea 压入栈
                s1.push(item);
            }
        }
        //    将s1中剩余的运算符一次弹出加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        //    注意应为存放的是list 这里我们顺序不需要改变 直接输出就是对应的后缀表达式
        return s2;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将中缀表达式 转换成对应的list
     * @date: 2021/12/27 17:32
     * @param s
     * @return: java.util.List<java.lang.String>
     */
    public static List<String> toinfixExpression(String s) {
        /*定义一个List 存放中缀表达式的对应内容*/
        List<String> ls = new ArrayList<>();
        //定义一个指针 用于遍历 中缀表达式的字符串
        int i = 0;
        // 用于拼接字符串
        String str;
        //用于存放遍历的字符
        char c;
        do {
            //   如果c是一个非数字 那么我们需要加入到 ls 中去 ，这里的判断条件是 ASCLL值
            if ((c = s.charAt(i)) < 48 || ((c = s.charAt(i)) > 57)) {
                ls.add("" + c);
                //    指针后移
                i++;
            } else {
                /*
                 * 如果是一个数字 那么我们还需要考虑是不是多位数
                 * 这里我们将 str 置空
                 * */
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && ((c = s.charAt(i)) <= 57)) {
                    //拼接数字字符串
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将一个逆波兰表达式的数据和运算符 依次放入Arraylist中
     * @date: 2021/12/25 18:09
     * @param suffixExpression
     * @return: java.util.List<java.lang.String> 将分割好的字符List 返回
     */
    public static List<String> getListString(String suffixExpression) {
        //  分割字符串 将后缀表达式的每一个字符取出
        String[] split = suffixExpression.split(" ");
        // 我们用list 来存储分割出来的表达式，这样之后我们就需要遍历即可
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 这个方法就是 逆波兰表达式的运算处理方法
     *  * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 -
     *  * 1） 从左至右扫描，将3和4压入栈
     *  * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈
     *  * 3） 将5 入栈
     *  * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5  = 35 将结果入栈
     *  * 5） 将6 入栈
     * @date: 2021/12/25 18:14
     * @param ls
     * @return: int 返回的是一个运算结果
     */
    public static int calculate(List<String> ls) {
        //创建栈 只需要一个栈即可
        Stack<String> stack = new Stack<>();
        //    遍历处理
        for (String item : ls) {
            // 这里我们用正则表达式来取出数字 和符号 如果是数字进行处理，如果符号做另外的处理
            if (item.matches("\\d+")) {
                //匹配的是数字
                stack.push(item);
            } else {
                //    如果是符号就 pop出两个数 运算之后结果入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)) {
                    res = num1 + num2;
                } else if ("-".equals(item)) {
                    res = num1 - num2;
                } else if ("*".equals(item)) {
                    res = num1 * num2;
                } else if ("/".equals(item)) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                //    把 res 入栈
                stack.push("" + res);
            }
        }
        //最后留在stack 中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    //   写一个方法 返回对应的数字
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符");
                break;
        }
        return result;
    }
}

总结

计算的思路和我们先前写的逆波兰计算器事一样的
这里我们考虑中缀转后缀的几个要点，运算符优先级和运算符的位置
动手之后，debug看看栈和List的变化加深理解

排序算法

快速排序

快速排序法介绍：

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

快速排序思路图：

快速排序的思路由上图所示：

首先是找到一个基准点，这个不一定非要是中位数，也可以是任意一位，可以自主分割，在什么位置都可以，这里我们以中位来学习
根据中位数为基准，将需要排序的数组分为两份，之后分别交换位置，保证比中位数小的都在左边，比中位数的都在右边，此时左右两边虽然无序，但是都保证一定规则
之后按照递归，再次将左边选出中位数，右边选出中位数，递归到不能交换为止

快速排序案例

要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。【测试 8w 和 800w】说明[验证分析]:

如果取消左右递归，结果是 -9 -567 0 23 78 70
如果取消右递归,结果是 -567 -9 0 23 78 70
如果取消左递归,结果是 -9 -567 0 23 70 78

public static void quickSort(int[] arr, int left, int right) {
        //  left index
        int l = left;
        int r = right;
        //    pivot 中轴值
        int pivot = arr[(left + right) / 2];
        //临时变量
        int temp = 0;
        //    while 循环的目的是比比中轴的pivot值小的放在左边
        //    比pivot 值大的放在右边
        while (l < r) {
            //    在pivot的左边一直寻找 找到大于等于pivot 的值才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //    在pivot的右边一直寻找 找到小于等于pivot 的值才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
            //    如果 l>=r说明pivot的左右两个值已经按照左边全都是小于等于pivot，右边去哪不是大于等于pivot排列好了
            if (l >= r) {
                break;
            }
            //    交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //    如果交换玩发现这个arr[l]==pivot值 相等r--前移
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换玩发现 arr[r] == pivot值 相等l++ 后移
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        //    如果l==r 必须是 l++ r-- 否则会出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }

排序过程断点调试

int arr[] = {-9, 78, 0, 23, -567};

我们的测试数组是一个五位数的数组，

进入循环，此时我们看到，中位数和左右两边的索引，0和4

这里我们可以看第一组数据，

下标0 arr[l] =- 9, -9小于0于是左边下标后移继续寻找，找到78，此时l = 1 是78对应的数组下标此时的78 比中位 0 要大，进入右侧比对

显然 arr[r] = -567 比中位数小，不需要改变下标，跳出循环，

此时我们对比因为我们之后需要重复的递归，这里就是我们递归的跳出条件，如果左边大于右边了，代表左边已经没有大于中位数的数了，反之右边也一定没有小于中位数的

此时，交换两边不符合条件的数字，将比0大的七十八交换到右边吗，将比0小的-567交换到左边

交换完成之后，判断左右两边此时小标的数字是否与中位数相等，如果相等就后移，不需要重复比对

此时我们的第一次循环就结束了，可以看到，数组已经被交换到了，我们的思路第一步的样子，

比中位数0 小的都在左边，比中位数0大的都在右边，之后我们需要重复递归，一直到交换不了为止

此时 r 与l相等，就代表都到中位数了，左右两边都递归有序了，此时我们需要将l后一位，r前移一位，防止栈溢出，并且再继续向下，再最后一次递归之前会结束，

后面的递归就是重复的分组重复的交换，一直到左索引小于又索引，代表还可以继续分组排序，直到左边递归完毕

右索引大于左索引代表可以继续向右边递归，一直到右边递归完毕

快速排序测速

八十万长度存放0-80w的随机数

可以看到，效率是十分的快速

有兴趣的小伙伴可以自己试试写一个冒泡排序测试一下，再拿小冷的快速排序测试一下，算法的精妙之处一下就能感受到了

归并排序

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

基本思想:

分开：将数组递归拆分成最小子序列，之后分组排序

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将

[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]

动态图

思路实现

给你一个数组, val arr = Array(8, 4, 5, 7, 1, 3, 6, 2 ), 请使用归并排序完成排序。

package com.hyc.DataStructure.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergetSort {
    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2}; //
        //测试快排的执行速度
        // 创建要给80000个的随机的数组
        //int[] arr = new int[8000000];
        //for (int i = 0; i < 8000000; i++) {
        //    arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        //}
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);
        Arrays.toString(arr);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        //System.out.println("归并排序后=" + Arrays.toString(arr));
    }
    //分+合方法
    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; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引
        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之,将右边有序序列的当前元素，填充到temp数组
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        //(三)
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t = 0;
        int tempLeft = left; //
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}

速度测试

长度为 8000000，每个内容为0-800000的随机数，

可以很稳定，两秒左右，同样是排序，思想不同带来的优化肉眼可见的，以上就是归并排序的内容啦

基数排序

经典空间换时间的思想流排序算法

基数排序(桶排序)介绍

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展
基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个

位数分别比较。

基数排序基本思想

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

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

创建一个二维数组，arr[10][n] 10是作为的桶，n是每个桶要装的数，按照个位数取出放到桶里，之后再按照十位数，分桶，一般来说排序的次数和最大数的位数一致，但是空间占用会越来越大，金典的空间换时间的算法

第二轮

最后

动图演示

代码思路实验

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

package com.hyc.DataStructure.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        // 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() * 8000000); // 生成一个[0, 8000000) 数
//    }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        radixSort(arr);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        System.out.println("基数排序后 " + Arrays.toString(arr));
    }
    //基数排序方法
    public static void radixSort(int[] arr) {
        //根据前面的推导过程，我们可以得到最终的基数排序代码
        //1. 得到数组中最大的数的位数
        int max = arr[0]; //假设第一数就是最大数
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
        //说明
        //1. 二维数组包含10个一维数组
        //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
        //3. 名明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
        //这里我们使用循环将代码处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            //遍历每一桶，并将桶中是数据，放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中，有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环该桶即第k个桶(即第k个一维数组), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
            }
            //System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
        }
    
    /*
    
    //第1轮(针对每个元素的个位进行排序处理)
    for(int j = 0; j < arr.length; j++) {
      //取出每个元素的个位的值
      int digitOfElement = arr[j] / 1 % 10;
      //放入到对应的桶中
      bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
      bucketElementCounts[digitOfElement]++;
    }
    //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
    int index = 0;
    //遍历每一桶，并将桶中是数据，放入到原数组
    for(int k = 0; k < bucketElementCounts.length; k++) {
      //如果桶中，有数据，我们才放入到原数组
      if(bucketElementCounts[k] != 0) {
        //循环该桶即第k个桶(即第k个一维数组), 放入
        for(int l = 0; l < bucketElementCounts[k]; l++) {
          //取出元素放入到arr
          arr[index++] = bucket[k][l];
        }
      }
      //第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
      bucketElementCounts[k] = 0;
      
    }
    System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));
    
    
    //==========================================
    
    //第2轮(针对每个元素的十位进行排序处理)
    for (int j = 0; j < arr.length; j++) {
      // 取出每个元素的十位的值
      int digitOfElement = arr[j] / 10  % 10; //748 / 10 => 74 % 10 => 4
      // 放入到对应的桶中
      bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
      bucketElementCounts[digitOfElement]++;
    }
    // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
    index = 0;
    // 遍历每一桶，并将桶中是数据，放入到原数组
    for (int k = 0; k < bucketElementCounts.length; k++) {
      // 如果桶中，有数据，我们才放入到原数组
      if (bucketElementCounts[k] != 0) {
        // 循环该桶即第k个桶(即第k个一维数组), 放入
        for (int l = 0; l < bucketElementCounts[k]; l++) {
          // 取出元素放入到arr
          arr[index++] = bucket[k][l];
        }
      }
      //第2轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
      bucketElementCounts[k] = 0;
    }
    System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));
    
    
    //第3轮(针对每个元素的百位进行排序处理)
    for (int j = 0; j < arr.length; j++) {
      // 取出每个元素的百位的值
      int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
      // 放入到对应的桶中
      bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
      bucketElementCounts[digitOfElement]++;
    }
    // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
    index = 0;
    // 遍历每一桶，并将桶中是数据，放入到原数组
    for (int k = 0; k < bucketElementCounts.length; k++) {
      // 如果桶中，有数据，我们才放入到原数组
      if (bucketElementCounts[k] != 0) {
        // 循环该桶即第k个桶(即第k个一维数组), 放入
        for (int l = 0; l < bucketElementCounts[k]; l++) {
          // 取出元素放入到arr
          arr[index++] = bucket[k][l];
        }
      }
      //第3轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
      bucketElementCounts[k] = 0;
    }
    System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr)); */
    }
}

速度测试

八百万长度，内容为 0-8000000的随机数只需要一秒钟

我们简单计算一下用来多少内容

8000000 * 11 * 4 / 1024 / 1024 / 1024 =1G

从公式可以看出我们排序八百万使用到了1g的内存，从各方面都可以看出，基数排序是经典的空间换时间的算法

基数排序的说明:

基数排序是对传统桶排序的扩展，速度很快.
基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

Java数据结构与算法-java数据结构与算法（四）https://developer.aliyun.com/article/1469492

Java数据结构与算法-java数据结构与算法（三）

栈

栈的介绍

栈的应用场景

栈快速入门（数组模拟栈）

小总结

中缀表达式计算器

中缀转后缀表达式逆波兰计算器实现

什么是前缀，什么中缀，什么是后缀？（理论加举例）

中缀转后缀表达式

总结

排序算法

快速排序

快速排序案例

快速排序测速

归并排序

基本思想:

合并相邻有序子序列

动态图

思路实现

速度测试

基数排序

基数排序(桶排序)介绍

基数排序基本思想

动图演示

代码思路实验

速度测试

基数排序的说明:

热门文章

最新文章

相关课程

相关电子书

Java数据结构与算法-java数据结构与算法（三）

栈

栈的介绍

栈的应用场景

栈 快速入门（数组模拟栈）

小总结

中缀表达式计算器

中缀转后缀表达式 逆波兰计算器实现

什么是前缀，什么中缀，什么是后缀？（理论加举例）

中缀转后缀表达式

总结

排序算法

快速排序

快速排序案例

快速排序测速

归并排序

基本思想:

合并相邻有序子序列

动态图

思路实现

速度测试

基数排序

基数排序(桶排序)介绍

基数排序基本思想

动图演示

代码思路实验

速度测试

基数排序的说明:

热门文章

最新文章

相关课程

相关电子书

栈快速入门（数组模拟栈）

中缀转后缀表达式逆波兰计算器实现