• day21算法

    常见的七种查找算法：

    ​ 数据结构是数据存储的方式，算法是数据计算的方式。所以在开发中，算法和数据结构息息相关。今天的讲义中会涉及部分数据结构的专业名词，如果各位铁粉有疑惑，可以先看一下哥们后面录制的数据结构，再回头看算法。

    1. 基本查找

    ​ 也叫做顺序查找

    ​ 说明：顺序查找适合于存储结构为数组或者链表。

    基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。

    示例代码：

    public class A01_BasicSearchDemo1 {
    public static void main(String[] args) {
        //基本查找/顺序查找
        //核心：
        //从0索引开始挨个往后查找

        //需求：定义一个方法利用基本查找，查询某个元素是否存在
        //数据如下：{131, 127, 147, 81, 103, 23, 7, 79}


        int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};
        int number = 82;
        System.out.println(basicSearch(arr, number));

    }

    //参数：
    //一：数组
    //二：要查找的元素

    //返回值：
    //元素是否存在
    public static boolean basicSearch(int[] arr, int number){
        //利用基本查找来查找number在数组中是否存在
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number){
                return true;
            }
        }
        return false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    2. 二分查找

    ​ 也叫做折半查找

    说明：元素必须是有序的，从小到大，或者从大到小都是可以的。

    如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。

    基本思想：也称为是折半查找，属于有序查找算法。用给定值先与中间结点比较。比较完之后有三种情况：

    • 相等

      说明找到了

    • 要查找的数据比中间节点小

      说明要查找的数字在中间节点左边

    • 要查找的数据比中间节点大

      说明要查找的数字在中间节点右边

    代码示例：

    package com.itheima.search;

public class A02_BinarySearchDemo1 {
    public static void main(String[] args) {
        //二分查找/折半查找
        //核心：
        //每次排除一半的查找范围

        //需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
        //数据如下：{7, 23, 79, 81, 103, 127, 131, 147}

        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(binarySearch(arr, 150));
    }

    public static int binarySearch(int[] arr, int number){
        //1.定义两个变量记录要查找的范围
        int min = 0;
        int max = arr.length - 1;

        //2.利用循环不断的去找要查找的数据
        while(true){
            if(min > max){
                return -1;
            }
            //3.找到min和max的中间位置
            int mid = (min + max) / 2;
            //4.拿着mid指向的元素跟要查找的元素进行比较
            if(arr[mid] > number){
                //4.1 number在mid的左边
                //min不变，max = mid - 1；
                max = mid - 1;
            }else if(arr[mid] < number){
                //4.2 number在mid的右边
                //max不变，min = mid + 1;
                min = mid + 1;
            }else{
                //4.3 number跟mid指向的元素一样
                //找到了
                return mid;
            }

        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    3. 插值查找

    在介绍插值查找之前，先考虑一个问题：

    ​ 为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？

    其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？

    二分查找中查找点计算如下：

    mid=(low+high)/2, 即mid=low+1/2*(high-low);

    我们可以将查找的点改进为如下：

    mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

    这样，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

    基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

    **细节：**对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

    代码跟二分查找类似，只要修改一下mid的计算方式即可。

    4. 斐波那契查找

    在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

    黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

    0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

    在数学中有一个非常有名的数学规律：斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….

    （从第三个数开始，后边每一个数都是前两个数的和）。

    然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

    img

    基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

    斐波那契查找也是在二分查找的基础上进行了优化，优化中间点mid的计算方式即可

    代码示例：

    public class FeiBoSearchDemo {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(search(arr, 1234));
    }

    public static int[] getFeiBo() {
        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;
    }

    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        //表示斐波那契数分割数的下标值
        int index = 0;
        int mid = 0;
        //调用斐波那契数列
        int[] f = getFeiBo();
        //获取斐波那契分割数值的下标
        while (high > (f[index] - 1)) {
            index++;
        }
        //因为f[k]值可能大于a的长度，因此需要使用Arrays工具类，构造一个新法数组，并指向temp[],不足的部分会使用0补齐
        int[] temp = Arrays.copyOf(arr, f[index]);
        //实际需要使用arr数组的最后一个数来填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while循环处理，找到key值
        while (low <= high) {
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {//向数组的前面部分进行查找
                high = mid - 1;
                /*
                  对k--进行理解
                  1.全部元素=前面的元素+后面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因为前面有k-1个元素没所以可以继续分为f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面继续查找k--
                  即下次循环,mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {//向数组的后面的部分进行查找
                low = mid + 1;
                index -= 2;
            } else {//找到了
                //需要确定返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    5. 分块查找

    当数据表中的数据元素很多时，可以采用分块查找。

    汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找

    分块查找适用于数据较多，但是数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找

    分块查找的过程：

    1. 需要把数据分成N多小块，块与块之间不能有数据重复的交集。
    2. 给每一块创建对象单独存储到数组当中
    3. 查找数据的时候，先在数组查，当前数据属于哪一块
    4. 再到这一块中顺序查找

    代码示例：

    package com.itheima.search;

public class A03_BlockSearchDemo {
    public static void main(String[] args) {
        /*
            分块查找
            核心思想：
                块内无序，块间有序
            实现步骤：
                1.创建数组blockArr存放每一个块对象的信息
                2.先查找blockArr确定要查找的数据属于哪一块
                3.再单独遍历这一块数据即可
        */
        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //创建三个块的对象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定义数组用来管理三个块的对象（索引表）
        Block[] blockArr = {b1,b2,b3};

        //定义一个变量用来记录要查找的元素
        int number = 37;

        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(blockArr,arr,number);

        //打印一下
        System.out.println(index);



    }

    //利用分块查找的原理，查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.确定number是在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);

        if(indexBlock == -1){
            //表示number不在数组当中
            return -1;
        }

        //2.获取这一块的起始索引和结束索引   --- 30
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        //3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        return -1;
    }


    //定义一个方法，用来确定number在哪一块当中
    public static int findIndexBlock(Block[] blockArr,int number){ //100


        //从0索引开始遍历blockArr，如果number小于max，那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }



}

class Block{
    private int max;//最大值
    private int startIndex;//起始索引
    private int endIndex;//结束索引


    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149

    6. 哈希查找

    哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。

    一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体

    在课程中，为了让大家方便理解，所以规定：

    • 数组的0索引处存储1~100
    • 数组的1索引处存储101~200
    • 数组的2索引处存储201~300
    • 以此类推

    但是实际上，我们一般不会采取这种方式，因为这种方式容易导致一块区域添加的元素过多，导致效率偏低。

    更多的是先计算出当前数据的哈希值，用哈希值跟数组的长度进行计算，计算出应存入的位置，再挂在数组的后面形成链表，如果挂的元素太多而且数组长度过长，我们也会把链表转化为红黑树，进一步提高效率。

    具体的过程，大家可以参见B站阿玮讲解课程：从入门到起飞。在集合章节详细讲解了哈希表的数据结构。全程采取动画形式讲解，让大家一目了然。

    在此不多做阐述。

    7. 树表查找

    本知识点涉及到数据结构：树。

    建议先看一下后面阿玮讲解的数据结构，再回头理解。

    基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

    二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree），具有下列性质的二叉树：

    1）若任意节点左子树上所有的数据，均小于本身；

    2）若任意节点右子树上所有的数据，均大于本身；

    二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

    ​ 不同形态的二叉查找树如下图所示：

    在这里插入图片描述

    基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

    具体细节大家可以参见B站阿玮讲解课程：从入门到起飞。在集合章节详细讲解了树数据结构。全程采取动画形式讲解，让大家一目了然。

    在此不多做阐述。

    ​ 不管是二叉查找树，还是平衡二叉树，还是红黑树，查找的性能都比较高

    十大排序算法：

    1. 冒泡排序

    冒泡排序（Bubble Sort）也是一种简单直观的排序算法。

    它重复的遍历过要排序的数列，一次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。

    这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到最后面。

    当然，大家可以按照从大到小的方式进行排列。

    1.1 算法步骤

    1. 相邻的元素两两比较，大的放右边，小的放左边
    2. 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
    3. 如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以

    1.2 动图演示

    在这里插入图片描述

    1.3 代码示例

    public class A01_BubbleDemo {
    public static void main(String[] args) {
        /*
            冒泡排序：
            核心思想：
            1，相邻的元素两两比较，大的放右边，小的放左边。
            2，第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推。
            3，如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以。
        */


        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用冒泡排序将数组中的数据变成 1 2 3 4 5

        //外循环：表示我要执行多少轮。 如果有n个数据，那么执行n - 1 轮
        for (int i = 0; i < arr.length - 1; i++) {
            //内循环：每一轮中我如何比较数据并找到当前的最大值
            //-1：为了防止索引越界
            //-i：提高效率，每一轮执行的次数应该比上一轮少一次。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //i 依次表示数组中的每一个索引：0 1 2 3 4
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        printArr(arr);




    }

    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    2. 选择排序

    2.1 算法步骤

    1. 从0索引开始，跟后面的元素一一比较
    2. 小的放前面，大的放后面
    3. 第一次循环结束后，最小的数据已经确定
    4. 第二次循环从1索引开始以此类推
    5. 第三轮循环从2索引开始以此类推
    6. 第四轮循环从3索引开始以此类推。

    2.2 动图演示

    在这里插入图片描述

    public class A02_SelectionDemo {
    public static void main(String[] args) {

        /*
            选择排序：
                1，从0索引开始，跟后面的元素一一比较。
                2，小的放前面，大的放后面。
                3，第一次循环结束后，最小的数据已经确定。
                4，第二次循环从1索引开始以此类推。

         */


        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};


        //2.利用选择排序让数组变成 1 2 3 4 5
       /* //第一轮：
        //从0索引开始，跟后面的元素一一比较。
        for (int i = 0 + 1; i < arr.length; i++) {
            //拿着0索引跟后面的数据进行比较
            if(arr[0] > arr[i]){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
            }
        }*/

        //最终代码：
        //外循环：几轮
        //i:表示这一轮中，我拿着哪个索引上的数据跟后面的数据进行比较并交换
        for (int i = 0; i < arr.length -1; i++) {
            //内循环：每一轮我要干什么事情？
            //拿着i跟i后面的数据进行比较交换
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }


        printArr(arr);


    }
    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    3. 插入排序

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。

    插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找

    3.1 算法步骤

    将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。

    遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

    N的范围：0~最大索引

    3.2 动图演示

    在这里插入图片描述

    package com.itheima.mysort;


public class A03_InsertDemo {
    public static void main(String[] args) {
        /*
            插入排序：
                将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
                遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
                N的范围：0~最大索引

        */
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到无序的哪一组数组是从哪个索引开始的。  2
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i + 1]){
                startIndex = i + 1;
                break;
            }
        }

        //2.遍历从startIndex开始到最后一个元素，依次得到无序的哪一组数据中的每一个元素
        for (int i = startIndex; i < arr.length; i++) {
            //问题：如何把遍历到的数据，插入到前面有序的这一组当中

            //记录当前要插入数据的索引
            int j = i;

            while(j > 0 && arr[j] < arr[j - 1]){
                //交换位置
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }

        }
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    4. 快速排序

    快速排序是由东尼·霍尔所发展的一种排序算法。

    快速排序又是一种分而治之思想在排序算法上的典型应用。

    快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！

    它是处理大数据最快的排序算法之一了。

    4.1 算法步骤

    1. 从数列中挑出一个元素，一般都是左边第一个数字，称为 “基准数”;
    2. 创建两个指针，一个从前往后走，一个从后往前走。
    3. 先执行后面的指针，找出第一个比基准数小的数字
    4. 再执行前面的指针，找出第一个比基准数大的数字
    5. 交换两个指针指向的数字
    6. 直到两个指针相遇
    7. 将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。
    8. 第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。
    9. 把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序

    4.2 动图演示

    在这里插入图片描述

    package com.itheima.mysort;

import java.util.Arrays;

public class A05_QuickSortDemo {
  public static void main(String[] args) {
      System.out.println(Integer.MAX_VALUE);
      System.out.println(Integer.MIN_VALUE);
    /*
      快速排序：
          第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。
          比基准数小的全部在左边，比基准数大的全部在右边。
          后面以此类推。
    */

      int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};


      //int[] arr = new int[1000000];

     /* Random r = new Random();
      for (int i = 0; i < arr.length; i++) {
          arr[i] = r.nextInt();
      }*/


      long start = System.currentTimeMillis();
      quickSort(arr, 0, arr.length - 1);
      long end = System.currentTimeMillis();

      System.out.println(end - start);//149

      System.out.println(Arrays.toString(arr));
      //课堂练习：
      //我们可以利用相同的办法去测试一下，选择排序，冒泡排序以及插入排序运行的效率
      //得到一个结论：快速排序真的非常快。

     /* for (int i = 0; i < arr.length; i++) {
          System.out.print(arr[i] + " ");
      }*/

  }


  /*
   *   参数一：我们要排序的数组
   *   参数二：要排序数组的起始索引
   *   参数三：要排序数组的结束索引
   * */
  public static void quickSort(int[] arr, int i, int j) {
      //定义两个变量记录要查找的范围
      int start = i;
      int end = j;

      if(start > end){
          //递归的出口
          return;
      }



      //记录基准数
      int baseNumber = arr[i];
      //利用循环找到要交换的数字
      while(start != end){
          //利用end，从后往前开始找，找比基准数小的数字
          //int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8};
          while(true){
              if(end <= start || arr[end] < baseNumber){
                  break;
              }
              end--;
          }
          System.out.println(end);
          //利用start，从前往后找，找比基准数大的数字
          while(true){
              if(end <= start || arr[start] > baseNumber){
                  break;
              }
              start++;
          }



          //把end和start指向的元素进行交换
          int temp = arr[start];
          arr[start] = arr[end];
          arr[end] = temp;
      }

      //当start和end指向了同一个元素的时候，那么上面的循环就会结束
      //表示已经找到了基准数在数组中应存入的位置
      //基准数归位
      //就是拿着这个范围中的第一个数字，跟start指向的元素进行交换
      int temp = arr[i];
      arr[i] = arr[start];
      arr[start] = temp;

      //确定6左边的范围，重复刚刚所做的事情
      quickSort(arr,i,start - 1);
      //确定6右边的范围，重复刚刚所做的事情
      quickSort(arr,start + 1,j);

  }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105

    常见算法 API-Arrays

    在这里插入图片描述

    方法名说明
    public static String toString(数组)把数组拼接成一个字符串
    public static int binarySearch(数组，查找的元素)二分查找法查找元素
    public static int[] copyOf(原数组,新数组长度)拷贝数组
    public static int[]copyOfRange(原数组,起始索引,结束索引)拷贝数组（指定范围)
    public static void fill(数组,元素)填充数组
    public static void sort(数组)按照默认方式进行数组排序
    public static void sort(数组，排序规则)按照指定的规则排序
    //toString函数的底层实现原理和之前写的toString函数是一样的原理，有时间的话就去看看源码
system.out.print1n("-----------------toString-------------------");
int[] arr = {1，2，3，4，5，6，7，8，9，10};
system.out.print1n(Arrays.toString(arr));//[1，2，3，4，5，6，7，8，9，10]

    • 1
    • 2
    • 3
    • 4
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//binarySearch:二分查找法查找元素
//细节1:二分查找的前提:数组中的元素必须是有序，数组中的元素必须是升序的
//细节2:如果要查找的元素是存在的，那么返回的是真实的索引
//但是，如果要查找的元素是不存在的，返回的是-插入点- 1//疑问:为什么要减1呢?
//解释:如果此时，我现在要查找数字e，那么如果返回的值是-插入点，就会出现问题了。
//如果要查找数字0，此时0是不存在的，但是按照上面的规则-插入点，应该就是-0
//为了避免这样的情况，Java在这个基础上又减一。
system.out.println("------------------binarySearch------------------");
system.out.print1n(Arrays.binarySearch(arr,key: 10)); //9
system.out.print1n(Arrays.binarySearch(arr，key: 2)); // 1
system.out.print1n(Arrays.binarySearch(arr，key: 20)); // -11

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    // copyof:拷贝数组
//参数一:老数组
//参数二:新数组的长度
//方法的底层会根据第二个参数来创建新的数组
//如果新数组的长度是小于老数组的长度，会部分拷贝//如果新数组的长度是等于老数组的长度，会完全拷贝
//如果新数组的长度是大于老数组的长度，会补上默认初始值
system.out.print1n("-------------------copyof-----------------");
int[] newArr1 = Arrays.copyof(arr, 20);
system. out.print1n(Arrays.toString(newArr1));//[1，2，3，4，5，6，7，8，9，10]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    // copyOfRange:拷贝数组(指定范围)
//细节:包头不包尾，包左不包右
system.out.print1n("-------------------copyofRange-------");
int[] newArr2 = Arrays.copyofRange(arr, 0, 9);
system.out.println(Arrays.toString(newArr2));//[1，2，3，4，5，6，7，8，9]

    • 1
    • 2
    • 3
    • 4
    • 5
    //fill:填充数组
//这种函数的底层实现原理是非常的简单，有时间可以看看这个函数的源码
system.out.println("------");
Arrays.fill(arr, 10e);
system.out.print1n(Arrays.toString(arr));

    • 1
    • 2
    • 3
    • 4
    • 5
    //sort:排序。默认情况下，给基本数据类型进行升序排列。底层使用的是快速排序.
system.out.println("--------------------sort---------------------");
int[] arr2 = {10，2，3，5，6，1，7，8,4，9};
Arrays.sort(arr2);
system.out.print1n(Arrays.toString(arr2));//[1，2，3，4,，5，6，7，8， 9，10]

    • 1
    • 2
    • 3
    • 4
    • 5
    /*
public static void sort(数组，排序规则)
按照指定的规则排序
参数一:要排序的数组
参数二:排序的规则细节:
只能给引用数据类型的数组进行排序
如果数组是基本数据类型的,需要变成其对于的包装类
*/

Integer[] arr = {2，3，1，5，6，7，8，4，9};

//第二个参数是一个接口，所以我们在调用方法的时候，需要传递这个接口的实现类对象，作为排序的规则。
//但是这个实现类，我只要使用一次，所以就没有必要单独的去写一个类，直接采取匿名内部类的方式就可以了
//底层原理:
//利用插入排序 + 二分查找的方式进行排序的。
//默认把0索引的数据当做是有序的序列，1索引到最后认为是无序的序列。
//遍历无序的序列得到里面的每一个元素，假设当前遍历得到的元素是A元素
//把A往有序序列中进行插入，在插入的时候，是利用二分查找确定A元素的插入点。
//拿着A元素，跟插入点的元素进行比较，比较的规则就是compare方法的方法体
//如果方法的返回值是负数，拿着A继续跟前面的数据进行比较
//如果方法的返回值是正数，拿着A继续跟后面的数据进行比较
//如果方法的返回值是0，也拿着A跟后面的数据进行比较
//直到能确定A的最终位置为止。

// compare方法的形式参数:
//参数一 o1:表示在无序序列中，遍历得到的每一个元素
//参数二 o2:有序序列中的元素

//返回值:
//负数:表示当前要插入的元素是小的，放在前面
//正数:表示当前要插入的元素是大的，放在后面
//0:表示当前要插入的元素跟现在的元素比是一样的们也会放在后面

//简单理解:
//o1 - o2 :升序排列
//o2 - o1 :降序排序

//Integer[] arr = {2, 3, 1, 5, 6, 7, 8, 4, 9};
Arrays.sort(arr, new Comparator<Integer>() {
@override
public int compare( Integer o1, Integer o2) {
	// system.out.print1n("------------------");
    // system.out.print1n("o1 : " +o1);
	// system.out.print1n("o2 : " +o2);
    return o1 - o2;
}
});

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    Lambda表达式

    // 这样写代码比较多，还是比较的麻烦，可以用Lambda表达式来简化代码
Arrays.sort(arr, new Comparator<Integer>() {
    @override
	public int compare(Integer o1, Integer o2) {
		return o1 - o2;
	}
});
Arrays.sort(arr, (Integer o1, Integer o2) -> {
		return o1 - o2;
	}
);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    函数式编程

    函数式编程( Functional programming）是一种思想特点。

    面向对象: 先找对象，让对象做事情。

    函数式编程思想，忽略面向对象的复杂语法，强调做什么，而不是谁去做。

    而我们要学习的Lambda表达式就是函数式思想的体现。

    Lambda表达式的标准格式

    Lambda表达式是JDK8开始后的一种新语法形式。

    注意点:

    1. Lambda表达式可以用来简化匿名内部类的书写
    2. Lambda表达式只能简化函数式接口的匿名内部类的写法
    3. 函数式接口:有且仅有一个抽象方法的接口叫做函数式接口，接口上方可以加 @Functionallnterface 注解
    public class test11 {
    public static void main(String[] args) {
        // 如果函数的参数是一个接口，其参数就必须安排一个实例化的接口对象
/*        method(new swim(){
        @Override
        public void swimming() {
            System.out.println("正在游泳~~~" );
        }
    });*/

        method(
                ()->{
                    System.out.println("正在游泳！");
                }
        );

    }
    public static void method (swim s){
        s.swimming();
    }

}
interface swim{
    public abstract void swimming();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    /*
lambda的省略规则:
1.参数类型可以省略不写。
2.如果只有一个参数，参数类型可以省略，同时()也可以省略。
3.如果Lambda表达式的方法体只有一行，大括号，分号，return可以省略不写，需要同时省略。
*/
Integer[] arr = {2, 3, 1, 5, 6, 7, 8, 4, 9};
Arrays.sort( arr, new comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
	return o1 - o2;
});
// lambda完整格式
Arrays.sort(arr, (Integer o1, Integer o2) -> {
	return o1 - o2;
}
);
// lambda省略写法
Arrays.sort(arr, (o1, o2) -> o1 - o2);


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    关于Lambda表达式的小练习
    /*
定义数组并存储一些字符串，利用Arrays中的sort方法进行排序
要求:
按照字符串的长度进行排序，短的在前面，长的在后面。
(暂时不比较字符串里面的内容)
*/
string[] arr = {"a", "aaaa", "aaa", "aa"};
//如果以后我们要把数组中的数据按照指定的方式进行排列，就需要用到sort方法，而且要指定排序的规则

/*Arrays.sort(arr, new Comparator( ) {
@Override
public int compare(String o1，string o2) i
//字符串的长度进行排序
return o1.length() - o2.length( );
}
});

// Lambda 完整格式
Arrays.sort(arr,(string o1，string o2)-> {
return o1.length() - o2.length( );
}
);*/

// Lambda简写格式
//小括号:数据类型可以省略，如果参数只有一个，小括号还可以省略
//大括号:如果方法体只有一行，return，分号，大括号都可以省略
Arrays.sort(arr,(o1,o2)-> o1.length() - o2.length());

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    小案例

    定义数组并存储一些女朋友对象，利用Arrays中的sort方法进行排序

    要求1:属性有姓名、年龄、身高。

    要求2:按照年龄的大小进行排序，年龄一样，按照身高排序，身高一样按照姓名的字母进行排序。

    (姓名中不要有中文或特殊字符，会涉及到后面的知识)

    public class Girlfriend {
    public String name;
    public int age;
    public double height;

    public Girlfriend() {
    }

    public Girlfriend(String name, int age, double height) {
        this.name = name;
        this.age = age;
        this.height = height;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    import java.util.Arrays;
import java.util.Comparator;

public class test12 {
    public static void main(String[] args) {
        //1.创建三个女朋友的对象
        Girlfriend gf1 = new Girlfriend("xiaoshishi", 18, 1.67);
        Girlfriend gf2 = new Girlfriend("xiaodandan", 19, 1.72);
        Girlfriend gf3 = new Girlfriend("xiaohuihui", 19, 1.78);
        Girlfriend gf4 = new Girlfriend("abc", 19, 1.78);

        //2.定义数组存储女朋友的信息
        Girlfriend[] arr = {gf1, gf2, gf3, gf4};

        //3.利用Arrays中的sort方法进行排序//匿名内部类lambda表达式
        Arrays.sort(arr, new Comparator<Girlfriend>() {
            @Override
            public int compare(Girlfriend o1, Girlfriend o2) {
                //按照年龄的大小进行排序，年龄一样，按照身高排序，身高一样按照姓名的字母进行排序。
                double temp = o1.age - o2.age;
                temp = temp == 0 ? o1.height - o2.height : temp;
                temp = temp == 0 ? o1.name.compareTo(o2.name) : temp;
                if (temp > 0) {
                    return 1;
                } else if (temp < 0) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        // lambda表达式
        // () -> {}
        // ():对应着抽象方法的形参
        // {}:方法体

        Arrays.sort(arr, (Girlfriend o1, Girlfriend o2) -> {
                //按照年龄的大小进行排序，年龄一样，按照身高排序，身高一样按照姓名的字母进行排序。
                double temp = o1.age - o2.age;
                temp = temp == 0 ? o1.height - o2.height : temp;
                temp = temp == 0 ? o1.name.compareTo(o2.name) : temp;
                if (temp > 0) {
                    return 1;
                } else if (temp < 0) {
                    return -1;
                } else {
                    return 0;
                }
            }
        );
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
  • 相关阅读:
    AOP面向切面编程
    自学（黑客技术）——网络安全
    带你玩转 Redis 的 SortedSet 数据类型
    推荐系统 | 基础推荐模型 | GBDT+LR模型 | Python实现
    Flask框架-2-[单聊]: flask-socketio实现websocket的功能，实现单对单聊天，flask实现单聊功能
    【系统分析师之路】第十五章 复盘数据库系统（数据库案例分析）
    附导读 |《网络安全标准实践指南——网络数据安全风险评估实施指引》解读
    【UE5】物体沿样条线移动
    【动态规划】583. 两个字符串的删除操作、72. 编辑距离
    Go语言进化之路：泛型的崛起与复用的新篇章
  • 原文地址：https://blog.csdn.net/WU3087676106/article/details/132955531