常见算法的学习笔记

常见算法（用Java语言描述）的学习笔记

一、查找算法

01 线性查找

1、介绍

核心思想是按照顺序依次对数据结构里的每个元素进行检查，直至找到目标元素。数据不需要有任何顺序。

2、代码表示

public static boolean BasicSearch(int[] arr, int number) {
        //利用基本查找来在数组中进行查找
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == number) {
                return true;
            }
        }
        return false;
    }

3、适用场景

顺序查找简单易懂，适用于数据量较小或者数据无序的情况。

不过，当数据量很大时，由于其时间复杂度较高，查找效率会比较低。

4、时间复杂度

顺序查找需要遍历整个数组，因此在最坏的情况下，时间复杂度是$O(n)$,n 是数组的长度。

02 二分查找/折半查找

1、二分查找优势

相比基本查找效率高，每次可以去掉一半的查找范围。

2、前提条件

查找的数据必须是有序的排列。

3、查找过程

• min和max表示当前要查找的范围
• mid是在min和max中间的
• 如果要查找的元素在mid的左边，缩小范围时，min不变，max=mid-1
• 如果要查找的元素在mid的右边，缩小范围时，max不变，mix=mid+1

[!IMPORTANT]

要查找的数据是用索引来和min、mid、max比较的。

4、代码表示

	//定义静态方法binarySearch，接收两个参数：
    //int[] arr：表示一个有序的整数数组。
    //int number：代表要查找的目标元素。
    //此方法的返回值类型为int，如果找到元素，返回其在数组中的索引，否则返回-1
    public static int binarySearch(int[] arr, int number) {

        //1、定义两个变量记录要查找的范围
        //min表示数组的起始索引；max代表数组的最后一个元素的索引
        int min = 0;
        int max = arr.length - 1;
        
        //2、利用无限循环while（true）持续的查找目标元素
        //在每次循环开始时，检查min是否大于max，若满足此条件，
        //意味着查找范围为空，目标元素不在数组中，此时返回 -1。
        while(true){
            if (min > max) {
                return -1;
            }

       //3、计算当前查找范围的中间位置mid，通过(min + max) / 2得到。
       int mid = (min + max) / 2;

            //4、拿mid指向的元素和要查找的元素进行比较
            //4.1 number在mid的左边
            //4.2 number在mid的右边
            //4.3 number和mid指向的元素一样
            if (arr[mid] > number) {

                //number在mid的左边,min不变，max = mid - 1
                max = mid -1;
            }else if (arr[mid] < number) {

                //number在mid的右边,min不变，max = mid + 1
                min = mid + 1;
            }else {

                //找到啦！
                return mid;
            }
        }
    }

5、时间复杂度

• 二分查找算法的时间复杂度为${\log }_{2}n$，这里的n是数组的长度。
• 示例说明：假设数组长度 n=16，每次迭代后搜索范围的变化为：

可以看到，经过$lo{g}_{2}16=4$次迭代后，搜索范围缩小到了 1。

综上，二分查找算法的时间复杂度为$O(\log n)$。随着数组长度的增加，算法的执行时间增长速度相对较慢，具有较高的效率。

03 插值查找

1、基本思想

假设查找表中的数据是按升序排列的，对于给定的关键字mid，插值查找通过公式

$$mid=min+\frac{key-arr[min]}{arr[max]-arr[min]}\ast (max-min)$$

来计算中间位置mid，其中arr[min]和arr[max]分别是查找区间的最小值和最大值。该公式是基于数据在查找区间内均匀分布的假设，通过估算mid在区间*[min,max]中的相对位置来确定mid*，而不是像二分查找那样简单地取中间位置。

后面的max和min是对应的索引。

2、代码表示

public static int interpolationSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && key >= arr[low] && key <= arr[high]) {
            if (low == high) {
                if (arr[low] == key) {
                    return low;
                }
                return -1;
            }

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

            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

[!CAUTION]

插值查找需要数据 分布均匀。

3、时间复杂度

在数据均匀分布的情况下，插值查找的时间复杂度为 $O(loglogn)$，优于二分查找的 $O(\log n)$。但如果数据分布不均匀，其性能可能会退化为 $O(n)$。

04 分块查找

1、分块原则

• 前一块中的最大数据，小于后一块中的所有数据（块内无序，块间有序）。
• 块数数量一般等于数字的个数开根号。例：16个数字一般分为4块左右。

2、核心思路

先确定要查找的元素在哪一块，然后在块内挨个查找。

3、代码表示

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

        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //1、分块

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

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

        //4、定义变量用来记录要查找的元素
        int number = 5;

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

        //6、打印输出
        System.out.println(index);
    }

    //定义方法。
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1、确定number在哪个块
        int indenBlock = findIndexBlock(blockArr,number);

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

        //获取这一块的起始索引和结束索引
        int startIndex = blockArr[indenBlock].getStartIndex();
        int endIndex = blockArr[indenBlock].getEndIndex();


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

    //定义方法确定number在哪个块中
    private static int findIndexBlock(Block[] blockArr, int number) { //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号块

        //从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 + "}";
    }
}

4、时间复杂度

分块查找的时间复杂度与块数、每块中的元素个数以及查找方式有关。假设将长度为 n 的数组分为 m 块，每块有 s 个元素（n=m×s）。

在索引表中查找块的时间复杂度：如果索引表是有序的，使用二分查找等高效算法，时间复杂度为$O(\log m)$；如果索引表是无序的，采用顺序查找，时间复杂度为$O(m)$。

在块内查找元素的时间复杂度：通常采用顺序查找，时间复杂度为$O(s)$。

因此，分块查找的平均时间复杂度为**索引表查找时间复杂度与块内查找时间复杂度之和。**当索引表采用顺序查找时，分块查找的平均时间复杂度为$O(m+s)$；当索引表采用二分查找时，平均时间复杂度约为$O(\log m+s)$。

理想情况：由于m=n/s，当s取n时，m也为n，此时分块查找的平均时间复杂度为O(n)。

5、适用场景

分块查找适用于数据量较大且需要快速查找的场景，尤其是当数据无法一次性全部加载到内存中时，可以将数据分块存储在磁盘上，通过索引表快速定位到目标元素所在的块，然后再在块中进行查找。

二、排序算法

01 冒泡排序！！！

1、核心思想

• 相邻的数据两两比较，大的放右边，小的放左边。（从小到大）
• 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推。
• 如果数组中有n个数据，总共执行n-1次代码。

2、代码表示

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

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

        //2、利用冒泡

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

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

02 选择排序！！！

1、核心思想

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

2、代码展示

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

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

        //2、利用选择排序进行
        //外循环,i表示拿着哪个索引上的数据跟后面的数据进行比较并交换
        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 = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

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

}

03 插入排序

1、核心思想

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

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

N的范围：0-最大索引。

2、代码展示

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++) {
            //3、记录当前要插入数据的索引
            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) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

04 递归算法

1、核心思想

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

2、代码展示

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

    public static void method() {
        method();	//方法中自己调用自己
    }
}

[!CAUTION]

递归一点要有出口，否则就会出现内存溢出的现象。

3、书写递归的核心

• 找出口：什么时候不再调用方法。
• 找规则：如何把大问题变为规模较小的问题。
• 心得：方法内部再次调用方法的时候，参数必须要更加的靠近出口。

4、练习

1、需求：利用递归求1-100之间的和。

代码展示：

public class A04_RecursionDemo2 {
    public static void main(String[] args) {
        /*
         * 需求：利用递归求1-100之间的和。
         * 100 + 99 + 98 + 97 + ... + 3 + 2 + 1
         *
         * 1-100之间的和 = 100 +（1-99之间的和）
         * 1-99之间的和 = 99 + （1-98之间的和）
         * ...
         * 1-2之间的和 = 2 + （1-1之间的和）
         * 1-1之间的和 = 1 （递归的出口)*/

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

    }

    public static int getSum(int number) {
        if (number == 1) {    //number为1
            return 1;
        }
        return number + getSum(number - 1); //number不为1
   }
}

2、需求：利用递归求5的阶乘，并把结果在控制台输出。

代码展示：

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

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

    }

    public static int getFactorialRecursion(int number) {
        if (number == 1) {
            return 1;
        }
        return number * getFactorialRecursion(number - 1);
    }

}

05 快速排序

1、核心思想

第一轮：以0索引的数字为基准数，确定基准数在数组中的正确位置。

​ 比基准数小的全部在左边，比基准数大的全部在右边。

​ 后面的以此类推。

2、代码展示

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

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

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

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

    }

    /*
     *   参数1：我们要排序的数组
     *   参数2：要排序的数组的起始索引
     *   参数3：要排序的数组的结束索引 */

    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，从后往前开始找，找比基准数小的数字
            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指向了同一个元素的时候，那么循环结束
        //表示已经找到了基准数在数组中应存入的位置
        //基准数归位
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

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

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

}

三、综合练习

1、按照要求进行排序

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

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

要求2：按照年龄的大小进行排序，年龄一样，按照身高排序，身高一样按照姓名的字母进行排序。（姓名中不要有中文或特殊字符）

代码展示：

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

public class Test1 {
    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、利用Array中的sort方法进行排序
        //匿名内部类
        /*Arrays.sort(arr, new Comparator<GirlFriend>() {
            @Override
            public int compare(GirlFriend o1, GirlFriend o2) {
                //比较规则
                double temp = o1.getAge() - o2.getAge();
                temp = temp == 0 ? o1.getHeight() - o2.getHeight() : temp;
                temp = temp == 0 ? o1.getName().compareTo(o2.getName()) : temp;

                if (temp > 0) {
                    return 1;
                } else if (temp < 0) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });*/

        //lanbda表达式
        //() -> {}
        //():对应着抽象方法的形参
        //{}：方法体
        Arrays.sort(arr, (o1, o2) -> {
            //比较规则
            double temp = o1.getAge() - o2.getAge();
            temp = temp == 0 ? o1.getHeight() - o2.getHeight() : temp;
            temp = temp == 0 ? o1.getName().compareTo(o2.getName()) : temp;

            if (temp > 0) {
                return 1;
            } else if (temp < 0) {
                return -1;
            } else {
                return 0;
            }
        });


        //4、展示数组中的内容
        System.out.println(Arrays.toString(arr));
    }

}