常见算法

查找算法

基本查找

练习：

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

（源代码）

package com.itheima.search;

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


}

（运行结果截图）

二分查找/折半查找

练习：

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

（源代码）

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, 81));


    }


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

        }
    }

}

（运行结果截图）

总结

插值查找

斐波那契查找

总结

分块查找

练习：

（源代码）

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
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2

        //从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，如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以。

练习：

（源代码）

package com.itheima.mysort;

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

（运行结果截图）

选择排序

例如：

练习：

（源代码）

package com.itheima.mysort;

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

}

（运行结果截图）

插入排序

练习：

（源代码）

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

}

（运行结果截图）

快速排序

递归算法

什么是递归?

        递归指的是方法中调用方法本身的现象

package com.itheima.mysort;

public class A04_RecursionDemo1 {
    public static void main(String[] args) {
        method();
    }


    public static void method(){
        method();
    }
}

递归算法的作用

书写递归算法的两个核心

练习：递归求和

（源代码）

package com.itheima.mysort;

public class A04_RecursionDemo2 {
    public static void main(String[] args) {
        //需求：利用递归求1-100之间的和
        //100 + 99 + 98 + 97 + 96 + 95 .... + 2 + 1

        //大问题拆解成小问题
        //1~100之间的和 = 100 + （1~99之间的和）
        //1~99之间的和 = 99 + （1~98之间的和）
        //1~98之间的和 = 98 + （1~97之间的和）
        //。。。
        //1~2之间的和 = 2 + （1~1之间的和）
        //1~1之间的和 = 1（递归的出口）

        //核心：
        //1.找出口
        //2.找规律

        System.out.println(getSum(100));//5050

    }


    public static int getSum(int number){//99
        if(number == 1){
            return 1;
        }

        //如果numbert不是1呢？
        return number + getSum(number -1);

    }
}

（运行结果截图）

练习：递归求阶乘

（源代码）

package com.itheima.mysort;

public class A04_RecursionDemo3 {
    public static void main(String[] args) {
        //需求：利用递归求5的阶乘
        //5！ = 5 * 4 * 3 * 2 * 1;

        //核心：
        //1.找出口
        //2.找规律
        //心得：
        //方法内部再次调用方法的时候，参数必须要更加的靠近出口
        //第一次调用：5
        //第二次调用：4


        //5！ = 5 * 4!;
        //4！ = 4 * 3!;
        //3！ = 3 * 2!;
        //2！ = 2 * 1!;
        //1！ = 1;

        System.out.println(getFactorialRecursion(5));//120


    }

    public static int getFactorialRecursion(int number){//5 !
        if(number == 1){
            return 1;
        }

        return number * getFactorialRecursion(number - 1);
    }


}

（运行结果截图）

内存图

快速排序

（源代码）

package com.itheima.mysort;

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

      /*
        快速排序：
            第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。
            比基准数小的全部在左边，比基准数大的全部在右边。
            后面以此类推。
      */

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

        quickSort(arr, 0, arr.length - 1);

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


            //利用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);

    }


}

（运行结果截图）

总结

Arrays

什么是Arrays？

        操作数组的工具类

例如：

（源代码）

package com.itheima.arraysdemo;

import java.util.Arrays;

public class MyArraysDemo1 {
    public static void main(String[] args) {
        //toString:将数组变成字符串
        System.out.println("-----------toString-----------");
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

        //binarySearch:二分查找法查找元素
        //细节1：二分查找的前提：数组中的元素必须是有序，数组中的元素必须是升序的
        //细节2：如果要查找的元素是存在的，那么返回的是真实的索引
        //但是，如果要查找的元素是不存在的，返回的是 -返回值 - 1
        System.out.println("-----------binarySearch-----------");
        System.out.println(Arrays.binarySearch(arr, 10));//9
        System.out.println(Arrays.binarySearch(arr, 2));//1
        System.out.println(Arrays.binarySearch(arr, 20));//-11

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

        //copyOfRange:拷贝数组（指定范围）
        System.out.println("-----------copyOfRange-----------");
        int[] newArr2 = Arrays.copyOfRange(arr, 0,9);
        System.out.println(Arrays.toString(newArr2));//[1, 2, 3, 4, 5, 6, 7, 8, 9]

        //fill:填充数组
        System.out.println("-----------fill-----------");
        Arrays.fill(arr,100);
        System.out.println(Arrays.toString(arr));//[100, 100, 100, 100, 100, 100, 100, 100, 100, 100]

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

    }
}

（运行结果截图）

sort的重载

例如：

（源代码）

package com.itheima.arraysdemo;

import java.util.Arrays;
import java.util.Comparator;

public class MyArraysDemo2 {
    public static void main(String[] args) {
        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：表示当前要插入的元素跟现在的元素相比是一样的，也会放在后面
        Arrays.sort(arr,new Comparator<Integer>(){

            //Integer[] arr = {2,3,1,5,6,7,8,4,9};
            @Override
            public int compare(Integer o1, Integer o2) {
                System.out.println("--------------------");
                System.out.println("o1 : " + o1);
                System.out.println("o2 : " + o2);
                return o1 - o2;
            }
        });

        System.out.println(Arrays.toString(arr));
    }
}

（运行结果截图）

lambda表达式

初试lambda表达式

例如：

（源代码）

package com.itheima.lambdademo;

import java.util.Arrays;
import java.util.Comparator;

public class LambdaDemo1 {
    public static void main(String[] args) {
        Integer[] arr = {2,3,1,5,6,7,8,4,9};

        /*Arrays.sort(arr,new Comparator<Integer>(){

            public int compare(Integer o1, Integer o2) {
                System.out.println("--------------------");
                System.out.println("o1 : " + o1);
                System.out.println("o2 : " + o2);
                return o1 - o2;
            }
        });*/

        Arrays.sort(arr,(Integer o1, Integer o2)-> {
            return o1 - o2;
        }
        );
            System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
        
    }
}

（运行结果截图）

函数式编程

lambda表达式的标准格式

例如：

例如：

（源代码）

package com.itheima.lambdademo;

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

        //1.利用匿名内部类的形式去调用下面的方法
        /*method(new Swim(){
            @Override
            public void swimming(){
                System.out.println("正在游泳");
            }

        });
    }*/

    //2.利用lambda表达式进行改写
    method(
            () -> {
            System.out.println("正在游泳");
        }

    );
}


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



interface Swim{
    public abstract void swimming();
}

（运行结果截图）

总结

lambda表达式的省略写法

省略核心：可推导，可省略

lambda表达式的省略规则：

        1.参数类型可以省略不写

        2.如果只有一个参数，参数类型可以省略，同时()也可以省略

        3.如果lambda表达式的方法体只有一行，大括号，分号，return可以省略不写，需要同时省略。

例如：

（源代码）

package com.itheima.lambdademo;

import java.util.Arrays;

public class LambdaDemo3 {
    public static void main(String[] args) {
        /*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

        );



        System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

（运行结果截图）

练习：Lambda表达式简化Comparator接口的匿名形式

（源代码）

package com.itheima.lambdademo;

import java.util.Arrays;
import java.util.Comparator;

public class LambdaDemo4 {
    public static void main(String[] args) {
        String[] arr = {"a", "aaaa", "aaa","aa"};

        /*
        //匿名内部类
        Arrays.sort(arr,new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
            return o1.length() - o2.length();
        }
        });

        //lambda表达式
        Arrays.sort(arr,(String o1, String o2) -> {
            return o1.length() - o2.length();
            }
        );

         */

        //lambda表达式省略
        Arrays.sort(arr,( o1,  o2) -> o1.length() - o2.length()

        );

        //打印数组
        System.out.println(Arrays.toString(arr));
    }
}

（运行结果截图）