算法笔记

学习链接尚硅谷

https://www.bilibili.com/video/BV1E4411H73v?p=10

一、稀疏数组

稀疏数组规则：

•  第一行：旧数组的行数 旧数组的列数 旧数组的非零数、
  

•  第二行：非零数所在行数 非零数所在列数 非零数值
  

•  。（以此类推）
  

•  。
  

•  。
  

1.1转为稀疏数组

/**
 * 转为稀疏数组
 */
public static int[][] toSparseArray(int[][] array){
    int sum = showArray(array);
    int [][]sparseArray = new int[sum+1][3];
    //为稀疏数组赋值
    sparseArray[0][0] = 7;
    sparseArray[0][1] = 7;
    sparseArray[0][2] = sum;
    int count = 0;
    for (int i = 0; i < array.length; i++){
        for (int j = 0; j < array[i].length; j++){
            if(array[i][j] != 0){
                count++;
                //赋值
                sparseArray[count][0] = i;
                sparseArray[count][1] = j;
                sparseArray[count][2] = array[i][j];

            }
        }
    }
    return sparseArray;
}

1.2稀疏数组转为正常数组

/**
 * 稀疏数组转为正常数组
 */
public static int[][] sparseArrayToArray(int[][] sparseArray){
    int array[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
    for(int i = 1; i< sparseArray.length; i++){
            array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    }
    return array;
}

二、单链表

2.1添加节点构造方法

/**
 * 添加节点考虑序号
 * @param node
 */
public void addNodeByNum(Node node){
    //获取节点数据内的no值
    int no = node.getNo();
    //遍历
    //当前节点的no值小于添加节点的no值时，进行添加
    Node temp = head;
    //循环用于寻找添加节点的位置
    /*
    三种情况可以找到节点位置，找到后退出循环
    1.当前节点为最后一个节点
    2.当前节点的下一个节点的no值大于新的node的no值
    3.如果编号存在，则添加失败，也退出循环
     */
    //判断新节点的no值是否存在，默认不存在
    boolean isExist = false;
    while(true){
        //temp为最后一个节点
        if(temp.next == null){
            break;
        }
        //当前节点的下一个节点的no值大于新的node的no值
        else if (temp.next.getNo() > node.getNo()){
            break;
        }
        //已经存在编号
        else if(temp.next.getNo() == node.getNo()){
            //标志改为存在
            isExist = true;
            break;
        }
        //后移
        temp = temp.next;
    }
    //进行添加操作（2为新节点）
    if(isExist){
        System.out.println("编号已存在，不可添加");
        return;
    }
    //2连3
    node.next = temp.next;
    //1连2
    temp.next = node;
    System.out.println(node.getNo()+"号，添加成功");
}

主函数

public class SingleList {
    public static void main(String[] args) {
        Node node1 = new Node(1,"小王",20);
        Node node3 = new Node(3,"小张",13);
        Node node2 = new Node(2,"小李",15);

        SingleListt singleListt = new SingleListt();
        //singleListt.addNode(node1);
        //singleListt.addNode(node3);
        //singleListt.addNode(node2);
        singleListt.addNodeByNum(node1);
        singleListt.addNodeByNum(node3);
        singleListt.addNodeByNum(node2);
        singleListt.addNodeByNum(node2);

        singleListt.traverseList();
    }

}

2.2练习题

1.计算单链表的有效节点数

/**
 * 计算链表的有效节点数
 */
public int numberOfComputingNodes(){
    int count = 0;
    if(head.next == null){
        //空链表
        return 0;
    }
    while (head.next != null){
        count++;
        head = head.next;
    }
    return count;
}

2.查找单链表的倒数第k个节点

/**
 * 查找单链表的倒数第k个节点
 */
public Node findDecK(int k){
    Node temp = head.next;
    //链表为空
    if(temp == null){
        return null;
    }
    //计算链表的有效节点数
    int count =  numberOfComputingNodes();
    System.out.println("有效节点数："+count);

    for (int i = 0; i < count - k; i++){
        //节点移动count-k次
        temp = temp.next;
    }
    return temp;
}

3.反转单链表

/**
 * 反转单链表（创建新的头结点，将原链表的节点取出，并使用头插法插入到新的头结点，最后将原链表的头结点连接第一个节点）
 *
 * 步骤1.创建新的头结点
 *     2。将原链表的节点取出，并使用头插法插入到新的头结点
 *     3.最后将原链表的头结点连接第一个节点
 */
public void reverseLinkedList(){
    //空链表或一个节点的链表，不反转
    if(head.next == null || head.next.next == null){
        return;
    }
    //1.创建新的头结点
    Node tempHeadNode = new Node();
    Node temp = head.next;
    //遍历到尾节点
    //2。将原链表的节点取出，并使用头插法插入到新的头结点
    while (temp != null){
        //用于保存原链表中temp的下一节点
        Node next = temp.next;
        temp.next = tempHeadNode.next;
        tempHeadNode.next = temp;

        //后移
        temp = next;
    }
    //3.最后将原链表的头结点连接第一个节点
    head.next = tempHeadNode.next;
}

4.合并两个有序链表

/**
 * 合并两个有序链表，合并完仍然有序
 * 步骤1.创建一个新的头结点，指向一个有序链表
 *  2.遍历第一、二个有序链表链表，对每个节点进行插入
 *      2.1找到合适插入位置的前一个，进行插入
 */
public Node mergeLinkedList(SingleListt singleList){
    //1.创建一个新的头结点，指向一个有序链表

    Node newHead = head;
    newHead.next = head.next;
    //2.遍历第二个有序链表链表，对每个节点进行插入
    Node temp = singleList.getHead().next;
    Node newHeadTemp = newHead;
    //当第二个链表为空时，直接返回新节点
    if(temp == null){
        System.out.println("要合并的链表为空");
        return head;
    }
    //第二个链表遍历到尾节点
    while(temp != null){
        Node next = temp.next;
        //2.1找到合适插入位置的前一个，进行插入
        while(newHeadTemp.next!=null){
            if (temp.getNo() <= newHeadTemp.next.getNo()){
                break;
            }
            newHeadTemp = newHeadTemp.next;
        }
        //找到后插入
        temp.next = newHeadTemp.next;
        newHeadTemp.next = temp;
        //后移
        temp = next;
    }

    return newHead;
}

5.约瑟夫问题

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

小孩类

/**
 * 小孩类
 */
class Boy{
    /**
     * 编号
     */
    private int no;
    /**
     * 指向下一节点
     */
    private Boy next;

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

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

循环单项链表类

/**
 * 单向循环链表类
 */
class SingleCircleLinkList{
    /**
     * 相当于头结点
     */
    private Boy first;

    public Boy getFirst() {
        return first;
    }

    /**
     * 添加男孩
     * @param nums 数量
     */
    public void addBoy(int nums){
        //nums值校验
        if(nums < 1){
            System.out.println("人数不正确");
            return;
        }
        //先创建第一个boy，first指向第一个boy
        Boy boy = new Boy(1);
        first = boy;
        //第一个boy的next指向自己
        boy.setNext(first);
        Boy temp = first;
        //实例化boy
        for (int i = 2; i <= nums; i++) {
            Boy newBoy = new Boy(i);
            //连接当前boy和newBoy
            temp.setNext(newBoy);
            //连接newBoy和first,形成环状
            newBoy.setNext(first);
            //后移
            temp = temp.getNext();
        }
    }
    /**
     * 遍历
     */
    public int getBoys(){
        int num = 0;
        if(first == null){
            return 0;
        }
        Boy temp = first;
        while (true){
            int no = temp.getNo();
            num++;
            //到达末尾
            if(temp.getNext() == first){
                break;
            }
            temp = temp.getNext();
        }
        return num;
    }
}

约瑟夫主类

public class Josephu {
    public static void main(String[] args) {
        //创建链表
        SingleCircleLinkList singleCircleLinkList = new SingleCircleLinkList();
        singleCircleLinkList.addBoy(6);
        Josephu(singleCircleLinkList,5,6);
    }
    public  static void Josephu(SingleCircleLinkList list,int m, int nums){
        int step = m - 1;
        Boy first = list.getFirst();
        //先找到尾节点
        Boy tailNode = getTailNode(list);
        Boy temp = tailNode;

        while (true){
            for (int i = 0; i < step; i++) {
                temp = temp.getNext();
            }
            //first永远在temp的后一个，可有可无
            first = temp.getNext();
            //删除first所在节点
            System.out.println(first.getNo());
            temp.setNext(first.getNext());
            nums--;
            if(nums == 0){
                break;
            }
        }
    }
    /**
     * 获取尾节点
     */
    public static Boy getTailNode(SingleCircleLinkList list){
        int nums = list.getBoys();
        Boy first = list.getFirst();
        Boy temp = first;
        while (true){
            //尾节点
            if(temp.getNext() == first){
                return temp;
            }
            temp= temp.getNext();
        }
    }
}

三、栈

单链表实现栈

public class LinkList {
    /**
     * 链表的头结点
     */
    private Node head = new Node(0,null);
    private int max;

    public LinkList(Node head) {
        this.head = head;
    }

    public LinkList() {
    }
    public LinkList(int max) {
        this.max = max;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }
    /**
     * 判断栈内是否已满
     */
    public boolean isFull(){
        boolean isFull = false;
        //计算栈内元素数
        int num = 0;
        Node temp = head;
        while (true){
            if(num == max){
                isFull = true;
            }
            if(temp.getNext() == null){
                //尾节点了
                break;
            }
            temp = temp.getNext();
            num++;
        }
        return isFull;
    }
    /**
     * 入栈操作
     */
    public void push(int value){
        //判断是否已满
        if (isFull()){
            System.out.println("栈内已满");
            return;
        }
        Node newNode = new Node(value);
        Node temp = head;
        while(true){
            if (temp.getNext() == null){
                temp.setNext(newNode);
                break;
            }
            temp= temp.getNext();
        }

    }
    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return head.getNext() == null;
    }
    /**
     * 出栈操作
     */
    public int pop(){
        int ele;
        //判空
        if(head.getNext() == null){
            System.out.println("栈为空，不可出栈");
            return 0;
        }
        Node temp = head;
        while (true){
            if(temp.getNext().getNext() == null){
                ele = temp.getNext().getNo();
                //出栈
                temp.setNext(null);
                break;
            }
            temp=temp.getNext();
        }
        return ele;
    }
    /**
     * 查看栈顶元素
     * @return
     */
    public int look(){
        int ele;
        //判空
        if(head.getNext() == null){
            return '0';
        }
        Node temp = head;
        while (true){
            if(temp.getNext() == null){
                ele=  temp.getNo();
                break;
            }
            temp=temp.getNext();
        }
        return ele;
    }
    /**
     * 展示栈内元素
     */
    public void showElement(){
        //判空
        if(head.getNext() == null){
            System.out.println("栈内空");
            return;
        }
        Node temp = head.getNext();
        while (true){
            //尾节点
            if(temp.getNext() == null){
                System.out.println(temp.getNo());
                break;
            }
            System.out.println(temp.getNo());
            temp= temp.getNext();
        }
    }

}

节点类

public class Node {
    /**
     * 编号
     */
    private int no;
    /**
     * 指针域
     */
    private Node next;


    public Node() {
    }

    public Node(int no) {
        this.no = no;
    }
    public Node(int no,Node next) {
        this.no = no;
        this.next = next;
    }

    public int getNo() {
        return no;
    }

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

    public Node getNext() {
        return next;
    }

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

3.1栈实现简单计算器

步骤

1. 分类数栈和操作数栈，并根据元素分别进入对应类别栈
2. 判断加入操作数占是否为空
   1. 空，直接加入操作数
   2. 不为空，判断优先级
      1. 当要加入的操作数优先级<=操作数栈顶优先级时，取出两个数栈元素和操作数栈顶元素计算，再将新的操作数加入栈
      2. 小于则直接入栈
3. 加入数栈时要判断下一位是否为数栈，为数栈则扩展字符串，知道出现操作数为止。（用完字符串要置空）
4. 全部入栈后，继续计算（取出两个数栈元素，一个操作数）
5. 当操作数栈为空时，计算完毕，将最后计算的结果加入数栈（为最终答案）

public class Stack {
    public static void main(String[] args) {
        LinkList OperLinkList = new LinkList(5);
        LinkList NumLinkList = new LinkList(5);
        String temp ="";
        String str = "100+2*2";
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            //判断是否为操作符
            if(isOper(chars[i])){
                if (OperLinkList.isEmpty()){
                    //操作符栈为空
                    //入栈
                    OperLinkList.push(chars[i]);
                }
                else{
                    if(OperPriority(chars[i]) <= OperPriority( OperLinkList.look())){
                        //小于等于栈内的优先级
                        //取出两个数栈元素和一个操作栈元素，进行计算
                        int res = calculate(NumLinkList.pop(),NumLinkList.pop(),OperLinkList.pop());
                        //计算结果入数栈
                        NumLinkList.push(res);
                        OperLinkList.push(chars[i]);
                    }
                    else {
                        //入栈
                        OperLinkList.push(chars[i]);
                    }
                }
            }
            else {
                //进数栈(可能不是个位数，需要拼接)
                //NumLinkList.push(chars[i]-48);
                    temp+=chars[i];
                    //判断是否为最后一位
                    if(i == chars.length-1){
                        //直接入栈
                        NumLinkList.push(Integer.parseInt(temp) );
                    }
                    else {
                        //一直添加到有操作符为止
                        if(isOper(chars[i+1])){
                            //入栈
                            NumLinkList.push(Integer.parseInt(temp));
                            //清空temp缓存
                            temp="";
                        }
                    }
            }

        }
        //全部入栈完毕
        //依次取出数栈和操作数栈进行计算
        while (true){
            if (OperLinkList.isEmpty()){
                break;
            }
            int res = calculate(NumLinkList.pop(),NumLinkList.pop(),OperLinkList.pop());
            NumLinkList.push(res);
        }
        System.out.println("结果为："+ NumLinkList.pop());

    }

    /**
     * 判断是否为操作符
     * @param oper
     * @return
     */
    public static boolean isOper(int oper){
        return oper =='+' || oper =='-'|| oper=='*'||oper=='/';
    }
    /**
     * 判断操作符的优先级
     */
    public static int OperPriority(int oper){
        if(oper == '+' ||oper == '-'){
            return 0;
        }
        else if(oper == '*' || oper == '/'){
            return 1;
        }
        else {
            //出错
            return -1;
        }
    }
    /**
     * 计算
     * @return
     */
    public static int calculate(int num1, int num2, int oper){
        int res = 0;
        switch (oper){
            case '+':
                res = num2 + num1;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num2 * num1;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                System.out.println("符号错误");
                break;

        }

        return res;
    }
}

3.2逆波兰表达式

public class PostfixExpression {
    /**
     * 后缀表达式计算器
     *
     * @param args
     */
    public static void main(String[] args) {
        //(3+4)*5-6 -->29
        String postfixExpression = "3 4 + 5 * 6 -";
        //1.将字符串放入数组中
        String[] strings = postfixExpression.split(" ");
        //2.将数组内元素依次入栈
        Stack<String> stack = new Stack<>();
        for (String string : strings) {
            //如果是数，则入栈（用正则表达式考虑多位数）
            if (string.matches("\\d+")) {
                //为数
                //入栈
                stack.push(string);
            } else {
                //操作符，则pop出两个栈顶元素，并计算，后算前
                String s1 = stack.pop();
                String s2 = stack.pop();
                String res = calculate(s1, s2, string);
                //将计算结果入栈
                stack.push(res);
            }
        }
        //最后栈内元素为最终结果
        int calRes = Integer.parseInt(stack.pop());
        System.out.println("结果为：" + calRes);

    }

    /**
     * 计算两个出栈的数
     *
     * @param s1   先出栈元素
     * @param s2   后出栈元素
     * @param oper 操作符
     * @return 计算结果，String类型
     */
    public static String calculate(String s1, String s2, String oper) {
        int num1 = Integer.parseInt(s1);
        int num2 = Integer.parseInt(s2);
        int res = 0;
        switch (oper) {
            case "+":
                res = num2 + num1;
                break;
            case "-":
                res = num2 - num1;
                break;
            case "*":
                res = num2 * num1;
                break;
            case "/":
                res = num2 / num1;
                break;
            default:
                throw new RuntimeException("符号出错");
        }

        return "" + res;
    }
}

四、递归

4.1递归实现迷宫问题

public class RecursionDemo {
    /**
     * 递归实现迷宫问题
     * @param args
     */
    public static void main(String[] args) {
        //创建迷宫地图
        /**
         * 迷宫 1：代表为墙
         *     2：代表为通路
         *     3：代表为走过的死路
         *     0：没走过的路
         */
        int map[][] = new int[8][7];
        //设置墙壁
        for (int i = 0; i < 7; i++) {
            map[7][i] = 1;
            map[0][i] = 1;
        }
        for (int i = 1; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[6][5] = 4;

        findWay(map,1,1);
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.printf(anInt+" ");
            }
            System.out.println("");
        }

    }

    /**
     * 寻找出口
     * @param map 迷宫地图
     * @param i 初始横坐标
     * @param j 初始纵坐标
     * @return
     */
    public static boolean findWay(int [][]map, int i, int j){
        //判断是否到出口
        if(map[5][4] == 2){
            return true;
        }
        else {
            if (map[i][j] == 0){
                //把当前位置假设为通路
                map[i][j] =2;
                //向下寻找
                if (findWay(map,i+1,j)) {
                    return true;
                }
                //向右
                else if(findWay(map,i,j+1)){
                    return true;
                }
                //向上
                else if(findWay(map,i-1,j)){
                    return true;
                }
                //向左
                else if(findWay(map,i,j-1)){
                    return true;
                }
                else {
                    map[i][j] = 3;
                    return false;
                }
            }
            else {
                return false;
            }
        }
    }
}

4.2递归实现八皇后问题

public class EightQueens {
    /**
     * 递归实现八皇后问题
     * 保证八个旗子互相不能在同一行、列、对角线（8*8的棋盘）
     */
    final static int maxCount = 8;
    static int[] solution = new int[maxCount];
    //最多8枚棋子

    static int count = 0;

    public static void main(String[] args) {
        //数组代表一次可行策略，下标n代表第n个棋子，值row代表第row列
        //solution[n] = row;
        put(0);
        System.out.println(count);

    }
    public static void put(int n){
        //已经放完8枚了
        if(n == maxCount){
            showSolution();
            return;
        }
        else {
            for (int i = 0; i < maxCount; i++){
                solution[n] =i;
                if (!ifJudgmentConflict(n)){
                    put(n+1);
                }
            }
        }

    }

    /**
     * 判断第n个棋子和之前的所有棋子是否冲突
     * @return
     */
    public static boolean ifJudgmentConflict(int n){
        //判断第n个棋子和其他棋子冲突
        for (int i = 0; i < n; i++) {
            //是否在同一列或是否在对角线（纵坐标等于横坐标）
            if(solution[n] == solution[i] || Math.abs(n-i) == Math.abs(solution[n]-solution[i])){
                //冲突
                return true;
            }
        }
        return false;
    }

    /**
     * 遍历数组
     */
    public static void showSolution(){
        count++;
        for (int i : solution) {
            System.out.printf(i+" ");
        }
        System.out.println("");
    }
}

五、排序

度量程序执行时间的两种方法

1. 事后统计方法：要求同一台机器同一状态
2. 事前估算方法： 分析程序的时间复杂度

排序

5.1冒泡排序

每次寻找一个最大的数放在最后

优化：当本次循环没有交换，则完成排序，不继续比较

public class BubbleSort {
    public static void main(String[] args) {
        int []arr = {12,43,5234,1,54,14};
        bubbleSort(arr);
    }

    /**
     * 冒泡
     * @param arr
     */
    public static void bubbleSort(int []arr){

        //判断本次循环是否有交换（优化）
        boolean ifExchange = false;
        int temp = 0;
        for (int i = 0; i < arr.length-1; i++){
            for (int j = 0; j < arr.length-1-i; j++){
                //如果前面值大
                if(arr[j] > arr[j+1]){
                    //交换
                    ifExchange = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (ifExchange){
                //复原用于下一次循环
                ifExchange = false;
            }
            else {
                break;
            }
            printArr(arr);

        }
    }
    /**
     * 打印数组
     */
    public static void printArr(int []arr){
        for (int i : arr) {
            System.out.printf(i+" ");
        }
        System.out.println();
    }
}

5.2选择排序

每趟循环寻找一个最小的数，本次循环后将最小的数与第一个数交换位置

优化：当寻找后最小下标不变，则不交换

public static void selectSort(int []arr){
    //假设数组内第一个元素为最小值，所以最小下标为0
    int minIndex = 0;
    //临时量，用于交换
    int temp = 0;
    for (int i = 0; i < arr.length; i++) {
        minIndex = i;
        for (int j = i+1; j < arr.length; j++){
            //如果后面数比最小数大
            if(arr[minIndex] > arr[j]){
                //更该最小下标
                minIndex = j;
            }
        }
        //有比第一个更小的，交换(优化)
        if (minIndex != i){
            //将最小值放在第一个位置
            temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

}

5.3插入排序

将数组分为两部分：有序和无序，（第一个数为有序）

将后面无序的数，向前依次对有序数比较（无序数小则有序数一直向后覆盖）

最后将最前面的数补位那个无序数。

public static void insertSort(int []arr){
        for (int i = 1; i < arr.length; i++){
            //存储当前值
            int value = arr[i];
            int j =i;
            for(j = i-1;j>=0&&arr[j]>value; j--){
                //覆盖后面较小值
                arr[j+1] =arr[j];
            }
            arr[j+1] = value;
        }
    }

5.4希尔排序

将数组分组计算，每次分为length/2组（步长为length/2）

public static void shellSort(int []arr){
    //step步长
    for (int step = arr.length/2; step>0; step/=2){
        //根据步长计算应该和谁比较
        for (int i = step; i < arr.length; i++){
            int temp =arr[i];
            int j = i;
            for (j = i-step;j >= 0&&arr[j] > temp; j-=step){
                arr[j+step] = arr[j];
            }
            arr[j+step] = temp;
        }
    }
}

5.5快速排序

传入要排序的头和尾，将第一个值作为标准。

两头向中间遍历，期间将小于标准值的和大于标准值的数互换，直到相遇，=（先右，在左），然后将标准值归正确位置

然后递归标准值左边的，递归标准值右边的。

递归出口：当传入的头小于等于尾时

public static void quickSort(int []arr,int left, int right){
    if (left >= right){
        return;
    }
    //第一个值作为标准值
    int standard = arr[left];
    //右边寻找的哨兵
    int rightFind =right;
    //左边寻找的哨兵
    int leftFind = left;
    //存储临时变量
    int temp = 0;

    while (leftFind < rightFind){
        //右边有值大于等于标准值
        while (arr[rightFind] >= standard && leftFind<rightFind){
            //哨兵左移一个
            rightFind--;
        }
        //左边有值小于等于标准值
        while (arr[leftFind] <= standard && leftFind<rightFind){
            //哨兵左移一个
            leftFind++;
        }
        //找到对应值，交换
        if (leftFind < rightFind){
            temp = arr[rightFind];
            arr[rightFind] = arr[leftFind];
            arr[leftFind] = temp;
        }
    }
    //将当前值与标准值互换位置(将标准值归位)
    arr[left] = arr[rightFind];
    arr[rightFind] =standard;
    printArr(arr);
    //递归
    quickSort(arr,left,rightFind-1);
    quickSort(arr,rightFind+1,right);
}

5.6归并排序

类似于二叉树，一直递归到最低。

当每层结束的时候名，将该层的arr排序

排序后记得将排序后的元素复制到arr中

/**
 * 归并
 * @param arr 原始数组
 * @param left  数组的最左端
 * @param right 数组的最右端
 * @param temp  临时数组，用于还原
 */
public static void mergeSort(int []arr, int left, int right,int []temp){
    if (left >= right){
        return;
    }
    //对左边进行递归
    int mid = (left+right)/2;
    //System.out.println("左");
    mergeSort(arr,left,mid,temp);

    //右边
    //System.out.println("右");
    mergeSort(arr,mid+1,right,temp);

    merge(arr,left,mid,right,temp);
    printArr(arr);

    //System.out.println("完");
}
public static void merge(int[] arr,int left,int mid,int right, int[] temp){
    //左边序列开始索引
    int i = left;
    //右边
    int j = mid+1;
    //temp的开始索引
    int k = 0;
    while (i<=mid&&j<=right){
        //将小的值放入temp中，并且下标都后移一个
        if(arr[i] < arr[j]){
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
        }
    }
    //此时如果有数组有剩余
    while (i <= mid){
        temp[k++]= arr[i++];
    }
    //此时如果有数组有剩余
    while (j <= right){
        temp[k++]= arr[j++];
    }
    //此时temp已经为排序好的数组，将temp内元素转移到arr中
    for (int x = 0; x < k;x++){
        arr[left+x] = temp[x];
    }
}

5.7基数排序

比较数组内各数的个位，然后放入对应桶内，取出放回数组，再比较十位。。。

注意：取出后应将计算桶内元素数的数组清零

public static void baseSort(int []arr){
    //计算数组内最大值
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (max<arr[i]){
            max = arr[i];
        }
    }
    //计算最大值的位数(个、十、百。。)
    int exponent = (max+"").length();
    //10个临时存放数组的桶，每个桶最多存length个
    int[][] bucketArray = new int[10][arr.length];

    //存放每个桶内的元素数量
    int []bucketEleCount = new int[10];
    for (int i = 1, n = 1; i < exponent+1; i++,n*=10){
        for (int arrIndex = 0; arrIndex < arr.length; arrIndex++){
            //当前循环需要比较的尾数
            int tailNum = ((arr[arrIndex])/n) %10;
            //将元素放入临时桶内（bucketEleCount[tailNum]的初始值为0，因此需要+1来确定下次放入的位置）
            bucketArray[tailNum][bucketEleCount[tailNum]] = arr[arrIndex];
            bucketEleCount[tailNum]++;
        }
        //依次取出元素，放回到数组内
        int arrIndex = 0;
        for (int bucketIndex = 0; bucketIndex < 10; bucketIndex++){
            //如果计数的桶不为空
            if (bucketEleCount[bucketIndex] != 0){
                for (int j = 0; j < bucketEleCount[bucketIndex]; j++){
                    //取出元素
                    arr[arrIndex++] = bucketArray[bucketIndex][j];
                    //将桶内元素清空（也可以不清空，下次会覆盖，用bucketEleCount来计算得出应该取多少元素）
                    bucketArray[bucketIndex][j] = 0;
                }

            }
            bucketEleCount[bucketIndex] = 0;

        }
    }
}

5.8堆排序

/**
 * 堆排序
 */
public static void heapSort(int []arr){
    //1.将原数组转换为大顶堆
    //arr.length/2-1:最后一个叶子节点
    for(int i = arr.length/2-1; i>=0; i--){
        adjustHeap(arr,i,arr.length);
    }
    //2.已经为大顶堆
    //将最大数放在数组最后，然后继续将数组换位大顶堆
    int temp = 0;
    for (int j = arr.length-1; j>0;j--){
        //交换
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;

        //继续转换为大顶堆，此时只有顶元素需要调整
        adjustHeap(arr,0,j);
    }
}
/**
 * 调整为大顶堆
 * 将数组看做为一个 顺序化树
 * @param arr
 * @param i 当前非叶子节点对应下标，要调整的数的根节点
 * @param length 数组长度
 */
public static void adjustHeap(int[] arr,int i, int length){
    //保存当前非叶子节点
    int temp = arr[i];
    //将以i下标为节点的树调整为大顶堆，循环
    for (int k = 2*i+1; k<length; k=2*k+1){
        //右节点大于左节点
        if(k+1<length && arr[k+1] > arr[k]){
            k++;
        }
        //子节点大于父节点
        if(arr[k] > temp){
            //赋值给父节点
            arr[i] = arr[k];
            //下次从i节点开始
            i = k;
        }
        //父节点大(当前子树已经为大顶堆)
        else {
            break;
        }
    }
    //将原来父节点的值，赋值给下次要开始遍历的值
    arr[i] = temp;
}

六、查找

6.1二分查找

/**
 * 二分查找
 * @param arr
 * @param left
 * @param right
 * @param searchNum 要查找的值
 * @return
 */
public static int binarySearch(int []arr, int left, int right, int searchNum){
    if(left > right){
        //没找到
        return -1;
    }
    //中间值
    int mid = (left+right)/2;
    if(searchNum == arr[mid]){
        //返回下标
        return mid;
    }
    else if (searchNum < arr[mid]){
        return binarySearch(arr,left,mid-1,searchNum);
    }
    else {
        return binarySearch(arr,mid+1,right,searchNum);
    }

}

6.2插值查找

适用于均匀的递增递减序列，并且查找数不能大于最大值，不能小于最小值

/**
 * 插值查找
 * @param arr
 * @param left
 * @param right
 * @param searchNum
 * @return
 */
public static int interpolationSearch(int []arr, int left, int right, int searchNum){
    //防止数组越界加入额外校验
    if(left > right || searchNum < arr[left] || searchNum > arr[right]){
        //没找到
        return -1;
    }
    //中间值(自适应)
    int mid = left + (right - left) *(searchNum - arr[left])/(arr[right]-arr[left]);
    if(searchNum == arr[mid]){
        //返回下标
        return mid;
    }
    else if (searchNum < arr[mid]){
        return interpolationSearch(arr,left,mid-1,searchNum);
    }
    else {
        return interpolationSearch(arr,mid+1,right,searchNum);
    }

}

6.3斐波那契(黄金分割)

//因为后面我们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;
}