2020-01-12

数据结构和算法

2 小时读完 (大约 14734 个字)

算法入门

内容概要：

算法初识
排序算法
查找算法
常用的算法
其他算法小案例

算法初识

算法的度量

时间频度

基本介绍

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

时间频度举例

比如 计算 1-100 所有数字之和 ，我们设计了 两种算法 ：

// 01-第一种算法时间频度： T(n) = n + 1
int total = 0;
int end = 100;
for(int i = 1; i < end; i++){
    total += i;
}

// 02-第二种算法时间频度： T(n) = 1
total = (1 + end) * end / 2;

注意事项

第一： 常数项能够被忽略 ，如下图：

第二： 低次项能够被忽略 ，如下图：

第三： 系数能够被忽略 ，如下图：

时间复杂度

基本概念

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

TIPS：

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

计算方法

用常数 1 代替运行时间中的所有加法常数： T(n) = 3n²+7n+6 => T(n) = 3n²+7n+1
修改后的运行次数函数中，只保留最高阶项： T(n)=3n²+7n+1 => T(n) = 3n²
去除最高阶项的系数： T(n) = 3n² => T(n) = n² => O(n²)

常见的时间复杂度

常见的时间复杂度 如下图：

常数阶 举例：

对数阶 举例：

线性阶 举例：

线性对数阶 举例：

平方阶 举例：

平均 / 最坏时间复杂度

平均时间复杂度 和 最坏时间复杂度 的解释都在图中：

空间复杂度

排序算法

先看一张图，了解 排序算法 ：

以下是 十大排序算法 ，每种算法都分析了 平均时间复杂度 、最好情况 、最坏情况 、空间复杂度 、排序方式和稳定性 。详情参考下图：

冒泡排序

基本介绍

在一个数组中，相邻两个元素进行对比，小的放在前，大的放在后，第一轮比完就找到了最大的数并且放在最后。依此类推，直到排序完成。

冒泡排序图解

静态图解：

动态图解：

代码实现标准版

public class Main {

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

}

代码实现升级版

public static void bubbleSort(int[] arr) {
    // 01-定义一个标志，判断数组相邻位置是否发生交换
    boolean flag = false;

    // 02-对数组进行判断
    if (arr == null || arr.length < 2) {
        return;
    }

    // 03-冒泡排序开始
    for (int i = arr.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 04-进入 if 判断，说明数组相邻位置发生了交换，将 flag 置为 true
                flag = true;
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j + 1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
            }
        }
        System.out.println("第" + (arr.length - i) + "趟排序");
        System.out.println(Arrays.toString(arr));

        // 05-如果 flag != true ，说明没有进入 if 判断语句，即相邻位置没有发生交换，那么数组已经排好序了，那么 break 跳出循环。
        if(flag){
            flag = false;
        } else {
            break;
        }
    }
}

算法测试

public static void main(String[] args) {
    // 创建一个数组，并给数组赋随机值
    int[] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 1000 + 1);
    }

    long start = System.currentTimeMillis();
    bubbleSort(arr);
    long end = System.currentTimeMillis();
    System.out.println("排序 10 万个数据需要 " + (end - start) / 1000 + " 秒！");
}

public static void bubbleSort(int[] arr) {
    // 01-定义一个标志，判断数组相邻位置是否发生交换
    boolean flag = false;

    // 02-对数组进行判断
    if (arr == null || arr.length < 2) {
        return;
    }

    // 03-冒泡排序开始
    for (int i = arr.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 04-进入 if 判断，说明数组相邻位置发生了交换，将 flag 置为 true
                flag = true;
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j + 1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
            }
        }
        //System.out.println("第" + (arr.length - i) + "趟排序");
        //System.out.println(Arrays.toString(arr));

        // 05-如果 flag != true ，说明没有进入 if 判断语句，即相邻位置没有发生交换，那么数组已经排好序了，那么 break 跳出循环。
        if(flag){
            flag = false;
        } else {
            break;
        }
    }
}

冒泡排序总结：
标准版是最好的代码，后面的升级版只适用于数据量比较小的情况，如果数据量比较大，比如算法测试的 10 万个数据，标准版代码 23 秒左右，而升级版是 25 秒左右，慢了几秒钟。原因是大量的判断浪费了时间！！！

选择排序

基本介绍

选择排序就是在未排序的数组中，第一个元素和它以后的每一个元素进行比较，若第一个元素大于第 i 个元素，那么两元素交换位置。然后第一个元素继续和第 i + 1 个元素比较，直到结束。第一次比较后的结果找到了最小的数并放在数组第一个位置。后面从第二个数开始和它以后的数比较，以此类推，直到排序完成。

选择排序图解

代码实现标准版

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                int temp;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

代码测试版

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
//选择排序
public class SelectSort {

    public static void main(String[] args) {
        //int [] arr = {101, 34, 119, 1, -1, 90, 123};

        //创建要给80000个的随机的数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        }

        System.out.println("排序前");
        //System.out.println(Arrays.toString(arr));

        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);

        selectSort(arr);


        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);

        //System.out.println("排序后");
        //System.out.println(Arrays.toString(arr));


    }

    //选择排序
    public static void selectSort(int[] arr) {

        //在推导的过程，我们发现了规律，因此，可以使用for来解决
        //选择排序时间复杂度是 O(n^2)
        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]; // 重置min
                    minIndex = j; // 重置minIndex
                }
            }

            // 将最小值，放在arr[0], 即交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }

            //System.out.println("第"+(i+1)+"轮后~~");
            //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
        }
    }

}

总结：经过综合测试，选择排序的效率比冒泡的效率高。

插入排序

基本介绍

插入排序图解

代码实现

public static void insertSort(int[] arr){
    for (int i = 1; i < arr.length; i++) {
        // 01-定义待插入的数
        int insertValue = arr[i];
        // 02-定义 insertValue 前一个数的索引
        int insertIndex = i - 1;
        while (insertIndex >= 0 && insertValue < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        // 03-当退出 while 循环，代表 insertValue > arr[insertIndex] ，所以应该把插入值放到 arr[insertIndex + 1] 的位置
        arr[insertIndex + 1] = insertValue;
    }
}

总结：三种排序的效率：插入排序 > 选择排序 > 冒泡排序。

希尔排序

问题引入

基本介绍

希尔排序图解

静态图解：

动态图解：

代码实现

采用 交换法 实现希尔排序：

public static void shellSort(int[] arr){
    int temp;
    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;
                }
            }
        }
    }
}

采用 移动法 实现希尔排序：

public static void shellSort2(int[] arr){
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        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;
            }
        }
    }
}

总结一下：交换法实现的希尔排序表插入排序还慢，并且慢好多。然后，重点来了，移动法实现的希尔排序那牛的一批，排序速度非常非常非常快。用数据说话：8万个数据插入排序 2 ~ 3 秒，800万数据十多分钟；希尔排序 8万个数据 10多毫秒，800万个数据 2 ~ 3 秒。我服了！！！

快速排序

基本介绍

快速排序图解

代码实现

public static void quickSort(int[] arr, int left, int right) {
    // 左边下标
    int lt = left;
    // 右边下标
    int rt = right;
    // 中轴值
    int pivot = arr[(left + right) / 2];
    // 定义临时变量
    int temp;

    // while 循环目的：让比 pivot 小的数在其左边，大的数在其右边
    while (lt < rt){
        // 在 pivot 左边一直找，找到比 pivot 大就退出 while 循环
        while (arr[lt] < pivot){
            lt += 1;
        }

        // 在 pivot 右边一直找，找到比 pivot 小就退出 while 循环
        while (arr[rt] > pivot){
            rt -= 1;
        }

        if(lt >= rt){
            break;
        }

        temp = arr[lt];
        arr[lt] = arr[rt];
        arr[rt] = temp;

        if(arr[lt] == pivot){
            rt--;
        }

        if(arr[rt] == pivot){
            lt++;
        }
    }

    if(lt == rt){
        lt++;
        rt--;
    }

    // 向左递归
    if(left < rt){
        quickSort(arr, left, rt);
    }

    // 向右递归
    if(right > lt){
        quickSort(arr, lt, right);
    }
}

归并排序

基本介绍

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

归并排序图解

静态图解：

动态图解：

代码实现

public static void main(String[] args) {
    int[] arr = new int[30];
    int[] temp = new int[arr.length];
    for (int i = 0; i < 30; i++) {
        arr[i] = (int) (Math.random() * 70 + 10);
    }

    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;
        // Left recursion(左递归)
        mergeSort(arr, left, mid, temp);
        // right recursion(右递归)
        mergeSort(arr, mid + 1, right, temp);
        // merge(合并)
        mergeSort(arr, left, mid, right, temp);
    }
}

// 归并排序之合并过程
public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;
    int j = mid + 1;
    int t = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else {
            temp[t] = arr[j];
            t++;
            j++;
        }
    }

    while (i <= mid) {
        temp[t] = arr[i];
        t++;
        i++;
    }

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

    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

基数排序

基本介绍

基数排序图解

静态图解：

动态图解：

代码实现

public static void redixSort(int[] arr) {

    // 00-得到数组中最大的数的位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int maxLength = (max + "").length();    // 得到最大位数是几位数

    // 01-定义一个二位数组  代表桶
    int[][] bucket = new int[10][arr.length];

    // 02-定义一个数组  记录桶中数据个数
    int[] counts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        for (int j = 0; j < arr.length; j++) {
            int element = arr[j] / n % 10;
            bucket[element][counts[element]] = arr[j];
            counts[element]++;
        }

        int index = 0;
        // 03-遍历每一个桶，并把桶中的数据放回到原数组
        for (int k = 0; k < bucket.length; k++) {
            // 04-如果桶中有数据，我们才放入到原数组
            if (counts[k] != 0) {
                for (int m = 0; m < counts[k]; m++) {
                    arr[index++] = bucket[k][m];
                }
            }
            counts[k] = 0;
        }
    }
}

基数排序说明

堆排序

基本介绍

堆排序 是一种选择排序 ，是利用 堆 这种数据结构而设计的一种排序算法。具体介绍如下图：

堆排序图解

代码实现

堆排序 的代码实现如下：

/**
 * @Author: guoshizhan
 * @Create: 2020/7/4 22:53
 * @Description: 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {

        // 要求堆数组进行升序排序
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);

    }

    // 编写一个堆排序方法
    public static void heapSort(int[] arr) {

        int temp = 0;
        System.out.println("堆排序！");

        // 将无序序列构成堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

        System.out.println(Arrays.toString(arr));  // [4, 5, 6, 8, 9]

    }

    /**
     * 将一个数组（二叉树）调整成大顶堆
     *
     * @param arr    代表待调整数组
     * @param i      代表非叶子节点再数组中的索引
     * @param length 表示堆多少个数组继续调整，length 是逐渐减少的
     */
    public static void adjustHeap(int[] arr, int i, int length) {

        int temp = arr[i];    // 取出当前元素的值，保存于 temp 中

        // 开始调整。k 是 i 节点的左子节点
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            if ((k + 1) < length && arr[k] < arr[k + 1]) { // 说明左子节点小于右子节点
                k++;
            }
            if (arr[k] > temp) {     // 如果子节点大于父节点
                arr[i] = arr[k];   // 把较大的值赋给当前节点
                i = k;             // i 指向 k ，继续比较
            } else {
                break;
            }
        }
        // 当 for 循环结束后，我们已经将以 i 为父节点的树的最大值放到了最顶（局部，还不一定是大顶堆）

        arr[i] = temp;

    }
}

排序算法性能测试

public static void main(String[] args) {

    // 创建一个 80000 个的随机的数组
    int[] arr = new int[80000];
    int[] temp = new int[arr.length];

    for (int i = 0; i < 80000; i++) {
        arr[i] = (int) (Math.random() * 8000 + 1);   // 生成一个[0, 8000] 数
    }

    long start = System.currentTimeMillis();

    //bubbleSort(arr);    // 排序 8万数据 需要的时间 = 11 秒 600 毫秒左右
    //selectSort(arr);    // 排序 8万数据 需要的时间 = 2 秒 700 毫秒左右
    //insertSort(arr);    // 排序 8万数据 需要的时间 = 1 秒 800 毫秒左右
    //shellSort(arr);     // 排序 8万数据 需要的时间 = 6 秒 800 毫秒左右
    //shellSort2(arr);    // 排序 8万数据 需要的时间 = 0 秒 16 毫秒左右
    //quickSort(arr, 0, arr.length - 1);    // 排序 8万数据 需要的时间 = 0 秒 13 毫秒左右
    //mergeSort(arr, 0, arr.length - 1, temp);    // 排序 8万数据 需要的时间 = 0 秒 13 毫秒左右
    //redixSort(arr);    // 排序 8万数据 需要的时间 = 0 秒 10 毫秒
    //heapSort(arr);     // 排序 8万数据 需要的时间 = 0 秒 10 毫秒

    long end = System.currentTimeMillis();
    System.out.println("排序 8万数据 需要的时间 = " + (end - start) / 1000 + " 秒 " + (end - start) % 1000 + " 毫秒");

}
// 01-冒泡排序
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 02-选择排序
public static void selectSort(int[] arr) {

    //在推导的过程，我们发现了规律，因此，可以使用for来解决
    //选择排序时间复杂度是 O(n^2)
    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]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }

        // 将最小值，放在arr[0], 即交换
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }

        //System.out.println("第"+(i+1)+"轮后~~");
        //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
    }
}

// 03-插入排序
public static void insertSort(int[] arr){
    for (int i = 1; i < arr.length; i++) {
        // 01-定义待插入的数
        int insertValue = arr[i];
        // 02-定义 insertValue 前一个数的索引
        int insertIndex = i - 1;
        while (insertIndex >= 0 && insertValue < arr[insertIndex]){
            // 03-如果插入值比它前一个数大，那就没有必要再比较了，直接进入下一轮比较【自己加的代码】
            if(insertValue > arr[insertIndex]){
                break;
            }
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }

        arr[insertIndex + 1] = insertValue;
    }
}

// 04-希尔排序
public static void shellSort(int[] arr){
    int temp;
    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;
                }
            }
        }
    }
}

// 04-希尔排序移位版
public static void shellSort2(int[] arr){
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        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;
            }
        }
    }
}

// 05-快速排序
public static void quickSort(int[] arr, int left, int right) {
    // 左边下标
    int lt = left;
    // 右边下标
    int rt = right;
    // 中轴值
    int pivot = arr[(left + right) / 2];
    // 定义临时变量
    int temp;

    // while 循环目的：让比 pivot 小的数在其左边，大的数在其右边
    while (lt < rt){
        // 在 pivot 左边一直找，找到比 pivot 大就退出 while 循环
        while (arr[lt] < pivot){
            lt += 1;
        }

        // 在 pivot 右边一直找，找到比 pivot 小就退出 while 循环
        while (arr[rt] > pivot){
            rt -= 1;
        }

        if(lt >= rt){
            break;
        }

        temp = arr[lt];
        arr[lt] = arr[rt];
        arr[rt] = temp;

        if(arr[lt] == pivot){
            rt--;
        }

        if(arr[rt] == pivot){
            lt++;
        }
    }

    if(lt == rt){
        lt++;
        rt--;
    }

    // 向左递归
    if(left < rt){
        quickSort(arr, left, rt);
    }

    // 向右递归
    if(right > lt){
        quickSort(arr, lt, right);
    }
}

// 06-归并排序
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        // Left recursion(左递归)
        mergeSort(arr, left, mid, temp);
        // right recursion(右递归)
        mergeSort(arr, mid + 1, right, temp);
        // merge(合并)
        mergeSort(arr, left, mid, right, temp);
    }
}

// 归并排序之合并过程
public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;
    int j = mid + 1;
    int t = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else {
            temp[t] = arr[j];
            t++;
            j++;
        }
    }

    while (i <= mid) {
        temp[t] = arr[i];
        t++;
        i++;
    }

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

    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

// 07-基数排序
public static void redixSort(int[] arr) {

    // 00-得到数组中最大的数的位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int maxLength = (max + "").length();    // 得到最大位数是几位数

    // 01-定义一个二位数组  代表桶
    int[][] bucket = new int[10][arr.length];

    // 02-定义一个数组  记录桶中数据个数
    int[] counts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        for (int j = 0; j < arr.length; j++) {
            int element = arr[j] / n % 10;
            bucket[element][counts[element]] = arr[j];
            counts[element]++;
        }

        int index = 0;
        // 03-遍历每一个桶，并把桶中的数据放回到原数组
        for (int k = 0; k < bucket.length; k++) {
            // 04-如果桶中有数据，我们才放入到原数组
            if (counts[k] != 0) {
                for (int m = 0; m < counts[k]; m++) {
                    arr[index++] = bucket[k][m];
                }
            }
            counts[k] = 0;
        }
    }
}

// 08-堆排序
// 编写一个堆排序方法
public static void heapSort(int[] arr) {

    int temp = 0;
    System.out.println("堆排序！");

    // 将无序序列构成堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }

    for (int j = arr.length - 1; j > 0; j--) {
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, j);
    }

    System.out.println(Arrays.toString(arr));  // [4, 5, 6, 8, 9]

}

/**
 * 将一个数组（二叉树）调整成大顶堆
 *
 * @param arr    代表待调整数组
 * @param i      代表非叶子节点再数组中的索引
 * @param length 表示堆多少个数组继续调整，length 是逐渐减少的
 */
public static void adjustHeap(int[] arr, int i, int length) {

    int temp = arr[i];    // 取出当前元素的值，保存于 temp 中

    // 开始调整。k 是 i 节点的左子节点
    for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
        if ((k + 1) < length && arr[k] < arr[k + 1]) { // 说明左子节点小于右子节点
            k++;
        }
        if (arr[k] > temp) {     // 如果子节点大于父节点
            arr[i] = arr[k];   // 把较大的值赋给当前节点
            i = k;             // i 指向 k ，继续比较
        } else {
            break;
        }
    }
    // 当 for 循环结束后，我们已经将以 i 为父节点的树的最大值放到了最顶（局部，还不一定是大顶堆）

    arr[i] = temp;

}

查找算法

查找 是在大量的信息中寻找一个特定的信息元素。在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。【————百度百科】本文简单介绍了 常见的五种查找算法 ，线性查找 、二分查找 、插值查找 、斐波那契查找 和 哈希查找 。

线性查找

线性查找 也称为 顺序查找 ，查找过程为 ：从表中的 最后一个/第一个记录开始 ，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若 直到第一个/最后一个 记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。

查找一个值

查找结果只有一个值 的情况，详情看代码：

public static void main(String[] args) {

    int[] arr = {-3, 5, 10, 13, 10, 10, 17, 10, 34, 54, 10, 60};
    int index = linearSearchOne(arr, 17);

    if (index == -1) {
        System.out.println("没有查到哦~~~");
    } else {
        System.out.println("找到了，下标为：" + index);
    }

}


// 线性查找（单个值）
public static int linearSearchOne(int[] arr, int target) {

    if (arr == null) {
        return -1;
    }

    // 线性查找是逐一比对，发现有相同值，就返回下标，没找到，返回 -1
    for (int i = 0; i < arr.length; i++) {
        if (target == arr[i]) {
            return i;
        }
    }

    return -1;

}

查找多个值

查找结果有多个值 的情况，详情看代码：

public static void main(String[] args) {

    int[] arr = {-3, 5, 10, 13, 10, 10, 17, 10, 34, 54, 10, 60};
    List<Integer> list = linearSearchMore(arr, 10);
    System.out.println(list);

}


// 线性查找（多个值）
public static List<Integer> linearSearchMore(int[] arr, int target) {

    // 创建集合存储索引
    List<Integer> list = new ArrayList<>();

    if (arr == null) {
        return list;
    }

    // 线性查找是逐一比对，发现有相同值，就把下标加入到集合里
    for (int i = 0; i < arr.length; i++) {
        if (target == arr[i]) {
            list.add(i);
        }
    }

    return list;

}

二分查找

二分查找 也称 折半查找（Binary Search） ，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。【————百度百科】二分查找优点： 比较次数少，查找速度快，平均性能好。 二分查找缺点： 要求待查表为有序表，且插入删除困难。 适用范围： 适用于不经常变动而查找频繁的有序列表 。

算法复杂度：

假设其数组长度为 n ，其算法复杂度为 O（log（n））。

算法思想：

首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

二分查找-递归

二分查找递归图解：

二分查找-递归（只查找一个值） 代码实现：

public static void main(String[] args) {

    int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int res = binarySearchOne(arr, 0, arr.length - 1, 10);
    System.out.println(res);

}

// 二分查找，折半查找算法（只有一个值）
public static int binarySearchOne(int[] arr, int left, int right, int target) {

    // 当数组为空或 left > right 时，说明递归整个数组，但是没有找到，返回 -1
    if (arr == null || left > right) {
        return -1;
    }

    int mid = (left + right) / 2;
    int midVal = arr[mid];

    if (target > midVal) {    // 向右递归
        return binarySearchOne(arr, mid + 1, right, target);
    } else if (target < midVal) {    // 向左递归
        return binarySearchOne(arr, left, mid - 1, target);
    } else {
        return mid;
    }

}

二分查找-递归（查找多个值） 代码实现：

public static void main(String[] args) {

    int[] arr = {10, 20, 30, 30, 30, 30, 40, 50, 60, 70, 80, 90};
    List<Integer> list = binarySearchMore(arr, 0, arr.length - 1, 30);
    System.out.println(list);

}

// 二分查找（有多个值）
public static List<Integer> binarySearchMore(int[] arr, int left, int right, int findVal) {

    //System.out.println("hello~");
    // 当数组为空或 left > right 时，说明递归整个数组，但是没有找到
    if (arr == null || left > right) {
        return new ArrayList<>();
    }

    int mid = (left + right) / 2;
    int midVal = arr[mid];

    if (findVal > midVal) {   // 向右递归
        return binarySearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {   // 向左递归
        return binarySearch(arr, left, mid - 1, findVal);
    } else {

        //  思路分析：
        //  1、在找到 mid 索引值，不要马上返回
        //  2、向 mid 索引值的左边扫描，将所有满足 findVal 的元素的下标，加入到集合 ArrayList
        //  3、向 mid 索引值的右边扫描，将所有满足 findVal 的元素的下标，加入到集合 ArrayList
        //  4、将 Arraylist 返回

        List<Integer> resIndexlist = new ArrayList<Integer>();
        // 向 mid 索引值的左边扫描，将所有满足 findVal 的元素的下标，加入到集合 ArrayList
        int temp = mid - 1;

        while (true) {

            if (temp < 0 || arr[temp] != findVal) {    // 退出
                break;
            }

            // 否则，就把 temp 放入到 resIndexlist
            resIndexlist.add(temp);
            temp -= 1;    // temp 左移

        }

        resIndexlist.add(mid);   // 把 mid 值加入到集合

        // 向 mid 索引值的右边扫描，将所有满足 findVal 的元素的下标，加入到集合 ArrayList
        temp = mid + 1;

        while (true) {
            if (temp > arr.length - 1 || arr[temp] != findVal) {    // 退出
                break;
            }
            // 否则，就把 temp 放入到 resIndexlist
            resIndexlist.add(temp);
            temp += 1;   // temp 右移
        }

        Collections.sort(resIndexlist);    // 此行代码不过说对结果进行排序，不是特别重要。去掉这一行，集合可能乱序
        return resIndexlist;

    }

}

二分查找-非递归

二分查找-非递归（只有一个值） 代码实现：

public static void main(String[] args) {

    int[] arr = {10, 20, 30, 30, 30, 30, 40, 50, 60, 70, 80, 90};
    int value = binarySearchOne(arr, 40);
    System.out.println(value);

}

// 二分查找-非递归（只有一个值）
public static int binarySearchOne(int[] arr, int target) {

    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {    // 当左边小于等于右边时，一直执行。【数组默认升序】

        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;   // 向左边查找
        } else {
            left = mid + 1;    // 向右边查找
        }

    }

    return -1;

}

二分查找-非递归（查找多个值） 代码实现：

public static void main(String[] args) {

    int[] arr = {10, 20, 30, 30, 30, 30, 40, 50, 60, 70, 80, 90};
    List list = binarySearchMore(arr, -10);
    System.out.println(list);

}

public static List<Integer> binarySearchMore(int[] arr, int value) {

    List<Integer> list = new ArrayList<>();
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {    // 当左边小于等于右边时，一直执行。【数组默认升序】

        int mid = (left + right) / 2;

        if (arr[mid] == value) {

            // 向左查找
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != value) {
                    break;
                }
                list.add(temp);
                temp -= 1;
            }

            list.add(mid);

            // 向左查找
            temp = mid + 1;
            while (true) {
                if (temp > arr.length || arr[temp] != value) {
                    break;
                }
                list.add(temp);
                temp += 1;
            }

            break;             // 一定要写 break; 否则报错：Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

        } else if (arr[mid] > value) {
            right = mid - 1;   // 向左边查找
        } else {
            left = mid + 1;    // 向右边查找
        }

    }

    Collections.sort(list);
    return list;

}

插值查找

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

举两个例子来说明 插值查找的快速 ，哈哈，如下图：

查找一个值

插值查找（只有一个值） 代码实现：

public static void main(String[] args) {

    int[] arr = {1, 2, 3, 4, 5, 5, 5, 5, 5, 6, 7, 9};
    int valueSearch = insertValueSearch(arr, 0, arr.length - 1, 5);
    System.out.println(valueSearch);

}

/**
 * @param arr     数组
 * @param left    左边索引
 * @param right   右边索引
 * @param findVal 查找值
 * @return 如果找到，就返回对应的下标，如果没有找到，返回 -1
 * 编写插值查找算法，查找一个值。说明：插值查找算法，也要求数组是有序的
 */
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {

    System.out.println("插值查找次数~~");

    // 注意：findVal < arr[0]  和  findVal > arr[arr.length - 1] 必须需要，否则 mid 可能越界
    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
        return -1;
    }

    // 求出 mid
    int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
    int midVal = arr[mid];

    if (findVal > midVal) {    // 说明应该向右边递归
        return insertValueSearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {    // 说明向左递归查找
        return insertValueSearch(arr, left, mid - 1, findVal);
    } else {
        return mid;
    }

}

查找多个值

插值查找（有多个值） 代码实现：

public static void main(String[] args) {

    int[] arr = {1, 2, 3, 4, 5, 5, 5, 5, 5, 6, 7, 9};
    List valueSearch = insertValueSearch(arr, 0, arr.length - 1, 5);
    System.out.println(valueSearch);

}

/**
 * @param arr     数组
 * @param left    左边索引
 * @param right   右边索引
 * @param findVal 查找值
 * @return 如果找到，就返回对应的下标，如果没有找到，返回 -1
 * 编写插值查找算法，查找多个值。说明：插值查找算法，也要求数组是有序的
 */
public static List<Integer> insertValueSearch(int[] arr, int left, int right, int findVal) {

    System.out.println("插值查找次数~~");

    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
        return new ArrayList<>();
    }

    int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
    int midVal = arr[mid];

    if (findVal > midVal) {    // 说明应该向右边递归
        return insertValueSearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {    // 说明向左递归查找
        return insertValueSearch(arr, left, mid - 1, findVal);
    } else {
        ArrayList<Integer> arrayList = new ArrayList<>();

        int temp = mid - 1;
        while (true) {
            if (temp < 0 || arr[temp] != findVal) {
                break;
            }
            arrayList.add(temp);
            temp--;
        }

        arrayList.add(mid);

        temp = mid + 1;
        while (true) {
            if (temp > arr.length || arr[temp] != findVal) {
                break;
            }
            arrayList.add(temp);
            temp++;
        }

        return arrayList;

    }

}

注意事项：

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

斐波那契查找

黄金分割

黄金分割 是指将整体 一分为二 ，较大部分与整体部分的比值 等于 较小部分与较大部分的比值 ，其比值约为 0.618 。这个比例被公认为是最能引起美感的比例，因此被称为 黄金分割 。由于按此比例设计的造型十分美丽，也称为 中外比 。斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数的比例，无限接近 黄金分割值 0.618 ，因此有了 斐波那契查找算法 。

斐波那契原理

斐波那契思想 与二分法相类似，不过中间点不再是中点，而变成了 黄金分割点 的附近 mid = low + F(k - 1) - 1 , F 代表斐波那契数列，以下将对 F(k - 1) - 1 进行解释，如下：

# F(k - 1) - 1 含义的理解

1、F 代表的斐波那契数列，k 代表斐波那契数列的第 k 个元素

2、由 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) 两段，另外一个 1 就是 mid 位置的元素

3、类似的每一个子段也可以用同样的方式来进行分隔

4、但是顺序表的长度不一定是恰好等于 F[k] - 1 ,所以需要将原来的顺序表的长度增加到 F[k] - 1 ，
   这里的 k 值仅仅需要使得 F[k] - 1 恰好大于或者等于 n ，新增的位置的值，都赋值为下标是 n - 1 位置的值

# 如果不理解也没有关系，这个算法有点难度，慢慢来！！！视频多看几遍，代码多敲几遍，慢慢就理解了。

代码实现

斐波那契查找（只有一个值） 代码实现：

public class FibonacciSearch {

    public static int maxSize = 25;

    public static void main(String[] args) {

        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int res = fibSearch(arr, 1000);
        System.out.println("index = " + res);

    }

    // 因为后面需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列【非递归方式】
    public static int[] fib() {

        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;

        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        return arr;

    }

    /**
     * 使用非递归的方式编写斐波那契查找算法
     * @param arr 数组
     * @param key 我们需要查找的关键码(值)
     * @return 返回对应的下标，如果没有-1
     */
    public static int fibSearch(int[] arr, int key) {

        int low = 0;
        int high = arr.length - 1;
        int k = 0;           // 表示斐波那契分割数值的下标
        int mid = 0;         // 存放 mid 值
        int fib[] = fib();   //获取到斐波那契数列

        // 获取到斐波那契分割数值的下标
        while (high > fib[k] - 1) {
            k++;
        }

        // 因为 fib[k] 值可能大于 arr 的长度，因此我们需要构造一个新的数组，不足的部分会使用 0 填充
        int[] temp = Arrays.copyOf(arr, fib[k]);

        // 实际上需求使用 arr 数组最后的数填充 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] = arr[high];
        }

        // 使用 while 来循环处理，找到我们的数 key
        while (low <= high) {

            mid = low + fib[k - 1] - 1;

            if (key < temp[mid]) {    // 向数组的前面查找(左边)
                high = mid - 1;
                /**
                 * 说明：为什么是 k--
                 * 1、全部元素 = 前面的元素 + 后边元素
                 * 2、f[k] = f[k-1] + f[k-2]
                 * 3、前面有 f[k-1] 个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                 * 4、即在 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 ,即下次循环 mid = f[k-1-2] - 1
                 */
                k -= 2;
            } else { // 找到，需要确定，返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }

        return -1;

    }
}

哈希表

基本介绍

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

问题描述

Google 公司的一个上机题:

有一个公司,当有新的员工来报道时,要求将该 员工的信息【id,性别,年龄,名字,住址..】 加入到系统，当输入该员工的 id 时，要求查找到该员工的所有信息。要求: 不使用数据库，速度越快越好 。

代码实现

import java.util.Scanner;

/**
 * @Author: guoshizhan
 * @Create: 2020/6/12 16:31
 * @Description: 哈希表查询
 */
public class HashTabTest {

    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("exit: 退出系统");

            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("请输入 id：");
                    int id = scanner.nextInt();
                    System.out.println("请输入名字：");
                    String name = scanner.next();
                    //创建雇员
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的 id：");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }

        }

    }

}

// 创建 HashTab 管理多条链表，这就是所谓的哈希表
class HashTab {

    private EmpLinkedList[] empArray;
    private int size;    // 表示有多少条链表

    // 创建构造器
    public HashTab(int size) {
        this.size = size;
        empArray = new EmpLinkedList[size];   // 初始化 empArray

        // 分别初始化每个链表
        for (int i = 0; i < size; i++) {
            empArray[i] = new EmpLinkedList();
        }
    }

    // 添加雇员
    public void add(Emp emp) {

        // 根据员工的 id , 得到该员工应当添加到哪条链表
        int empLinkedListNO = hashFun(emp.id);

        // 将 emp 添加到对应的链表中
        empArray[empLinkedListNO].add(emp);

    }

    // 遍历所有的链表
    public void list() {
        for (int i = 0; i < size; i++) {
            empArray[i].list(i);
        }
    }

    // 根据输入的 id , 查找雇员
    public void findEmpById(int id) {

        // 使用散列函数确定到哪条链表查找
        int empLinkedListNO = hashFun(id);
        Emp emp = empArray[empLinkedListNO].findEmpById(id);

        if (emp != null) {    // 找到雇员
            System.out.printf("在第%d条链表中找到雇员 id = %d\n", (empLinkedListNO + 1), id);
        } else {
            System.out.println("在哈希表中，没有找到该雇员~~~");
        }

    }

    // 编写散列函数, 使用一个简单取模法
    public int hashFun(int id) {
        return id % size;
    }
}

// 定义一个雇员类 Emp
class Emp {

    public int id;
    public String name;
    public Emp next;   // next 默认为 null

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

}

// 创建 EmpLinkedList 类，表示链表
class EmpLinkedList {

    // 定义头指针 head，指向第一个 Emp 对象
    private Emp head; // 默认 null

    /**
     * 添加雇员到链表
     * 1、假定，当添加雇员时，id 是自增长，即 id 的分配总是从小到大
     * 2、因此我们将该雇员直接加入到本链表的最后即可
     */
    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 后移
        }

        // 退出时直接将 emp 加入链表
        curEmp.next = emp;

    }

    // 遍历链表的雇员信息
    public void list(int no) {

        if (head == null) {   // 说明链表为空
            System.out.println("第 " + (no + 1) + " 条链表为空");
            return;
        }

        System.out.print("第 " + (no + 1) + " 条链表的信息为");
        Emp curEmp = head;

        while (true) {
            System.out.printf(" => id=%d name=%s ", curEmp.id, curEmp.name);
            if (curEmp.next == null) {    // 说明 curEmp 已经是最后结点
                break;
            }
            curEmp = curEmp.next;         // curEmp 后移
        }

        System.out.println();

    }

    // 根据 id 查找雇员。如果查找到，就返回 Emp 对象, 如果没有找到，就返回 null
    public Emp findEmpById(int id) {

        // 判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }

        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {
                break;    // 这时 curEmp 就指向要查找的雇员
            }

            // 退出条件
            if (curEmp.next == null) {    // 说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }

        return curEmp;

    }
}

常用的算法

分治算法

分治算法介绍

分治算法 是一种很重要的算法。字面上的解释是 “分而治之” ，就是把一个 复杂的问题 分成两个或更多的相同或相似的 子问题 ，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

分治算法可以求解的一些经典问题：

1、二分搜索 2、大整数乘法 3、棋盘覆盖 4、合并排序 5、快速排序 6、线性时间选择 7、最接近点对问题 8、循环赛日程表 9、汉诺塔问题

求解步骤

分治算法 在每一层递归上都有以下 三个步骤 ：

求解步骤：

1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题 2、解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 3、合并：将各个子问题的解合并为原问题的解。

应用：汉诺塔问题

汉诺塔的传说： 汉诺塔（又称河内塔）问题 是源于印度一个古老传说的 益智玩具 。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845.54 亿年 以上，太阳系的预期寿命据说也就是数百亿年。真的过了 5845.54 亿年 ，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

// 汉诺塔移动的方法：使用分治算法
// 参数含义：num 代表金属盘个数，L 代表左边的柱子，M 代表中间的柱子，R 代表右边的柱子
public static void hanoiTower(int num, char L, char M, char R){
    // 如果只有一个盘
    if(num == 1){
        System.out.println("第" + num + "个盘从 " + L + "-->" + R);
    }else {
        // 如果我们有 n >= 2 情况，我们总是可以看做是两个盘：最下边的一个盘 和 上面的所有盘
        // 1. 先把 最上面的所有盘 L-->M， 移动过程会使用到 R
        hanoiTower(num - 1, L, R, M);

        // 2. 把最下边的盘 L-->R
        System.out.println("第" + num + "个盘从 " + L + "-->" + R);

        // 3. 把 M 塔的所有盘 从 M-->R , 移动过程使用到 L 塔
        hanoiTower(num - 1, M , L , R);
    }
}

TIPS : 分治算法理解起来容易，就是分而治之。但关键在于： 如何划分，如何把整体划分成部分。解决划分问题，分治算法就算掌握了。

动态规划算法

算法介绍

动态规划(Dynamic Programming)算法 的 核心思想 是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是 ，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )动态规划可以通过 填表的方式 来逐步推进，得到最优解。

应用：背包问题

背包问题：有一个背包，容量为 4 磅，现有如下物品：

物品	重量	价格
吉他(G)	1	1500
音响(S)	4	3000
电脑(L)	3	2000

问题要求： ① 达到的目标为装入的背包的总价值最大，并且重量不超出。② 要求装入的物品不能重复。

思路分析

代码演示

动态规划算法的代码如下：

package edu.jgsu.algorithm;

/**
 * @Author: guoshizhan
 * @Create: 2020/3/28 12:08
 * @Description: 动态规划算法之背包问题
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1,4,2};               // 物品的重量
        int[] val = {1500,3000,2000};    // 物品的价值
        int n = val.length;              // 物品的个数
        int m = 4;                       // 背包的容量

        // 创建二维数组，v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v = new int[n+1][m+1];
        // 为了记录放入商品的情况，我们定一个二维数组
        int[][] path = new int[n+1][m+1];

        // 初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是 0
        for(int i = 0; i < v.length; i++) {
            v[i][0] = 0;    // 将第一列设置为0
        }
        for(int i=0; i < v[0].length; i++) {
            v[0][i] = 0;    // 将第一行设置0
        }

        // 输出一下 v ，看看目前的情况
        for(int i =0; i < v.length;i++) {
            for(int j = 0; j < v[i].length;j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("============================");

        //根据前面得到公式来动态规划处理
        for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
            for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
                //公式
                if(w[i-1]> j) { // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
                    v[i][j]=v[i-1][j];
                } else {
                    //说明:
                    //因为我们的i 从1开始的， 因此公式需要调整成
                    //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
                    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
                    if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        //把当前的情况记录到path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }

                }
            }
        }

        //输出一下v 看看目前的情况
        for(int i =0; i < v.length;i++) {
            for(int j = 0; j < v[i].length;j++) {
                System.out.printf("%04d  ",v[i][j]);
            }
            System.out.println();
        }

        System.out.println("============================");
        //输出最后我们是放入的哪些商品
        //遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
//        for(int i = 0; i < path.length; i++) {
//            for(int j=0; j < path[i].length; j++) {
//                if(path[i][j] == 1) {
//                    System.out.printf("第%d个商品放入到背包\n", i);
//                }
//            }
//        }

        //动脑筋
        int i = path.length - 1; //行的最大下标
        int j = path[0].length - 1;  //列的最大下标
        while(i > 0 && j > 0 ) { //从path的最后开始找
            if(path[i][j] == 1) {
                System.out.printf("第%d个商品放入到背包\n", i);
                j -= w[i-1]; //w[i-1]
            }
            i--;
        }
    }
}

暴力匹配算法

算法介绍

代码演示

public static int violenceMatch(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        int s1Len = s1.length;
        int s2Len = s2.length;

        int i = 0; // i索引指向s1
        int j = 0; // j索引指向s2
        while (i < s1Len && j < s2Len) {// 保证匹配时，不越界

            if(s1[i] == s2[j]) {//匹配ok
                i++;
                j++;
            } else { //没有匹配成功
                //如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。
                i = i - (j - 1);
                j = 0;
            }
        }

        //判断是否匹配成功
        if(j == s2Len) {
            return i - j;
        } else {
            return -1;
        }
    }

KMP 算法

算法介绍

TIPS :

KMP 算法关键： 搞懂 部分匹配表 ，就是代码里的那个 next 数组 。
参考文章： https://www.cnblogs.com/zzuuoo666/p/9028287.html

代码演示

public class KMPAlgorithm {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        //String str2 = "BBC";
        
        int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
        System.out.println("next=" + Arrays.toString(next));
        
        int index = kmpSearch(str1, str2, next);
        System.out.println("index=" + index); // 15了
        
        
    }
    
    //写出我们的kmp搜索算法
    /**
     * 
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表, 是子串对应的部分匹配表
     * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        
        //遍历 
        for(int i = 0, j = 0; i < str1.length(); i++) {
            
            //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
            //KMP算法核心点, 可以验证...
            while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j-1]; 
            }
            
            if(str1.charAt(i) == str2.charAt(j)) {
                j++;
            }            
            if(j == str2.length()) {//找到了 // j = 3 i 
                return i - j + 1;
            }
        }
        return  -1;
    }

    //获取到一个字符串(子串) 的部分匹配值表
    public static  int[] kmpNext(String dest) {
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
        for(int i = 1, j = 0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
            //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
            //这时kmp算法的核心点
            while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j-1];
            }
            
            //当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

贪心算法

算法介绍

应用场景及分析

代码实现

package greedy;

import java.util.*;

/**
 * @Author: guoshizhan
 * @Create: 2020/5/15 17:05
 * @Description: 贪心算法之集合覆盖问题
 */
public class Greedy {
    public static void main(String[] args) {
        // 创建广播电台，放到 Map 中
        Map<String, HashSet<String>> broadcast = new HashMap<>();

        // 每个电台对应的城市
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        // 加入到 Map
        broadcast.put("K1", hashSet1);
        broadcast.put("K2", hashSet2);
        broadcast.put("K3", hashSet3);
        broadcast.put("K4", hashSet4);
        broadcast.put("K5", hashSet5);

        // 存放所有地区，且不重复
        HashSet<String> allAreas = new HashSet<>();
        Set<Map.Entry<String, HashSet<String>>> entries = broadcast.entrySet();
        for (Map.Entry<String, HashSet<String>> entry : entries) {
            HashSet<String> value = entry.getValue();
            for (String s : value) {
                allAreas.add(s);
            }
        }

        // 查看地区是否正确
        System.out.println(allAreas);

        // 创建 ArrayList 集合，存放已选择的电台
        ArrayList<String> selects = new ArrayList<>();

        // 定义一个临时集合， 存放电台覆盖的地区和还未覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<>();

        // 定义 maxKey ，保存电台的 Key【能够覆盖最多未覆盖地区的那个电台的 Key。例如：K1 】
        String maxKey = null;

        // 如果不为 0 ，则表示还没有覆盖到所有地区
        while (allAreas.size() != 0) {
            // 每进行一次 while 循环，maxKey 就要置为空
            maxKey = null;
            // 遍历 broadcast ，取出对应 key
            for (String key : broadcast.keySet()) {
                // 每进行一次 for 循环，tempSet 就要清空
                tempSet.clear();

                HashSet<String> areas = broadcast.get(key);
                tempSet.addAll(areas);
                tempSet.retainAll(allAreas);  // 取交集并把结果赋值给 tempSet

                // 此处便是贪心算法的体现：每次都是选择最好的
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcast.get(maxKey).size())) {
                    maxKey = key;
                }
            }

            if (maxKey != null) {
                selects.add(maxKey);
                allAreas.removeAll(broadcast.get(maxKey));
            }
        }

        System.out.println("贪心算法最后结果：--- " + selects);

    }
}

注意事项

普利姆算法

克鲁斯卡尔算法

迪杰斯特拉算法

弗洛伊德算法

回溯算法

八皇后算法

骑士周游算法

番外篇，哈哈

数据结构：逻辑结构和物理结构（数据在计算机内部的物理存储方式）
数据元素存储形式：顺序存储结构和链式存储结构（银行排队叫号系统）
逻辑结构：集合结构、线性结构、树形结构（金字塔关系）、图形结构
了解：六度空间理论

了解算法：就是解决问题的方法。例如：求从1加到100的和。使用for循环和等差公式，对计算机来说都没有什么差别，但加到10000000就差别大了，这就是算法。
算法5个特性：零个或多个输入、至少一个或多个输出、有穷性、确定性和可行性。
算法设计要求：正确性、可读性、健壮性、时间效率高和存储量低。

时间复杂度（渐近时间复杂度）：使用大O体现算法时间复杂度，成为大O计法。
线性阶：非嵌套循环涉及线性阶，对应次数成直线增长。
平方阶：两个嵌套循环涉及平方阶。
对数阶：例如下面的程序：2的x次方=n，求解之后x=log（2）n，所以时间复杂度为O（logn）
还有常数阶，立方阶，指数阶。nlogn阶。
int i  = 1, n = 100;
while(i < n)
{
i = i * 2;
}

最坏情况：
平均情况：平均运行时间就是期望运行时间。
空间复杂度：写代码时，可以用空间换取时间。闰年算法的例子。 


线性表：
存和读的情况：时间复杂度为O(1)
插入和删除情况：时间复杂度为O(n)
单链表：
结点：数据域和指针域合在一起叫做结点
数据域：存放数据的地方
指针域：存放下一个地址的地方
第一个结点叫做头结点（头指针）头结点一般不存储任何东西，头指针指向头结点，最后一个结点指向NULL


下一次看线性表第6集



======================================

认识时间复杂度，用big O表示
二分搜索，时间复杂度O（log2N）
外排（谁小谁移动）
题目：给定一个M个数的数组a和N个数的数组B，数组a乱序，数组b顺序，求两个数组共有多少个相同的数的复杂度？
第一种：嵌套for循环，复杂度为O（M*N）
第二种：对数组b（数组b是顺序的）使用二分查找，时间复杂度O（M*log2N）
第三种：使用外排，先对数组a进行排序，然后使用外排，就是将两个数组的索引指向0，指向数字谁小谁就往下移动一个位置，直到结束。


选择排序：
第一次排序把最小的放在第一位，第二次排序把第二小的数字放在第二位，以此类推，直至结束。
这种排序和数据状况没有关系，即便是一个排好的数组，它的时间复杂度仍然不变。


冒泡排序：
在一个数组中，相邻位置的数进行比较。进行完第一轮排序，最大的数字会在最后一个位置。那么下一轮排序就不用比较最后一个数字了。
这种排序和数据状况没有关系，即便是一个排好的数组，它的时间复杂度仍然不变。


插入排序：
就像打扑克牌一样，一副排好序的牌，然后你摸了一张牌，就要给这张牌找位置，这就是插入排序。
插入排序和数据状况有关，例如：数组元素1，2，3，4，5，那么插入排序复杂度为O（N），如果是5，4，3，2，1，那么复杂度为O（N2）.
一般情况下，都是按照最坏情况作为一个算法的复杂度。


最好情况：


平均情况：


最坏情况：


以上三种情况在插入排序可见，自己百度以下平均情况。


对数器【很重要的】：方法在排序代码里有。先要有随机数组产生器，然后需要绝对正确的方法，接着进行大样本的测试。
堆的结构准备模板，排序、二叉树、数组也要准备对数器模板。

冒泡和选择公司已经不使用了，只具有参考和教学意义。

递归算法：1：38：26	递归如何求时间复杂度？1：51：49	时间复杂度求解公式1：54：30


归并排序：

master公式
复杂度为O（N*log2N）






计算机网络看视频从第一章开始看，同时参观CSDN别人的博客。



===============================
韩顺平老师数据结构：
===============================
KMP算法：

汉诺塔问题：使用分治算法


八皇后问题：使用回溯算法


骑士周游问题：DFS+贪心算法


场合不同，所使用的算法不一样

五子棋程序

约瑟夫问题【单向环形链表】

稀疏数组和队列
队列的应用：队列是个有序列表，可以用数组或者链表实现。特点：先进先出
队列加数据在尾部加入，且rear+1，取数据在头部取，且front+1。
queue包里面代码：数组实现队列和链表实现队列。
数组模拟成环形队列。

栈的应用：如子弹的弹夹，最先压入的子弹最后打出。
线性表：自己补充

单链表知识：看完写博客

双向链表：

（环形链表）约瑟夫环：



排序算法：
内容在 PPT 上

已看：50 51 


冒泡排序：
选择排序：
插入排序：
希尔排序：
快速排序：
归并排序：
基数排序：
桶排序：
堆排序：
计数排序：



查找算法：
顺序（线性）查找：
二分查找/折半查找：
插值查找：	非常的牛逼
斐波那契查找（黄金分割查找）：



哈希表：



二叉树：
- 各种二叉树术语
- 三种遍历方式
- 二叉树的查找
- 二叉树的删除
- 顺序存储二叉树
- 线索化二叉树
- 堆排序：先变成大顶堆，然后排序


赫夫曼树：
wpl最小的就是赫夫曼树，赫夫曼树也是二叉树
赫夫曼编码：不要前缀编码，就是不要出现二义性
赫夫曼压缩
赫夫曼解压



二叉排序树：
- 创建
- 遍历
- 删除


平衡二叉树：
- 左旋转
- 右旋转
- 双旋转

多叉树：
B树
- 2-3树
- 234树

B+树

B*树

多路查找树



图：
图的基本术语
图的邻接矩阵
图的邻接表
图的遍历方式：
- 深度优先遍历（DFS）
- 广度优先遍历（BFS）
想要理解清楚 DFS 和 BFS 的区别，就要以图的邻接矩阵为例子，更好理解一点。



程序员常用的 10 中算法：
- 二分查找算法（非递归）
- 分治算法（汉诺塔问题）【使用了递归算法】
- 动态规划算法（背包问题）
- KMP 算法（字符串匹配问题）
- 暴力匹配算法
- 贪心算法
- 普利姆算法（prim算法）（修路问题）（最小生成树问题）
- 克鲁斯卡尔算法（公交站问题）
- 迪杰斯特拉算法（最短路径问题）
- 弗洛伊德算法
- 马踏棋盘算法（骑士周游问题）



卖油翁和老黄牛的故事：
在通往成功的路上，我们必须坚持，不要中途放弃，自毁前程，而要勇往直前，坚持不懈，最终会抵达理想的彼岸。既然选择了远方，便只顾风雨兼程。

其他算法小案例

反转输出

// 01-小米笔试题：输入一个句子，例如 hello world xiaomi ，然后反转输出如： xiaomi world hello
public static void xiaomi(){
    Scanner sc = new Scanner(System.in);
    System.out.println("请输入句子，以空格分隔：");
    String str = sc.nextLine();

    // 通过split方法把句子切割保存到String数组
    String[] arr = str.split(" ");

    // 遍历数组
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[arr.length - 1 - i] + " ");
    }
}

十进制和十六进制转化

public static String intToHex(int n) {
    StringBuffer s = new StringBuffer();
    String a;
    char[] b = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
    while (n != 0) {
        s = s.append(b[n % 16]);
        n = n / 16;
    }
    a = s.reverse().toString();
    return a;
}

杨辉三角

// 杨辉三角：金字塔型的，方法里面的参数代表输出的行数
public static void yanghui(int rows){
    for (int i = 0; i < rows; i++) {
        int number = 1;
        // 打印空格字符串
        System.out.format("%" + (rows - i) * 2 + "s", "");
        for (int j = 0; j <= i; j++) {
            System.out.format("%4d", number);
            number = number * (i - j) / (j + 1);
        }
        System.out.println();
    }
}

格式化数组

// 按照指定的格式输出数组
public static void arrayFormat(int[] arr) {
    System.out.print("[");
    for (int i = 0; i < arr.length; i++) {
        if (i == arr.length -1) {
            System.out.print(arr[i] + "#]");
        } else {
            System.out.print(arr[i] + "# ");
        }
    }
}

常用算法 / 算法

本文标题：算法入门
本文作者：Java Developer
本文链接：https://guoshizhan.github.io/Algorithm.html
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

📚 本站推荐文章
👉 从 0 开始搭建 Hexo 博客
👉 计算机网络入门教程
👉 数据结构入门
👉 算法入门
👉 IDEA 入门教程