算法

查找

基本查找

数据没有顺序，直接遍历全部

二分查找binarySearch

前提：数组中的数据必须有序

核心逻辑：每一次排除一半的查找范围，提高查找效率

如果数据是乱的，先排序再用二分查找得到的索引没有实际意义，只能确定当前数字再数组中是否存在，因为排序之后数字的位置可能就发生变化了

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8,55,66,77,88,555,6666,77777};
    System.out.println(binarySearch(arr,55));
}
public static int binarySearch(int[] arr,int number){
    // 要查找的范围
    int min = 0;
    int max = arr.length-1;
    // 循环查找
    while(true){
        if(min > max){return -1;}

        int mid = (min + max) /2;
        
        if(arr[mid] > number){
            max = mid -1;
        }else if(arr[mid] < number){
            min = mid +1;
        }else{
            return mid;
        }
    }
}

差值查找

数组中的数据分步比较均匀

mid = min + (key-arr[min])/(arr[max]-arr[min]) *(max-min)

斐波那契查找

mid = min + 黄金分隔点左半边长度-1

分块查找

分块原则：前一块中的最大数据小于后一块中的所有数据（块内无序，块间有序）；块数数量一般为数字个数开根号

核心思路：先确定元素在哪一块，然后块内挨个查找

有序，但不多：

7,10,|13,19,16,20,|27,22,30,40,36,|43,50,48
分成四个块对象：块对象1|块对象2|块对象3|块对象4（索引表）
块对象1：max：10，index：0-1
块对象2：max：20，index：2-5
块对象3：max：40，index：6-10
块对象4：max：50，index：11-13

class block{
	int max;   //最大值
	int startIndex;   //开始索引
	int endIndex;   //结束索引
	....
}

public class demo1 {
    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};
        //System.out.println(arr.length);

        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 = 73;
        // 调用方法，传递索引表，数组和要查找的元素
        int index = getIndex(blockArr,arr,number);
        System.out.println(index);
    }

    //利用分块查找的原理，查询number的索引
    public static int getIndex(block[] blockArr,int[] arr,int number){
        int blockIndex = findBlockIndex(blockArr,number);
        if(blockIndex == -1){
            return -1;
        }

        // 获取起始索引
        int startIndex = blockArr[blockIndex].getStartIndex();
        int endIndex = blockArr[blockIndex].getEndIndex();

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

    }

    //先确定number在哪个索引表
    public static int findBlockIndex(block[] blockArr,int number){
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}

如果最小的在中间，要保证分块后的索引表不能有交集

27,22,30,40,36,|13,19,16,20|,7,10,|43,50,48

数表查找

哈希查找

扩展的分块查找（查找的过程中需要添加数据）

在0-1000中获取100个随机数，要求数据不重复，可以做一个间隔100，从0到1000的索引表，要存20就放入第一个索引表（max：100，startIndex：0，endIndex：100），后面再存20的时候先看在0-100中，再看里面有没有，没有的话挂在后面，有的话就不存入

排序

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

冒泡排序

相邻的元素两两比较，大的放右边，小的放左边

第一轮循环结束，最大值已经找到，在数组的最右边

第二轮循环只要在剩余元素找最大值即可

第二轮循环结束；次大值已经确定，第三轮循环继续在剩余数据中循环

public static void main(String[] args) {
    int[] arr = {2,4,6,3,7,1};
    for (int i = 0; i < 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;
            }
        }
        printArr(arr);
    }
}
/*
2 4 3 6 1 7 
2 3 4 1 6 7 
2 3 1 4 6 7 
2 1 3 4 6 7 
1 2 3 4 6 7 
*/

选择排序

从0索引开始，拿每一个索引上的元素跟后面的元素依次比较，小的放前面大的放后面

第一次循环完最小的在第一个，第二次循环完次小的在第二个...

public static void main(String[] args) {
    int[] arr = {2,4,6,3,7,1};    // length = 6,要5轮:01234
    for (int j = 0; j < arr.length-1; j++) {
        for (int i = j; i < arr.length-1; i++) {    //i+1 最大6，i5,
            if(arr[j]>arr[i+1]){
                int temp = arr[j];
                arr[j] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        printArr(arr);
    }
}
/*
1 4 6 3 7 2 
1 2 6 4 7 3 
1 2 3 6 7 4 
1 2 3 4 7 6 
1 2 3 4 6 7 
*/

插入排序demo2

将0索引的元素到N索引的元素看做有序的，把N+1索引的元素到最后一个当成无序的；遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，遇到相同数据插在后面（N：0-最大索引）

先把牌分为两组，左边有序，右边无序

public static void main(String[] args) {
    int[] arr = {2,9,4,6,3,7,1};    // length = 7
    // 找到无序的数组的开始索引   //2
    int startIndex = -1;
    for (int i = 0; i < arr.length; i++) {  //最多7次，0123456；
        if(arr[i]>arr[i+1]){
            startIndex = i+1;
            break;
        }
    }
    // System.out.println(startIndex);

    // 遍历后一组
    for (int i = startIndex; i < arr.length;i++) {    // length = 7,0123456;,i:23456
        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);
    }
}
/*
2 4 9 6 3 7 1 
2 4 6 9 3 7 1 
2 3 4 6 9 7 1 
2 3 4 6 7 9 1 
1 2 3 4 6 7 9 
*/

快速排序

递归算法

方法中调用方法本身

把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需要少量的程序就可以描述出解题过程中所需要的多次重复运算

递归一定要有出口，否则就会出现内存溢出

public static void main(String[] args) {
    System.out.println(getSum(100));    // 5050
    System.out.println(jiecheng(3));    // 6
}
public static int getSum(int number){
    if(number == 1){
        return 1;
    }
    return number+getSum(number-1);
}
public static int jiecheng(int number){
	if(number == 1){
	return 1;
	}
	return number * jiecheng(number -1);
}

快速排序

把0索引的数字作为基准数，确定基准数在数组中的正确位置，比基准数小的全部在左边，比基准数大的全部在右边

第一轮：左边的start从1索引往中间走start++，右边的end从最后一个往中间走end--，遍历判断，比基准数小的全部在左边，比基准数大的全部在右边，然后基准数放在最中间那个数的位置，基准数归位

此时，前面所有的数据都比基准数小，后面所有的数据都比基准数大

第一轮：

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]+" ");
    }

}
public static void quickSort(int[] arr,int i,int j){
    int start = i;
    int end = j;
    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++;
        }

        // 交换左边比baseNumber大的和右边比基准数小的
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;


    }
    // start和end指向同一个元素时，循环结束，表示已经找到基准数的位置，基准数归位
    int temp = arr[i];
    arr[i] = arr[start];
    arr[start] = temp;
}
// 3 1 2 5 4 6 9 7 10 8 

此时以3为基准数找3在左半边的位置，以9为基准数找9在右半边的位置

全部：

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]+" ");
    }

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

        // 交换左边比baseNumber大的和右边比基准数小的
        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);
    quickSort(arr,start+1,j);
}

先移动end，保证最后start和end指向的比基准数小

测试：

public static void main(String[] args) {
    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);          // 116（ms）
}

182,183,184----------------！！！！

希尔排序

归并排序

堆排序

计数排序

桶排序

基数排序

字符串匹配算法

基本查找

KMP算法

arrays

操作数组的工具类

int[] arr1 = Array.copyOfRange(arr,1,4)

lambda表达式

本栏目推荐文章
• 2024/1/13 算法笔记
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• 基于融合语义信息改进的内容推荐算法。Improved content recommendation algorithm integrating semantic information.
• 秦九韶算法学习笔记
• [RFC6238] TOTP: 基于时间的一次性密码生成算法