Java数据结构与算法一3-阿里云开发者社区

递归

自己调用自己，每次的变量都不一样

规范

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

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

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

递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError（栈溢出），死龟了

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

递归 - 迷宫回溯问题

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

package com.recursion;
/**
 * @author Kcs 2022/8/25
 */
public class MiGong {
    public static void main(String[] args) {
        //二维数组模拟迷宫
        int[][] map = new int[8][7];
        //1.表示墙
        //上下两行置为 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 < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        //设置起点
        // setWay(map, 1, 1);
        setWay2(map, 1, 1);
        //新的地图，标识过的
        System.out.println("走过的路径：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
    /**
     * @param map 地图
     * @param i 起始位置
     * @param j
     * @return true ,false
     * 当 map[i][j]为 0：还没有走的点，1：墙，2：走过的路径，3：走不通的点，(6,5)为终点
     * 策略一: 下 → 右 → 上 → 左，走不通，再回溯
     * 策略二：下 → 左 → 上 → 右
     * 策略三：上 → 右 → 下 → 左
     * 策略很多，可以自己尝试修改，本次使用的策略为策略一，但是存在最优路径
     */
    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)) {
                    //向下走
                    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 {
                    //走不通的起点
                    map[i][j] = 3;
                    return false;
                }
            } else {
                return false;
            }
        }
    }
    /**
     * 策略三：上 → 右 → 下 → 左
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay2(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            return true;
        } else {
            if (map[i][j] == 0) {
                // 假设可以走
                map[i][j] = 2;
                //对应策略的顺序进行修改
                if (setWay2(map, i - 1, j)) {
                    //向上走
                    return true;
                } else if (setWay2(map, i, j + 1)) {
                    //向右走
                    return true;
                } else if (setWay2(map, i + 1, j)) {
                    //向下走
                    return true;
                } else if (setWay2(map, i, j - 1)) {
                    //向左走
                    return true;
                } else {
                    //走不通的起点
                    map[i][j] = 3;
                    return false;
                }
            } else {
                return false;
            }
        }
    }
}

八皇后问题（92种）

问题描述：在一个8 × 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列

package com.recursion;
/**
 * @author Kcs 2022/8/28
 */
public class Queue8 {
    /**
     * 皇后总数
     */
    int max = 8;
    /**
     * 定义数组array，保留皇后放置的位置
     */
    int[] array = new int[max];
    /**
     * 统计一共有多少种解法
     */
    static int count = 0;
    public static void main(String[] args) {
        //测试
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("共有解法：%d", count);
    }
    /**
     * 放置第n个皇后
     * check每一次递归时，都会进入到for循环
     */
    private void check(int n) {
        //8皇后已经放完
        if (n == max) {
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //本皇后n，放置行的首列
            array[n] = i;
            //皇后放置第i列，判断是否与前面的皇后的列是否冲突
            if (judge(n)) {
                //不冲突，接着下一个皇后， 递归
                check(n + 1);
            }
            //冲突，回去到上一行 array[n] = i，将第n个皇后，放置在本行的后移一个位置
        }
    }
    /**
     * 查看放置的皇后是否与前面放置的皇后是否产生冲突
     * n: 第n个皇后
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            //判断皇后是否在同一列上，或者统一斜线上(Math.abs(n - i) == Math.abs(array[n] - array[i] n:表示列上，
            // 比如 n = 1 时，array[n] = array[1] = 1 ,arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
            // 同一行就不要判断， n不断在增加
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }
    /**
     * 输出皇后的位置
     */
    public void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

排序算法

排序是一种数据结构，不是算法，指定的顺序进行排序的过程。

内部排序

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

外部排序

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

常见排序算法

算法时间复杂度

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

事后统计的方法
存在两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；
二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。
事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优

时间频率

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

举例

时间复杂

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

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

计算时间复杂度

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

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

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

————————————————

平方阶：2个 for 循环

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n 2 )＜ Ο(n3 )＜ Ο(nk ) ＜Ο(2n ) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低

常数阶

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)

int i = 2;
int j = 3;
++i;
j++;
int m = i+j;

它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度
对数阶O(log2ⁿ)

int i = 1;
while(i<n){
  i = i*2;
}

在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环 x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为： O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n)

线性阶O(n)

for(i=1,i<=n,i++){
  j =i;
  j++;
}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度
线性对数阶O(nlogN)

for(i=1,i<=n,i++){
  i = 1;
  while(i<n){
    i = i*2;
  }
}

将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
平方阶O(n²)

for(i=1,i<=n,i++){
  for(j=1,j<=n,j++){
    j = i;
    j++;
  }
}

平方阶O(n²)

for(i=1,i<=n,i++){
  for(j=1,j<=n,j++){
    j = i;
    j++;
  }
}

如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n * n)，即 O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m * n)
立方阶O(n³)、K次方阶O(n^k)

平均时间复杂度和最坏时间复杂度

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

空间复杂度

一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元

一、冒泡排序 Bubble Sorting

基本思想

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

优化

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

分析

冒泡数组：3 ，9， -1， 10， -5

使用冒泡排序法将其排成一个从小到大的有序数列
相邻元素逆序就交换

结论

循环次数：数组长度 - 1 次
每一趟排序的次数不断减少
某一趟排序中，没有进行一次交换，则说明是有序排序（优化）

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
 * @author Kcs 2022/9/2
 */
public class BubbleSorting {
    public static void main(String[] args) {
        //排序数组
        int[] array = {3, 9, -1, 10, 20};
        System.out.println("原始冒泡数组：" + Arrays.toString(array));
        bubbleSort(array);
        System.out.println("排序结果：" + Arrays.toString(array));
        // 测试冒泡排序的时间复杂度, 用一个较大的数据进行测试
        int[] test = new int[8000];
        for (int i = 0; i < 8000; i++) {
            test[i] = (int) (Math.random() * 80000);
        }
        Date beforeDate = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String formatBefore = simpleDateFormat.format(beforeDate);
        System.out.println("排序前时间" + formatBefore);
        bubbleSort(test);
        Date afterDate = new Date();
        String afterDateformat = simpleDateFormat.format(afterDate);
        System.out.println("排序前时间" + afterDateformat);
    }
    //封装冒泡方法
    public static void bubbleSort(int[] arr) {
        //表示是否进行交换
        boolean flag = false;
        int temp;
        //第一趟排序
        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]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            // System.out.println("第" + (i + 1) + "次排序结果：" + Arrays.toString(arr));
            if (!flag) {
                //没有发生交换
                break;
            } else {
                //重置flag ,进行下次交换
                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次，得到一个按排序码从小到大排列的有序序列。

分析

原始数组： 101，34，119，1，要求：由小到大

每次执行的得到的结果：

1，34，119，101
1，34，119，101
1，34，101，119

结论

需要执行数组大小 -1轮排序
每一轮都是一个循环，循环的规则（代码）

先假定当前数为最小数，
然后和后面的数进行比较，若当前数更小，重新得到最小数，并得到下标
遍历到数组的最后时，就得到本轮的最小数和下标
交换

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
 * @author Kcs 2022/9/2
 */
public class SelectSorting {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        System.out.println("排序前：" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
        //测试时间
        int[] test = new int[8000];
        for (int i = 0; i < 8000; i++) {
            test[i] = (int) (Math.random() * 80000);
        }
        Date beforeDate = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String formatBefore = simpleDateFormat.format(beforeDate);
        System.out.println("排序前时间" + formatBefore);
        selectSort(test);
        Date afterDate = new Date();
        String afterDateformat = simpleDateFormat.format(afterDate);
        System.out.println("排序前时间" + afterDateformat);
    }
    /**
     * 选择排序
     * 时间复杂度 O(n^2)
     * @param arr
     */
    public static void selectSort(int[] arr) {
        //原始数组 ： 101，34，119，1，要求：由小到大
        for (int i = 0; i < arr.length - 1; i++) {
            //起始索引
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                //由大到小：>  由小到大：< ；当前值进行比较，找出索引
                if (min > arr[j]) {
                    min = arr[j];
                    // 得到最小值索引
                    minIndex = j;
                }
            }
            //最小值放在arr[0]
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            // System.out.println("第" + (i + 1) + "轮排序结果：" + Arrays.toString(arr));
        }
    }
}

三、插入排序

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

基本思想

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

分析

原始数组：101, 34, 119, 1

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
 * @author Kcs 2022/9/3
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, 45, 78};
        System.out.println("排序前结果：" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后结果：" + Arrays.toString(arr));
        // 测试冒泡排序的时间复杂度, 用一个较大的数据进行测试
        int[] test = new int[8000];
        for (int i = 0; i < 8000; i++) {
            test[i] = (int) (Math.random() * 80000);
        }
        Date beforeDate = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String formatBefore = simpleDateFormat.format(beforeDate);
        System.out.println("排序前时间" + formatBefore);
        insertSort(test);
        Date afterDate = new Date();
        String afterDateformat = simpleDateFormat.format(afterDate);
        System.out.println("排序后时间" + afterDateformat);
    }
    /**
     * 插入排序
     */
    public static void insertSort(int[] arr) {
        int insertValue = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            //定义待插入的数
            insertValue = arr[i];
            //arr[1] 前面这个数的索引
            insertIndex = i - 1;
            //insertValue 找到插入的位置  由小到大 < ；由大到小：<
            // insertIndex >= 0 放置越界
            // insertValue < arr[insertIndex] : 带插入的数字
            // arr[insertIndex] 后移
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //找到插入的位置
            if (insertIndex + 1 == i) {
                arr[insertIndex + 1] = insertValue;
            }
            // System.out.println("第" + i + "轮排序结果：" + Arrays.toString(arr));
        }
    }
}

四、希尔排序

基本思想

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

分析

初始数组 {8,9,1,7,2,3,5,4,6,0}

希尔排序时，对有序序列在插入时采用交换法, 并测试排序速度.
希尔排序时，对有序序列在插入时采用移动法, 并测试排序速度

交换法：

import java.util.Arrays;
/**
 * @author Kcs 2022/9/3
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
    }
    /**
     * 希尔排序
     */
    public static void shellSort(int[] arr) {
        int temp = 0;
        int count = 0;
        // 循环处理 希尔排序
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //遍历各组中所有的元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    //当前元素大于加上步长后的元素，则进行交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("第" + (++count) + "轮希尔排序结果：" + Arrays.toString(arr));
        }
    }
}

移步法

import java.util.Arrays;
/**
 * @author Kcs 2022/9/3
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);
        System.out.println("交换法：" + Arrays.toString(arr));
        shellSort2(arr);
        System.out.println("移位法：" + Arrays.toString(arr));
    }
    /**
     * 移位法
     * @param arr
     */
    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从gap个元素，逐个对其所在组进行之直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        // 元素进行移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }
}

五、快速排序

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

左右递归有顺序

import java.util.Arrays;
/**
 * @author Kcs 2022/9/3
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 快速排序
     * @param arr
     */
    public static void quickSort(int[] arr, int left, int right) {
        //左下标
        int l = left;
        //右下标
        int r = right;
        //中轴值
        int pivot = arr[(left + right) / 2];
        //作为交换
        int temp = 0;
        // 比 pivot 小的值 放到左边，大的值放到右边
        while (l < r) {
            //在pivot的左边找，比pivot大于等于的值
            while (arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右边找，比pivot小于等于的值
            while (arr[r] > pivot) {
                r -= 1;
            }
            //左边是小于pivot的值， 右边大于等于pivot的值
            if (l == r) {
                break;
            }
            //进行交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //交换后，发现arr[l] == pivot 值 ,则前移
            if (arr[l] == pivot) {
                r -= 1;
            }
            //交换后，发现arr[r] == pivot 值 ,则后移
            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);
        }
    }
}

六、归并排序

采用分治策略。分治法将问题分 (divide) 成一些小的问题然后递归求解，而治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。

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

分析

上图合并了七次，下图为最后一次的合并详解：

import java.util.Arrays;
/**
 * @author Kcs 2022/9/3
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println("要排序的数组:" + Arrays.toString(arr));
        //归并需要一个额外的空间
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        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) {
        // 初始化i 左边有序序列的初始索引
        int i = left;
        // 初始化 j ,右边有序序列的初始索引
        int j = mid + 1;
        // 指向temp数组的当前索引
        int t = 0;
        // 1. 左右两边的数据，按照规则进行填充到 temp 数组，直到左右两边的有序序列，有一边完成为止
        while (i <= mid && j <= right) {
            //左边的有序序列的当前元素，小于等于右边有序序列的当前元素，即将左边的当前元素，拷贝到 temp 中
            if (arr[i] < arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                // 右边的比左边的元素大，填充到temp数据
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        // 2. 把剩余数据的一边的数据依次全部填充到 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;
        }
        // 3. 将temp 数据的元素拷贝到 arr,并不是每次拷贝所有
        t = 0;
        int tempLeft = left;
        //最后一次 tempLeft = 0 ,right = 7
        System.out.println("tempLeft=" + tempLeft + " " + "right=" + right);
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}

七、基数排序（桶排序）

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort

它是通过键值的各个位的值，将要排序的元素分配至某些 “桶” 中，达到排序的作用。

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法（相同的数字会有先后顺序）

基本思想

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

分析

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。有多少位数就要进行多少次桶排序

说明：事先准备10个数组(10个桶)， 0-9 分别对应位数的 0-9

第1轮排序

将各个数，按照个位大小放入到对应的各个数组中（看每个元素的个位数，把这个多位数，放置在个位数对应的桶中（一个桶一个数组））

然后从 0-9 个数组 / 桶，依次按照加入元素的先后顺序取出

得到结果：542 、53、3、14、214、748

第二轮排序（后一轮是根据上一轮得到的结果进行排序）

将各个数，按照十位大小放入到对应的各个数组 / 桶中
然后从 0-9 个数组 / 桶，依次按照加入元素的先后顺序取出

得到结果：542 、53、3、14、214、748

第二轮排序（后一轮是根据上一轮得到的结果进行排序）

将各个数，按照十位大小放入到对应的各个数组 / 桶中
然后从 0-9 个数组 / 桶，依次按照加入元素的先后顺序取出

import java.util.Arrays;
/**
 * @author Kcs 2022/9/3
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }
    /**
     * 基数排序  时间换空间算法
     * @param arr
     */
    public static void radixSort(int[] arr) {
        //第一轮(每个元素的个位数进行处理)
        //二维数组表示十个桶，每个桶就是一个一维数组
        //防止数据溢出，将一维数组大小为arr.length
        int[][] bucket = new int[10][arr.length];
        //记录桶放入的有效数据中，实际存放的数据。存放bucket[0~10]的对应的数据
        int[] bucketElementCounts = new int[10];
        //得到数组中最大的数的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大的位数
        int maxLength = (max + "").length();
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //取出各位 个 十 百 千 位
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素对应位数的值
                int digitOfElment = arr[j] / n % 10;
                //放入对应的桶中,前一个找到对应的桶，后一个为该个位对应的多位数
                bucket[digitOfElment][bucketElementCounts[digitOfElment]] = arr[j];
                //下一个桶
                bucketElementCounts[digitOfElment]++;
            }
            //依次桶的顺序，依次取出数据，放入原来的数组
            int index = 0;
            //遍历每一个桶，就将桶的数据，放入到原数组中，
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //桶中有数据才放入原数组
                if (bucketElementCounts[k] != 0) {
                    //循环改桶的数据，放入原数组
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入 arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //对桶进行清零
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + (i + 1) + "次排序结果:" + Arrays.toString(arr));
        }
        //以下为推导过程
        /*//第二轮：取出十位
        for (int j = 0; j < arr.length; j++) {
            //得到十位的数 每一轮只要修改这个取模的 个 十 百 千 位
            int digitOfElment = arr[j] / 10 % 10;
            //放入对应的桶中,前一个找到对应的桶，后一个为该个位对应的多位数
            bucket[digitOfElment][bucketElementCounts[digitOfElment]] = arr[j];
            //下一个桶
            bucketElementCounts[digitOfElment]++;
        }
        //依次桶的顺序，依次取出数据，放入原来的数组
        index = 0;
        //遍历每一个桶，就将桶的数据，放入到原数组中，
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //桶中有数据才放入原数组
            if (bucketElementCounts[k] != 0) {
                //循环改桶的数据，放入原数组
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入 arr
                    arr[index++] = bucket[k][l];
                }
            }
            //对桶进行清零
            bucketElementCounts[k] = 0;
        }
        System.out.println("第二轮结果:" + Arrays.toString(arr));
        //第三轮：取出白位
        for (int j = 0; j < arr.length; j++) {
            //得到十位的数 每一轮只要修改这个取模的 个 十 百 千 位
            int digitOfElment = arr[j] / 100;
            //放入对应的桶中,前一个找到对应的桶，后一个为该个位对应的多位数
            bucket[digitOfElment][bucketElementCounts[digitOfElment]] = arr[j];
            //下一个桶
            bucketElementCounts[digitOfElment]++;
        }
        //依次桶的顺序，依次取出数据，放入原来的数组
        index = 0;
        //遍历每一个桶，就将桶的数据，放入到原数组中，
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //桶中有数据才放入原数组
            if (bucketElementCounts[k] != 0) {
                //循环改桶的数据，放入原数组
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入 arr
                    arr[index++] = bucket[k][l];
                }
            }
            //对桶进行清零
            bucketElementCounts[k] = 0;
        }
        System.out.println("第三轮结果:" + Arrays.toString(arr));*/
    }
}

排序算法对比

解释：

稳定：如果 a原本在 b前面，而a=b ，排序之后 a仍然在 b的前面；

不稳定：如果 a原本在 b的前面，而 a=b，排序之后 a可能会出现在 b的后面；

内排序：所有排序操作都在内存中完成；

外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度：一个算法执行所耗费的时间。

空间复杂度：运行完一个程序所需内存的大小。

n：数据规模

k：“桶”的个数

In -place：不占用额外内存

Out -place：占用额外内存

查找算法

顺序（线性查找）查找

从头到尾一个一个进行对比查找，找到则返回下标

/**
 * @author Kcs 2022/9/5
 */
public class SequenceSearch {
    public static void main(String[] args) {
        //数组
        int[] arr = {1 ,-25, 45, 32, 3, 0, 12, -20};
        int index = seqSearch(arr, 0);
        if (index == -1) {
            System.out.println("查无次数据");
        } else {
            System.out.println("该数字位于:" + index);
        }
    }
    /**
     * 找到一个就返回
     * @param arr 匹配数组
     * @param value 要查找的数
     * @return index
     */
    public static int seqSearch(int[] arr, int value) {
        //逐一比对
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

二分查找 / 折半查找

必须是顺序的数组，若是无序的，则需要先排序（小到大 / 大到小）

思路

（以下是排序已为由小到大）

首先确定该数组的中间下标

mid = （left + right）/ 2

然后让需要查找的数 findValue 和 arr[mid] 进行比较

findValue > mid[arr] ：说明要查找的数在 mid 的右边，应该向右查找（向右递归查找）

findValue < mid[arr] ：说明要查找的数在 mid 的左边，应该向左查找（向左递归查找）

findValue = mid[arr] ：说明已经找到，则返回

退出递归

找到目标退出递归

找不到退出递归（left > right）

/**
 * @author Kcs 2022/9/5
 */
public class BinarySearch {
    public static void main(String[] args) {
        //有序数组
        int[] arr = {0, 11, 22, 33, 44, 45, 55, 77, 88, 88, 88, 88, 99};
        // int index = binarySearch(arr, 0, arr.length - 1, 12);
        // System.out.println("index=" + index);
        List<Integer> integers = binarySearch2(arr, 0, arr.length - 1, 99);
        System.out.println(integers);
    }
    /**
     * 二分查找算法
     * @param arr 查找数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findValue 查找的值
     * @return index
     */
    public static int binarySearch(int[] arr, int left, int right, int findValue) {
        //没有找到
        if (left > right) {
            return -1;
        }
        //中间索引
        int mid = (left + right) / 2;
        //中间值
        int midValue = arr[mid];
        //判断递归的方向
        //向右
        if (findValue > midValue) {
            return binarySearch(arr, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return binarySearch(arr, left, mid - 1, findValue);
        } else {
            //查找到所有相同的值，并返回
            return mid;
        }
    }
    /**
     * 查找重复的值索引
     * @param arr
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findValue) {
        //没有找到
        if (left > right) {
            return new ArrayList<Integer>();
        }
        //中间索引
        int mid = (left + right) / 2;
        //中间值
        int midValue = arr[mid];
        //判断递归的方向
        //向右
        if (findValue > midValue) {
            return binarySearch2(arr, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return binarySearch2(arr, left, mid - 1, findValue);
        } else {
            ArrayList<Integer> resIndexlist = new ArrayList<>();
            int temp = mid - 1;
            //向mid左边开始继续搜索
            while (true) {
                //退出
                if (temp < 0 || arr[temp] != findValue) {
                    break;
                }
                resIndexlist.add(temp);
                temp -= 1;
            }
            resIndexlist.add(mid);
            //向mid右边继续搜索
            temp = mid + 1;
            while (true) {
                if (temp > (arr.length - 1) || arr[temp] != findValue) {
                    break;
                }
                resIndexlist.add(temp);
                temp += 1;
            }
            return resIndexlist;
        }
    }
}

插值查找

也是得用在有序数组上

插值查找每次从自适应mid处开始查找

将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是 findValue

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

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

特点

可以一次就能查找想要的结果
与二分查找相比，想过肯定的好很多的

使用场景

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快
关键字分布不均匀的情况下，该方法不一定比折半查找要好

/**
 * @author Kcs 2022/9/6
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        //1 ~ 100 数组
        int[] array = new int[100];
        for (int i = 0; i < 100; i++) {
            array[i] = i + 1;
        }
        int index = insertValueSearch(array, 0, array.length - 1, 50);
        System.out.println("index = " + index);
    }
    /**
     * 插值查找算法
     * @param array 查找的数组
     * @param left 左边 索引
     * @param right 右边索引
     * @param findValue 查找的值
     * @return index
     */
    public static int insertValueSearch(int[] array, int left, int right, int findValue) {
        System.out.println("查找了！！！！");
        //不符合，则退出 优化查找，防止mid越界。自适应的查找
        if (left > right || findValue < array[0] || findValue > array[array.length - 1]) {
            return -1;
        }
        //求出mid
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);
        //中间的值
        int midValue = array[mid];
        if (findValue > midValue) {
            //向右递归查找
            return insertValueSearch(array, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            //向左递归查找
            return insertValueSearch(array, left, mid - 1, findValue);
        } else {
            //相等
            return mid;
        }
    }
}

斐波那契查找

斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ···} 发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618

原理

mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1 （F代表斐波那契数列）

由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1

顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到 F[k]-1位置），都赋为n位置的值即可

分析

有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234}

import java.util.Arrays;
/**
 * @author Kcs 2022/9/7
 */
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(fibSearch(arr, 8));
    }
    /**
     * 20个斐波那契数列
     * @return f[]
     */
    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 index
     */
    public static int fibSearch(int[] a, int key) {
        //左边下标
        int low = 0;
        //右边下标
        int high = a.length - 1;
        //斐波那契分割数值的下标
        int k = 0;
        //mid
        int mid = 0;
        //获取斐波那契数列
        int[] f = fib();
        while (high > f[k] - 1) {
            k++;
        }
        //防止f[k] 大于 数组的长度,不足的时候使用 0 填充
        int[] temp = Arrays.copyOf(a, f[k]);
        //不使用0 进行填充，使用 arr数组的最后一位进行填充
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        //查找目标值
        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {
                //查找前半部分（左边）
                high = mid - 1;
                k--;
            } else if (key > temp[mid]) {
                //向右边查找
                low = mid + 1;
                //f[k-1] = f[k -3]+f[k -4]
                k -= 2;
            } else {
                //查找到
                if (mid <= high) {
                    //左边mid
                    return mid;
                } else {
                    //右边的index
                    return high;
                }
            }
        }
        //没有找到
        return -1;
    }
}

哈希表

哈希表属于数据结构

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

哈希表

思路

有一个公司,当有新的员工来报道时,要求将该员工的信息加入 (id,名字，···),当输入该员工的id时,要求查找到该员工的所有信息

要求

不使用数据库,速度越快越好=>哈希表(散列)
添加时，保证按照id从低到高插入

实现思路

使用链表来实现哈希表, 该链表不带表头 [即: 链表的第一个结点就存放雇员信息]

代码实现[增删改查(显示所有员工，按id查询)]

散列函数

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：

计算哈希函数所需时间
关键字的长度
哈希表的大小
关键字的分布情况
记录的查找频率

散列函数的几种方法

直接寻址法
数字分析法
平方取中法
折叠法
随机数法
除留余数法

创建三个类

雇员类：雇员的信息
雇员链表类：管理雇员
哈希表类：存放 n个雇员，散列函数：使 id 对应的链表

import java.util.Scanner;
/**
 * @author Kcs 2022/9/9
 */
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("delete：删除雇员");
            System.out.println("exit：退出系统");
            System.out.println("请选择add/list/find/delete/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);
                    System.out.println("添加成功！");
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找雇员的id");
                    id = scanner.nextInt();
                    hashTab.findEmpByID(id);
                    System.out.println("查找成功！");
                    break;
                case "delete":
                    System.out.println("请输入要删除雇员的id");
                    id = scanner.nextInt();
                    hashTab.delEmp(id);
                    System.out.println("删除成功！");
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    System.out.println("成功退出！");
                    break;
                default:
                    break;
            }
        }
    }
}
/**
 * 雇员类
 */
class Emp {
    /**
     * id
     */
    public int id;
    /**
     * 姓名
     */
    public String name;
    /**
     * next : null
     */
    public Emp next;
    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
/**
 * 哈希表 管理雇员
 */
class HashTab {
    //数组存放雇员信息
    private EmpLinkedList[] empLinkedListsArray;
    //链表总数
    private int size;
    /**
     * 构造
     * @param size 多少链表
     */
    public HashTab(int size) {
        this.size = size;
        //初始化 empLinkedListsArray
        empLinkedListsArray = new EmpLinkedList[size];
        //初始化每个链表
        for (int i = 0; i < size; i++) {
            empLinkedListsArray[i] = new EmpLinkedList();
        }
    }
    /**
     * 添加雇员
     */
    public void add(Emp emp) {
        //根据id 获得该员工的应该添加到的那一条链表
        int empLinkedListNo = hashFun(emp.id);
        // 添加到对应的链表种
        empLinkedListsArray[empLinkedListNo].add(emp);
    }
    /**
     * 遍历所有链表
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListsArray[i].list(i);
        }
    }
    /**
     * 根据id 查找雇员
     */
    public void findEmpByID(int id) {
        //散列函数确定查找的链表
        int empLinkedListNo = hashFun(id);
        Emp emp = empLinkedListsArray[empLinkedListNo].findEmpById(id);
        if (emp != null) {
            System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id);
        } else {
            System.out.println("在哈希表中，没有找到该雇员！");
        }
    }
    /**
     * 删除雇员信息
     * @param id 雇员id
     */
    public void delEmp(int id) {
        int i = hashFun(id);
        empLinkedListsArray[i].delete(id);
    }
    /**
     * 散列函数 取模
     */
    public int hashFun(int id) {
        return id % size;
    }
}
/**
 * 创建EmpLinkedList，表示链表
 */
class EmpLinkedList {
    /**
     * 头指针，指向第一个雇员的Emp
     */
    private Emp head;
    /**
     * 添加雇员
     * 添加的雇员id 自增长，id 总是从小到大，所有将该雇员添加到本链表的最后
     */
    public void add(Emp emp) {
        //第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //不是第一个雇员,添加到链表最后
        Emp curEmp = head;
        while (true) {
            //到链表最后
            if (curEmp.next == null) {
                break;
            }
            //后移
            curEmp = curEmp.next;
        }
        //退出时，加入链表
        curEmp.next = emp;
    }
    /**
     * 遍历链表
     */
    public void list(int num) {
        //链表为空
        if (head == null) {
            System.out.println("第" + (num + 1) + "个链表为空!");
            return;
        }
        System.out.print("第" + (num + 1) + "链表的信息为：");
        Emp curEmp = head;
        while (true) {
            System.out.printf("=> id = %d ,name=%s\t", curEmp.id, curEmp.name);
            //curEmp到最后结点
            if (curEmp.next == null) {
                break;
            }
            //指针后移
            curEmp = curEmp.next;
        }
        System.out.println();
    }
    /**
     * 通过id查找雇员信息
     * @param id 雇员id
     * @return 雇员信息
     */
    public Emp findEmpById(int id) {
        //链表是否为空
        if (head == null) {
            System.out.println("链表为空！");
            return null;
        }
        Emp curEmp = head;
        //id 不重复
        while (true) {
            if (curEmp.id == id) {
                //curEmp指向要查找的雇员
                break;
            }
            //退出
            if (curEmp.next == null) {
                //没有找到该雇员的信息
                curEmp = null;
            }
            //后移
            curEmp = curEmp.next;
        }
        return curEmp;
    }
    /**
     * 根据id删除雇员信息
     * @param id
     */
    public void delete(int id) {
        if (head == null) {
            System.out.println("链表为空,无须删除");
            return;
        }
        if (head.id == id) {
            //头节点为空
            if (head.next == null) {
                head = null;
            } else {
                //后移
                head = head.next;
            }
            return;
        }
        //辅助指针
        Emp curEmp = head;
        boolean flag = false;
        while (true) {
            if (head.id == id) {
                head = head.next;
                return;
            }
            if (curEmp.next.id == id) {
                flag = true;
                break;
            }
            if (flag) {
                curEmp.next = curEmp.next.next;
            } else {
                System.out.println("要删除的雇员不存在");
            }
            curEmp = curEmp.next;
        }
    }
}

w EmpLinkedList();

}

/**
 * 添加雇员
 */
public void add(Emp emp) {
    //根据id 获得该员工的应该添加到的那一条链表
    int empLinkedListNo = hashFun(emp.id);
    // 添加到对应的链表种
    empLinkedListsArray[empLinkedListNo].add(emp);
}
/**
 * 遍历所有链表
 */
public void list() {
    for (int i = 0; i < size; i++) {
        empLinkedListsArray[i].list(i);
    }
}
/**
 * 根据id 查找雇员
 */
public void findEmpByID(int id) {
    //散列函数确定查找的链表
    int empLinkedListNo = hashFun(id);
    Emp emp = empLinkedListsArray[empLinkedListNo].findEmpById(id);
    if (emp != null) {
        System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id);
    } else {
        System.out.println("在哈希表中，没有找到该雇员！");
    }
}
/**
 * 删除雇员信息
 * @param id 雇员id
 */
public void delEmp(int id) {
    int i = hashFun(id);
    empLinkedListsArray[i].delete(id);
}
/**
 * 散列函数 取模
 */
public int hashFun(int id) {
    return id % size;
}

}
/**
创建EmpLinkedList，表示链表
/
class EmpLinkedList {
/*
头指针，指向第一个雇员的Emp
*/
private Emp head;
/**
添加雇员
添加的雇员id 自增长，id 总是从小到大，所有将该雇员添加到本链表的最后
*/
public void add(Emp emp) {
//第一个雇员
if (head == null) {
head = emp;
return;
}
//不是第一个雇员,添加到链表最后
Emp curEmp = head;
while (true) {
//到链表最后
if (curEmp.next == null) {
break;
}
//后移
curEmp = curEmp.next;
}
//退出时，加入链表
curEmp.next = emp;
}
/**
遍历链表
*/
public void list(int num) {
//链表为空
if (head == null) {
System.out.println(“第” + (num + 1) + “个链表为空!”);
return;
}
System.out.print(“第” + (num + 1) + “链表的信息为：”);
Emp curEmp = head;
while (true) {
System.out.printf(“=> id = %d ,name=%s\t”, curEmp.id, curEmp.name);
//curEmp到最后结点
if (curEmp.next == null) {
break;
}
//指针后移
curEmp = curEmp.next;
}
System.out.println();
}
/**
通过id查找雇员信息
@param id 雇员id
@return 雇员信息
*/
public Emp findEmpById(int id) {
//链表是否为空
if (head == null) {
System.out.println(“链表为空！”);
return null;
}
Emp curEmp = head;
//id 不重复
while (true) {
if (curEmp.id == id) {
//curEmp指向要查找的雇员
break;
}
//退出
if (curEmp.next == null) {
//没有找到该雇员的信息
curEmp = null;
}
//后移
curEmp = curEmp.next;
}
return curEmp;
}
/**
根据id删除雇员信息
@param id
*/
public void delete(int id) {
if (head == null) {
System.out.println(“链表为空,无须删除”);
return;
}
if (head.id == id) {
//头节点为空
if (head.next == null) {
head = null;
} else {
//后移
head = head.next;
}
return;
}
//辅助指针
Emp curEmp = head;
boolean flag = false;
while (true) {
if (head.id == id) {
head = head.next;
return;
}
if (curEmp.next.id == id) {
flag = true;
break;
}
if (flag) {
curEmp.next = curEmp.next.next;
} else {
System.out.println(“要删除的雇员不存在”);
}
curEmp = curEmp.next;
}
}
}

Java数据结构与算法 一3

递归

规范

递归 - 迷宫回溯问题

八皇后问题（92种）

分析

排序算法

内部排序

外部排序

常见排序算法

算法时间复杂度

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

时间频率

举例

时间复杂

平均时间复杂度和最坏时间复 杂度

空间复杂度

一、冒泡排序 Bubble Sorting

基本思想

优化

分析

结论

二、选择排序 （Select Sorting）

思路

分析

结论

三、插入排序

基本思想

分析

四、希尔排序

基本思想

分析

五、快速排序

基本思想

六、归并排序

分析

七、基数排序（桶排序）

基本思想

分析

排序算法对比

解释：

查找算法

顺序（线性查找）查找

二分查找 / 折半查找

插值查找

使用场景

斐波那契查找

原理

分析

哈希表

哈希表

思路

要求

实现思路

散列函数

散列函数的几种方法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

Java数据结构与算法一3

平均时间复杂度和最坏时间复杂度

二、选择排序（Select Sorting）