[数据结构与算法] java 常见算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> java 常见算法 -> 正文阅读

[数据结构与算法]java 常见算法

文章目录

一、简介

内容根据尚硅谷、黑马的视频和漫画算法书本整理收集，所以一些文字或者图片出自这些，一些是根据自己的理解写的。
在学习算法，仅是按文章或者书本说的可能有点难理解，毕竟是学习数据结构和算法，一些逻辑会比较复杂，甚至需要数学功底，所以最好的方法是结合视频、书、文章一起来学习，如果这个视频的老师说起来听的不太懂的话，那么就找另一个老师的视频看下，如果视频的不太懂，那么就看下书本说的，看那个更易懂一些。然后不同老师/作者说的算法实现方式也不一样，我们也能学到他们不同的算法思想。
尚硅谷、黑马视频算是对新手比较简单能理解的，还有漫画算法的书也是比较适合新手，因此推荐一起看。

参考：
1、【尚硅谷】数据结构与算法（Java数据结构与算法）
https://www.bilibili.com/video/BV1E4411H73v/?spm_id_from=333.999.0.0&vd_source=548b27fee009b7ca3bfb319772b8d3e7

2、黑马程序员Java数据结构与java算法全套教程，数据结构+算法教程全资
https://www.bilibili.com/video/BV1iJ411E7xW/?spm_id_from=333.999.0.0&vd_source=548b27fee009b7ca3bfb319772b8d3e7

3、【程序员小灰】漫画算法：小灰的算法之旅（全彩）(博文视点出品)
https://item.jd.com/12513751.html

二、数据结构和算法一些概念

数据结构：是计算机存储、组织数据的方式。可以把它看成是用来如何存数据的

算法：指如何解决一类问题的明确规范。可以理解为解题的一种方式，解题的步骤。

时间复杂度：用来描述执行当前算法所消耗的时间。

空间复杂度：用来描述执行当前算法需要占用多少内存空间

三、排序算法

排序的分类：

内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

在这里插入图片描述

常用排序算法对比：

在这里插入图片描述

1、冒泡排序（简单排序）

冒泡排序：简单理解为前一个数和后一个数比较交互，一直从0到最后一个位置。这样的一层层比较交互就想冒泡一样。

时间复杂度：O(N^2)

冒泡排序原理：

比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大
值。

冒泡实现方式一

图解：
在这里插入图片描述

java代码实现：

/**
 * 冒泡排序,时间复杂度O(n^2)。
 * 简单理解：从0到最后一个位置，前一个数和后一个数比较交互。
 * 参考漫画算法：小灰的算法之旅
 */
public class BobbleSort {

    public static void main(String[] args) {
        BobbleSort bobbleSort = new BobbleSort();
        int[] a = {5, 8, 6, 3, 9, 2, 1, 7};
        //简单的冒泡
        bobbleSort.bobbleSort1(a);
        int[] b = {5, 8, 6, 3, 9, 2, 1, 7};
        //冒泡优化：不再重新遍历后面已经排序的数列；当循环到一定程度就已经是有序的数组，这时候不需要继续走完冒泡次数。
        bobbleSort.bobbleSort2(b);
        //冒泡再优化：优化当前面部分是无序的但后面部分是有序的情况。
        bobbleSort.bobbleSort3(new int[]{3,4,2,1,5,6,7,8});
    }


    /**
     * 一、简单冒泡排序，缺点：由于第一次最后一个数已经是最大，第二次最后两个数最后两个数已经是最大的，排序好了，但是第二层循环依然会进行
     * 因此，就是后面部分即使是排序好了，
     *
     * [5, 8, 6, 3, 9, 2, 1, 7]
     *
     * 【          j          】
     * [5, 6, 3, 8, 2, 1, 7, 9]  ︻
     * [5, 3, 6, 2, 1, 7, 8, 9]
     * [3, 5, 2, 1, 6, 7, 8, 9]
     * [3, 2, 1, 5, 6, 7, 8, 9]  i
     * [2, 1, 3, 5, 6, 7, 8, 9]
     * [1, 2, 3, 5, 6, 7, 8, 9]
     * [1, 2, 3, 5, 6, 7, 8, 9]
     * [1, 2, 3, 5, 6, 7, 8, 9]  ︼
     * <p>
     * i：第一层循环控制冒泡次数，arr.length - 1次
     * j：第二层循环控制冒泡交互，从第一个数交换到最后一个。
     * 参考漫画算法：小灰的算法之旅
     * @param arr
     */
    public void bobbleSort1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println("一、简单冒泡排序");
        System.out.println("原始数据：" + Arrays.toString(arr));
        //第一层循环，用来控制冒泡的次数
        for (int i = 0; i < arr.length -1; i++) {
            //第二层循环，用来控制一层层冒泡交换到最后一个
            for (int j = 0; j < arr.length - 1; j++) {
                //比较前一个数是否大于后一个数，如果大的话则交换
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }

    }


    /**
     *二、冒泡排序优化：
     * 1、随着第二层循环，冒泡交互，后面的数已经是有序了，在进行第i次冒泡后，控制第二层循环不需要冒泡交换到最后一个数
     * 2、可能当冒泡的次数是第i次时，这时候数组已经排序好了，因此此时不需要再进行后面的循环，优化中断后面的循环。
     * [5, 8, 6, 3, 9, 2, 1, 7]
     *
     * 【          j          】
     * [5, 6, 3, 8, 2, 1, 7, 9]  ︻
     * [5, 3, 6, 2, 1, 7, 8, 9]
     * [3, 5, 2, 1, 6, 7, 8, 9]  i
     * [3, 2, 1, 5, 6, 7, 8, 9]
     * [2, 1, 3, 5, 6, 7, 8, 9]
     * [1, 2, 3, 5, 6, 7, 8, 9]  ︼
     *
     * i：第一层循环控制冒泡次数，arr.length - 1次
     * j：第二层循环控制冒泡交互，从第一个数交换到arr.length - 1 -i位置，因为arr.length - 1 -i位置后面的数已经是有序的了。
     *
     * @param arr
     */
    public void bobbleSort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println("二、冒泡排序优化");
        System.out.println("原始数据：" + Arrays.toString(arr));
        //第一层循环，用来控制冒泡的次数
        for (int i = 0; i < arr.length -1; i++) {
            //有序标记，如果有一轮没有交换的话，说明已经排序好了。
            boolean isSorted = true;
            //第二层循环，用来控制一层层冒泡交换到最后一个，优化：每次冒泡到最后的第arr.length - 1 -i位置。
            //因为最后那几位已经是有序的了。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    isSorted = false;
                }
            }
            //说明已经排序好了，省去后面继续循环
            if (isSorted) {
                break;
            }
            System.out.println(Arrays.toString(arr));
        }

    }

    /**
     *  三、冒泡排序最终版：
     *  如果出现3、4、2、1、5、6、7、8这些数组，后面部分已经是有序的了，按照第二优化的版本，依然会出现循环判断后部分有序数列。
     *  将数组分成无序区域和有序区域，冒泡交换只到无序区域。
     *  [5, 8, 6, 3, 9, 2, 1, 7]
     *
     * 【          j          】
     * [3, 2, 1, 4, 5, 6, 7, 8]  ︻
     * [2, 1, 3, 4, 5, 6, 7, 8]  i
     * [1, 2, 3, 4, 5, 6, 7, 8]
     * [1, 2, 3, 4, 5, 6, 7, 8]  ︼
     *
     *
     *
     * @param arr
     */
    public void bobbleSort3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println("三、冒泡排序最终版");
        System.out.println("原始数据：" + Arrays.toString(arr));
        //记录最后一次交换的位置
        int lastExchangeIndex = 0;
        //无序数列的边界，每次比较只需要比到这里为止
        int sotBorder = arr.length -1;
        for (int i = 0; i < arr.length - 1; i++) {
            //有序标记，如果有一轮没有交换的话，说明已经排序好了。
            boolean isSorted = true;
            for (int j = 0; j < sotBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    //因为有元素进行交换，所以不是有序的，标记变为false
                    isSorted = false;
                    //更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            sotBorder = lastExchangeIndex;
            System.out.println(Arrays.toString(arr));
            if (isSorted) {
                break;
            }
        }

    }
}

冒泡实现方式二

java代码实现：

/**
 * 冒泡第二种实现方式。
 * 参考：黑马程序员（<a href="https://www.bilibili.com/video/BV1iJ411E7xW?p=13&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>）
 */
public class BobbleSort2 {

    public void bobbleSort2(int[] arr){
        //第一层循环控制横向冒泡数量,每一次循环冒泡数量减1，
        // 第二层循环，控制冒泡交换到第几个位置。
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

2、选择排序（简单排序）

选择排序：每次遍历，选择后面没排序的数组中最小的值和没排序数组中的第一个索引值交互。

时间复杂度：O(N^2)

和冒泡排序比较：
选择排序先将前面部分就行排序，而冒泡是先将后部分进行排序。
选择排序一次循环只交互一次数据，因此比冒泡大大减少。

在这里插入图片描述

java代码实现：

/**
 * 选择排序，时间复杂度 O(n^2)
 *
 */
public class SelectionSort {
    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort();
        int[] a = {5, 8, 6, 3, 9, 2, 1, 7};
        selectionSort.selectSort(a);
    }

    /**
     * 选择排序
     * 第一次，假定第一个为最小值，在第一个后面到最后找出一个最小值，和第一个值交换。
     * 第二次，假定第二个为最小值，在第二个后面到最后找出一个最小值，和第二个值交换。
     * 以此类推。
     * 参考（<a href="https://www.bilibili.com/video/BV1E4411H73v?p=58&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>）
     * @param arr
     */
    public void selectSort(int[] arr){
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            //循环的最小值，假定为arr[i]
            int min = arr[i];
            //最小值下标
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                //说明假定的最小值，并不是最小
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
                System.out.println("交换后"+ Arrays.toString(arr));
            }
            //如果最小值下标不是i的话就交换第i和最小值下标minIndex的值
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}

3、快速排序（高级排序）

快速排序：是对冒泡排序的一种改进，类似二分查找的思想，设定一个分界值，通过该分界值将数组分成左右两部分，左部分比分界值小，右部分比分界值大。然后又通过次方法将左边和右边设定一个分界值。通过递归重复上述步骤。

时间复杂度：最坏O(n^2)，最优O(nlogn)，平均O(nlogn);

实现方式：

双边循环法：设置分界值，用两个下标指针，进行遍历比较交换，约定左边比分界值小，右边比分界值大。
单边循环法：设置分界值，只用一个下标指针mark，进行遍历比较交换，约定mark指针左边数据比分界值小，右边数据比分界值大。

选择排序：双边循环法

参考：https://www.bilibili.com/video/BV1E4411H73v?p=67&vd_source=548b27fee009b7ca3bfb319772b8d3e7

选择排序-双边循环法原理：

设置中间值为分界值。
循环，分界值左边设置左下标，从左往右找出比分界值大的值；右边设置右下标，从右往左找出比分界值小的，然后将这两个值进行交换（可能会将分界值和左边或者右边的数交换，这时候左下标或者右下标会超过之前的分界值，但左下标不会大于右下标）。循环后，分界值左边数据全部是小于分界值的，分界值右边数据则全部大于分界值的。
再向左递归，从左边部分中间设置分界值，按上述步骤；向右递归，从右边部分中间设置分界值，按上述步骤。

整体图解
在这里插入图片描述

分步图解：
在这里插入图片描述

选择排序：单边循环法

选择排序-单边循环法原理：
单边循环（使用一个mark下标，遍历后面的数据和设置基准值作比较）。具体看下面图解

单边循环法图解：
在这里插入图片描述

在这里插入图片描述

选择排序双边和单边循环java代码：

/**
 * 快速排序，时间复杂度O(nlogn)
 */
public class QuickSort {
    public static void main(String[] args) {
        QuickSort quitSort = new QuickSort();
        System.out.println("====快速排序-双边循环====");
        //快速排序-双边循环
        int[] a = {4,0,6,5,3,8,2,1};
        System.out.println("原数据："+Arrays.toString(a));
        quitSort.quickSort1(a,0,a.length - 1);
        System.out.println("\n\n");
        System.out.println("====快速排序-单边循环====");
        int[] b = {4,0,6,5,3,8,2,1};
        System.out.println("原数据："+Arrays.toString(b));
        quitSort.quickSort2(b,0,b.length - 1);
    }


    /**
     * 快速排序实现方式1：双边循环（使用了左和右下标指针移动）
     * 参考：<a href="https://www.bilibili.com/video/BV1E4411H73v?p=67&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     * @param left
     * @param right
     */
    public void quickSort1(int[] arr,int left , int right){
        int l = left; //左下标
        int r = right; //右下标
        int pivot = arr[( right + left ) / 2];pivot 中轴值,设置中间数为分界值
        int temp = 0; //临时变量，作为交换时使用
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while (l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
//            System.out.println("{l:"+l +",r:"+r+"}");
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if (l >= r) {
                break;
            }

            System.out.println("交换{l:"+l +",r:"+r+",arr[l]:"+arr[l]+"," +arr[r]+"}");
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            System.out.println("交换后：" + Arrays.toString(arr));

            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移，当l >= r，结束循环
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移，当l >= r，结束循环
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        System.out.println("分治后数组：" + Arrays.toString(arr));
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            System.out.println("===向左递归===");
            quickSort1(arr, left , r);
        }
        //向右递归
        if (right > l) {
            System.out.println("===向右递归===");
            quickSort1(arr, l , right);
        }
    }


    /**
     * 快速排序：单边循环（使用一个mark下标，遍历后面的数据和设置基准值作比较）
     * 参考漫画算法：小灰的算法之旅
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public void quickSort2(int[] arr,int startIndex,int endIndex){
        //递归结束条件：startIndex >= endIndex
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素位置，此时基准值的左边数比基准值小，基准值右边数据比基准值大
        int pivotIndex = partition(arr,startIndex,endIndex);
        System.out.println("得到基准元素位置："+Arrays.toString(arr)+",startIndex:"+startIndex+",endIndex:"+endIndex+",pivotIndex:"+pivotIndex);
        System.out.println("==向左递归==");
        //向左递归
        quickSort2(arr,startIndex,pivotIndex - 1);
        System.out.println("==向右递归==");
        //向右递归
        quickSort2(arr,pivotIndex + 1,endIndex);

    }

    public int partition(int[] arr,int startIndex,int endIndex) {
        //取第一个位置的数作为基准值
        int pivot = arr[startIndex];
        //设置一个mark标记，默认是下标是基准值
        int mark = startIndex;
        for (int i = startIndex +1; i <= endIndex; i++) {
            //当遍历后部分的数据比基准值小的话，则交换mark标记位置的数
            if (arr[i] < pivot) {
                //mark标记向右移动一位
                mark++;
                //交换
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
                System.out.println("交换{mark："+temp +",i:" + arr[mark]+"}");
            }
            System.out.println("数组："+Arrays.toString(arr)+",mark:"+mark+ ", i:" +i );
        }
        //最后交换mark标记的位置和基准值，因为Mark标记的位置的数比基准值小。
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

}

4、插入排序（简单排序）

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

时间复杂度：O(N^2)

插入排序原理：

将所有数据分为两组，左边是排序了的，右边是未排序的。
找到未排序的组中的第一个元素，向左遍历比较和已排序组中的数，如果比某个数小，则在某个数前插入该数（实际和冒泡一样差不多向前交换）。插入后。

在这里插入图片描述

java代码实现：

/**
 * 插入排序，时间复杂度O(n^2)
 *
 */
public class InsertSort {
    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        int[] arr = {5, 8, 6, 3, 9, 2, 1, 7};
        System.out.println("原始数据："+ Arrays.toString(arr));
        insertSort.insertSort(arr);
    }


    /**
     * 插入排序
     * 将所有数据分为两组，左边是排序了的，右边是未排序的。
     * 找到未排序的组中的第一个元素，向左遍历比较和已排序组中的数，如果比某个数小，则在某个数前插入该数（实际和冒泡一样差不多向前交换）。
     * 插入后该数据纳入
     * 参考：<a href="https://www.bilibili.com/video/BV1iJ411E7xW?p=18&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     */
    public void insertSort(int[] arr){
        for (int i = 0; i < arr.length; i++) { //控制未排序的组，arr[i]表示未排序组的第一个数据。
            for (int j = i; j > 0; j--) { //控制已排序的组，向前遍历
                比较索引j处的值和索引j-1处的值，如果索引j-1处的值比索引j处的值大，则交换数据
                // 如果不大，那么就找到合适的位置了，退出循环即可；
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else {
                    break;
                }
            }
            System.out.println("未排序组第一个元素向前比较交换后的数组："+Arrays.toString(arr)+",i:"+i);
        }
        System.out.println("排序后："+ Arrays.toString(arr));
    }
}

5、希尔排序（高级排序）

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

时间复杂度：O(nlogn)，比插入排序快很多倍

希尔排序原理：
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组（按照增长量间隔到第几个数为一组）；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作

增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则

int h=1 while(h<5){ h=2h+1；//3,7 }//循环结束后我们就可以确定h的最大值； h的减小规则为： h=h/2

希尔排序图解：
注意：当h=5时，9和间隔的第5个元素4为一组，1和间隔的第5个元素8为一组，以此类推，根据增长量间隔分组。
待插入元素：根据增长量h为待插元素，例如当h=5时，9和4为一组，那么4为待插元素，1和8位一组，那么8为待插元素，以此类推。
分组排序：待插元素和组中的元素比较交换。
在这里插入图片描述

java代码实现：

/**
 * 希尔排序（插入排序的优化版,比插入排序快很多）,平均时间复杂度O(nlogn)
 */
public class ShellSort {

    public static void main(String[] args) {


        ShellSort shellSort = new ShellSort();
        System.out.println("=======希尔排序-交换法======");
        int[] arr = {5, 8, 6, 3, 9, 2, 1, 7};
        System.out.println("原始数据："+ Arrays.toString(arr));
        shellSort.shellSort(arr);
        System.out.println("希尔排序-交换法排序后："+ Arrays.toString(arr));

        System.out.println("\n\n");


        System.out.println("=======希尔排序-移位法======");
        int[] arr2 = {5, 8, 6, 3, 9, 2, 1, 7};
        System.out.println("原始数据："+ Arrays.toString(arr2));
        shellSort.shellSort2(arr2);
        System.out.println("希尔排序-移位法排序后："+ Arrays.toString(arr2));

    }


    /**
     * 1、希尔排序（插入排序的优化版,比插入排序快很多），此时使用交换法
     * 参考：<a href="https://www.bilibili.com/video/BV1iJ411E7xW?p=21&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     */
    public void shellSort(int[] arr){

        //根据arr长度，计算增长量（每次分组的长度间隔，就是间隔到第几个数为一组）的初始值。
        int h = 1;
        //初始值固定计算公式
        while (h < arr.length/2) {
            h = 2*h + 1;
        }
        //希尔排序，当增长量大于等于1的时候才循环，当h=1的时候说明已经排序完了
        while (h >= 1) {
            System.out.println("增长量h：" +h);
            //找出待插入的元素，待插入元素：按照增长量h分组，待插入元素在这一组的最后一个。
            // 也就是待插入元素在h下标或者h下标后面位置。所以i要从h开始。
            for (int i = h; i < arr.length; i++) {
                //把待插入的元素插入到有序数列中，这个和插入排序差不多，但是区别在于，希尔排序是和增长长度为h的组作比较。
                //由于第i（j,j=i）个元素是待插入值，因此和它前面组的元素j-h作比较交换。
                for (int j = i; j >= h; j-=h) {
                    //待插入的元素是a[j],比较a[j]和a[j-h]
                    if (arr[j-h] > arr[j]) {
                        int temp = arr[j];
                        arr[j] = arr[j-h];
                        arr[j-h] = temp;
                    } else {
                        //待插入元素已经找到了合适的位置，结束循环；
                        break;
                    }
                }
                System.out.println("每组待插入元素插入排序后：" + Arrays.toString(arr));
            }
            //减小h的值
            h = h/2;
        }
    }

    /**
     * 2、希尔排序-移位法，对交换法进行优化（实际上，效率速度上差不了多少,1千万级比数据,两个方式都是几秒就完成了，差别也在1、两秒内）
     * 参考：<a href="https://www.bilibili.com/video/BV1E4411H73v?p=65&spm_id_from=pageDriver&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     */
    public void shellSort2(int[] arr){
        //根据arr长度，计算增长量（每次分组的长度间隔，就是间隔到第几个数为一组）的初始值。
        int h = 1;
        //初始值固定计算公式（有一些是使用固定的arr.length / 2）
        while (h < arr.length / 2) {
            h = 2 * h +1;
        }
        //希尔排序，当增长量大于等于1的时候才循环，当h=1的时候说明已经排序完了
        while (h >= 1) {
            System.out.println("增长量h：" +h);
            //找出待插入的元素，待插入元素：按照增长量h分组，待插入元素在这一组的最后一个。
            // 也就是待插入元素在h下标或者h下标后面位置。所以i要从h开始。
            for (int i = h; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                //1、把待插入的元素插入到有序数列中，这个和插入排序差不多，但是区别在于，希尔排序是和增长长度为h的组作比较。
                //2、这里使用了移位法，先判断待插入元素是否比组中的前一位元素小，如果小的话就先将前面的在组向后移动一位，直到没有数比待插入元素大的数。
                //3、向移位后，有个位置数据就是空的了，将待插入元素直接放到这个位置。
                if (arr[j] < arr[j-h]){
                    while (j - h >= 0 && temp < arr[j-h]) {
                        //比待插入元素大的都向右移动一位
                        arr[j] = arr[j - h];
                        //下标向前移动一位（记住在组中数据间隔为H的位置）
                        j -=h;
                    }
                    //将待插入元素放到最后一个移位元素之前的位置。
                    arr[j] = temp;
                }
                System.out.println("每组待插入元素插入排序后：" + Arrays.toString(arr));
            }
            h = h/2;
        }
        
    }
}

6、归并排序（高级排序）

递归：定义方法时，在方法内部调用方法本身，称之为递归。

归并排序：是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序
表，称为二路归并。

时间复制度：O(nlogn)

归并排序的缺点：需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。

归并排序原理：

每次将数据拆分为尽可能元素个数相等的两组数，命名这两组数为子组，那两个子组继续按元素个数相等的拆分4个子组，按照这个规律，直到拆分为每一组只有一个数据。
然后将拆分后相邻的两个子组进行排序合并（归并），继续往上排序合并直到变为原来的一组数据。

排序合并原理：

创建一个空的辅助assist数组，两个子组A和B分别创建一个下标指针p1、p2，默认为子组A和子组B的第一个数下标，assist数组创建一个下标指针i，从子组A的p1和子组B的p2指针的数据进行比较，如果p1的数比p2小的话，则将p1的数放到assist数组的指针i处，然后子组A的p1指针加1向后移动一位，assist指针i加1，向后移动一位，否则p2比p1小，就是p2的数放到assist数组的指针i处，然后p2加1向后移动一位。继续遍历子组A和B的指针的数对比，当子组A下标p1走到A的结束位置，但子组B下标p2还没走到结束位置，这时候将子组B下标的数和剩下未走完的数按顺序放到assist数组后面，因为子组A和B都是排序的数组，A和B比较，A走完了，B剩下的数肯定是大于A的数了。如果是子组B下标走到B的结束位置，则和相反，和当子组A下标p1走到A的结束位置类推。
走完上述步骤后，子组A和子组B的数据合并在assist数组中了，这时候将assist数组合并的数据，复制代替原始数组的A和B数组下标的位置。

简单来说就是先拆后合

整体原理图解：
在这里插入图片描述

归并（合并时）原理
在这里插入图片描述

在这里插入图片描述

java代码实现：

/**
 * 归并排序，时间复杂度O(nlogn)
 */
public class MergeSort {

    //辅助数组
    private int[] assist;

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] a = {5, 8, 6, 3, 9, 2, 1, 7};
        System.out.println("原始数组："+ Arrays.toString(a));
        mergeSort.mergeSort(a);
        System.out.println("归并排序后数组："+ Arrays.toString(a));
    }

    /**
     * 归并排序
     * 参考：<a href="https://www.bilibili.com/video/BV1iJ411E7xW?p=25&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     */
    public void mergeSort(int[] arr){
        if (arr == null || arr.length == 0) {
            return;
        }
        //创建辅助数组
        assist = new int[arr.length];
        sort(arr,0,arr.length -1);
    }


    /**
     * 对数组a中从lo到hi的元素进行排序
     * @param arr
     * @param start
     * @param end
     */
    public void sort(int[] arr,int start,int end){
        //安全性校验，并且当分的组只有一个数的时候，此时 start 肯定等于 end。所以只有一个数的时候不能再分了。
        if (start >= end) {
            return;
        }
        //对数据进行分两组，计算中间位置，start 到 mid一组，mid + 1  到 end 一组
        int mid = start + (end - start) / 2; //防止溢出，原 （start + end）/2

        //左边一组，start 到 mid为一组，递归再次进行分组排序，最后分到只有一个数为一组了。
        sort(arr,start,mid);
        //右边一组，mid+1 到 end为一组，递归再次进行分组排序，最后分到只有一个数为一组了。
        sort(arr,mid + 1, end);

        //再把两个组中的数据进行归并。
        //由于上面sort方法递归分组，可以想象一下分到只有一个数为一组的时候，执行这个merge归并方法，这两个数合并后就是有序的，然后继续想象向上依次合并。
        merge(arr,start,mid,end);
    }

    /**
     * 将两个数组归并
     * 下标start 到 mid为一组A, 下标mid +1 到 end为一组B，将这两组数据进行归并
     *
     * @param arr
     * @param start
     * @param mid
     * @param end
     */
    public void merge(int[] arr,int start,int mid,int end) {
        //打印用
        printMergeBefore(arr,start,mid,end);

        //定义assist的下标指针
        int i = start;
        //定义 start 到 mid 数组的下标指针
        int p1 = start;
        //定义 mid + 1 到 end数组的下标指针
        int p2 = mid +1;

        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] < arr[p2]) {
                //当p1指针的数比p2小的话，将p1指针的数放到assist辅助数组。注意一下，i++先取i进行计算，再后自增，assist[i++] = assist[i]，i++;
                assist[i++] = arr[p1++];
            } else {
                //当p2指针的数比p1小的话，将p2指针的数放到assist辅助数组。
                assist[i++] = arr[p2++];
            }
        }

        //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while (p1 <= mid) {
            assist[i++] = arr[p1++];
        }
        //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while (p2 <= end) {
            assist[i++] = arr[p2++];
        }
        把辅助数组中的元素拷贝到原数组中
        for (int j = start; j <= end; j++) {
            arr[j] = assist[j];
        }

        //打印用
        printMergeAfter(arr,start,mid,end);

    }

    //打印
    public void printMergeBefore(int[] arr,int start,int mid,int end){
        StringBuffer aStr = new StringBuffer("左边组：[");
        for (int i = start; i <= mid; i++) {
            if (i > start) {
                aStr.append(",");
            }
            aStr.append(arr[i] + "");
        }
        aStr.append("]");

        aStr.append("   右边组：[");
        for (int i = mid + 1; i <= end; i++) {
            if (i > mid + 1) {
                aStr.append(",");
            }
            aStr.append(arr[i] + "");
        }
        aStr.append("]");
        System.out.println("归并前的数组：" + aStr.toString() +"    start:"+start+",mid:"+mid+",end:"+end);
    }

    //打印
    private void printMergeAfter(int[] arr,int start,int mid,int end){
        int[] printArr = new int[arr.length];
        System.arraycopy(arr,start,printArr,start,end - start +1);
        System.out.println("将两个数组归并后："+Arrays.toString(printArr));
    }

}

7、基数排序（高级排序）

基数排序：基数排序(Radix Sort)是桶排序的扩展，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。

时间复杂度：O(n + K)，k：桶的个数

基数排序原理：

创建10个桶，每个桶的内容是装数组，由于数字都是0到9的数，因此需要10个桶，10个桶对应的下标为0到9；
第一步遍历原始数组，先计算数组的每个数的个位数是什么，根据每个数的个位数和10个桶对应的下标，将数放到对应的桶中，例如542的个位数是2，那么将542放到下标为2的桶里面。依次类推，直到数组所有的数都放到桶里面。
第二步，再将桶里装的数组，从下标0到9的顺序把桶里数据取出来，依次放回到数组中，这时候数组就按个位数实现了排序。
依次类推，从上面第一步开始，不过这时候计算的是数组中每个数的10位数是什么了，然后按10位数的数字放到对应的桶中，再从桶放回数据，由于之前已经按个位数排序过，不难发现，这时候数组已经按个位和10位数排序了。
就这样按着数组中最大的数的位数，进行上面一轮轮放入桶再从桶中顺序拿出来，最终实现了数组的排序。

基数排序图解：
在这里插入图片描述

在这里插入图片描述

java代码实现：

/**
 * 基数排序，时间复杂度O(n + K)，k：桶的个数
 * 基数排序是使用空间换时间的经典算法
 */
public class RadixSort {

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int[] arr = { 53, 3, 542, 748, 14, 214, 64, 46};
        System.out.println("基数排序前 " + Arrays.toString(arr));
        radixSort.radixSort(arr);
        System.out.println("基数排序后 " + Arrays.toString(arr));

    }


    /**
     * 基数排序
     * 基数排序是使用空间换时间的经典算法
	 * 参考：<a href="https://www.bilibili.com/video/BV1E4411H73v?p=72&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     */
    public void radixSort(int [] arr){

        //得到数组中最大的数的位数
        int maxVal = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (maxVal < arr[i]) {
                maxVal = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLen = (maxVal + "").length();

        //定义一个二维数组，表示10个桶，和桶里装的数组。由于每位数都是0到9个数字，因此需要10个桶装。
        //bucket[x][y]，一维下标x表示桶的下标，二维y表示桶转的数组数据的下标，存arr放的数据。
        //比如将[53, 14, 748]数组，按第一轮放时，由于53个位数是3，14的个位数是4,748的个位数是8，
        //因此将53放到下标为3的桶bucket[3][0]，将14放到下标为4的桶bucket[4][0]，将748放到下标为8的桶bucket[8][0]
        //基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];

        //记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数（有效计数）
        //可以这里理解比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        for (int i = 0,n = 1; i < maxLen; i++,n *= 10) {

            //第一步，针对对应的位数，先将数据放入对应的桶里面
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素对应的位的值
                int bucketIndex = arr[j] / n % 10;
                //这里有点难理解，bucket[bucketIndex]就是元素的位数对应放哪个桶，bucketElementCounts[bucketIndex]实际是对应bucket一个桶里面装的数组个数。
                //bucketElementCounts[bucketIndex] 默认值是0，因此桶bucket第一次放数据是，bucket[bucketIndex][0]。
                //一个桶中的数组每装一个数，bucket[bucketIndex]计数就会加1，因此，这样运用很好，省去再做遍历的麻烦。
                bucket[bucketIndex][bucketElementCounts[bucketIndex]] = arr[j];
                bucketElementCounts[bucketIndex]++; //放入数据后，bucketElementCounts的计数有效值加1;
            }
            //定义arr的下标
            int index = 0;
            //第二步，再将所有桶里的数据取出来，按桶顺序放回arr中，这就实现对数组的数按某一位进行的排序。
            for (int j = 0; j < bucketElementCounts.length; j++) {

                if (bucketElementCounts[j] == 0) {
                    continue;
                }
                //循环该桶即第j个桶(即第k个一维数组), 放入
                for (int k = 0; k < bucketElementCounts[j]; k++) {
                    取出元素放入到arr，index下标自增。
                    arr[index++] = bucket[j][k];
                }

                //从桶bucket里拿出数据后，将计数重置为0，避免下一轮循环导致错乱。
                bucketElementCounts[j] = 0;
            }
        }


    }
}

四、查找算法

1、二分查找（折半查找）

二分查找：数据必须有序，也叫折半查找，一种效率较高的查找方法。

二分查找原理：

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

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

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

二分查找图解：
在这里插入图片描述

java代码实现：

/**
 * 二分查找（折半查找）
 */
public class BinarySearch {


    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int[] arr = {10, 15, 16, 17, 20 , 20, 21, 26, 90};
        System.out.println("二分查找数组："+ Arrays.toString(arr));
        int result = binarySearch.binarySearch(arr,0,arr.length -1,20);
        System.out.println("二分查找-递归方式结果：" + result);
        System.out.println("\n\n");
        int result2 = binarySearch.binarySearch2(arr,0,arr.length -1,20);
        System.out.println("二分查找-普通方式结果：" + result2);


        List<Integer> resultList = binarySearch.binarySearch3(arr,0,arr.length -1,20);
        System.out.println("二分查找-递归方式优化结果：" + resultList);

    }


    /**
     * 一、二分查找-递归方式
     * （1）需要数组有序
     * （2）根据数组长度，左边下标left和右边下标right计算中间下标mid的值，判断中间下标mid值是否比查找的值findVal小，如果小的话，将右边指针right移动中间值下标mid-1处。
     * （3）如果大的话，则将左边下标left移动到中间下标mid + 1处。
     * （4）继续从左边值下标left和右边值下标right计算出新的中间下标mid的值，再判断新的中间值是否比查找值小或者大。
     * （5）依次类推，不断比较left和right的中间下标的mid值，然后移动左边下标left或者右边下标right，重新计算中间下标mid，然后和查找值findVal作比较，
     * （6）直到找出和mid相等的值，或者找不到该值，结束。
     *  参考：<a href="https://www.bilibili.com/video/BV1E4411H73v?p=78&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr 查找的数组
     * @param left 左下标
     * @param right 右下标
     * @param findVal 查找的值
     * @return
     */
    public int binarySearch(int[] arr,int left,int right,int findVal) {

        if (left > right) {
            return -1;
        }
        //计算中间下标
        int mid = (left + right) / 2;
        //中间值
        int midVal = arr[mid];
        System.out.println("每次查找{ left:"+left+",right:"+right+",mid:"+mid+",midVal:"+midVal);
        //如果查找值比中间值小的话，移动右下标right到中间下标-1出，再递归重新计算中间值和比较
        if (findVal < midVal) {
            return binarySearch(arr,left,mid -1,findVal);
        } else if (findVal > midVal) {  //如果查找值比中间值大的话，移动左下标left到中间下标-1出，再递归重新计算中间值和比较
            return binarySearch(arr,mid + 1,right,findVal);
        } else {
            //找到中间值和查找值相等，返回中间值下标
            return mid;
        }

    }


    /**
     * 二、二分查找-普通方式
     * @param arr  查找的数组
     * @param left 左下标
     * @param right 右下标
     * @param findVal 查找的值
     * @return
     */
    public int binarySearch2(int[] arr,int left,int right,int findVal){
        //定义中间值下标
        int mid;
        //循环条件当左下标等于或者小于右下标,如果循环结束后没有找到，说明查找值不在数组中。
        while (left <= right) {

            //计算中间值
            mid = (left + right)/2;
            System.out.println("每次查找{ left:"+left+",right:"+right+",mid:"+mid+",midVal:"+arr[mid]);
            //中间值和查找值相等，找到了查找值，返回下标
            if (arr[mid] == findVal) {
                return mid;
            } else if (findVal < arr[mid] ) {//中间值比查找值小，移动rigt下标到中间下标-1处找
                right = mid - 1;
            } else if (findVal > arr[mid]) {//中间值比查找值小，移动left下标到中间下标+1处找
                left = mid + 1;
            }

        }
        //查找不到返回-1
        return -1;

    }


    /**
     * 三、二分查找-递归方式优化
     * （1）在数组有重复多个数据的情况下，上面的方式只能找到其中一个数的下标，因此优化一下使能够返回所有找到的数的下标。
     * （2）思路：
     * （3）在找到mid索引值，不要马上返回
     * （4）向mid索引值的左边扫描，将所有满足的元素的下标，加入集合ArrayList中
     * （5）向mid索引值的有边扫描，将所有满足的元素的下标，加入集合ArrayList中
     * （6）将Arraylist返回
     * 参考：<a href="https://www.bilibili.com/video/BV1E4411H73v?p=80&vd_source=548b27fee009b7ca3bfb319772b8d3e7">...</a>
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public List<Integer> binarySearch3(int[] arr,int left,int right,int findVal) {

        if (left > right) {
            return new ArrayList<Integer>();
        }
        //计算中间下标
        int mid = (left + right) / 2;
        //中间值
        int midVal = arr[mid];
        System.out.println("每次查找{ left:"+left+",right:"+right+",mid:"+mid+",midVal:"+midVal);
        //如果查找值比中间值小的话，移动右下标right到中间下标-1出，再递归重新计算中间值和比较
        if (findVal < midVal) {
            return binarySearch3(arr,left,mid -1,findVal);
        } else if (findVal > midVal) {  //如果查找值比中间值大的话，移动左下标left到中间下标-1出，再递归重新计算中间值和比较
            return binarySearch3(arr,mid + 1,right,findVal);
        } else {
//			 * 1. 在找到mid 索引值，不要马上返回
//			 * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
//			 * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
//			 * 4. 将Arraylist返回

            List<Integer> resIndexlist = new ArrayList<Integer>();
            //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合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 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            temp = mid + 1;
            while(true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
                    break;
                }
                //否则，就temp 放入到 resIndexlist
                resIndexlist.add(temp);
                temp += 1; //temp右移
            }

            return resIndexlist;
        }

    }

}