感谢黑马程序员的免费课程！大爱！

查找算法

基本查找

从 0 索引开始遍历查找。

public class test {
    public static void main(String[] args) {
        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){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number){
                return true;
            }
        }
        return false;
    }

二分/折半查找

只能查找有序元素。

每次都将元素分成两半，如果大了，就往小的范围移动 1，如果小了则反之。所以需要有序元素。

public class test {
    public static void main(String[] args) {
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(binarySearch(arr, 150));
    }
    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;
            }
        }
    }
}

计算公式如下：

pos=low+(key−arrlow)(arrhigh−arrlow)×(high−low)pos = low + \frac{(key - arr_{\text{low}})}{(arr_{\text{high}} - arr_{\text{low}})} \times (high - low)
  • low：当前查找区间的下界
  • high：当前查找区间的上界
  • key：要查找的值
  • arr[low] 和 arr[high] 分别是区间的最小值和最大值

这个公式会在一段线性分布的数据内给出越来越精确的估算位置，直到 pos 位置的数据等于 key。

分块查找

<!--复制自黑马程序员的资料-->

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

汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找，分块查找适用于数据较多，但是数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找

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

分块的原则1：前一块中的最大数据，小于后一块中所有的数据(块内无序，块间有序)
分块的原则2：块数数量一般等于数字的个数开根号。比如:16个数字一般分为4块左右。
核心思路:先确定要查找的元素在哪一块，然后在块内挨个查找。

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;//结束索引
    //构造方法，set/get方法
    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

哈希查找

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

排序算法

冒泡排序

将相邻数据两两比较，小的放前面，大的放后面。（举例，也可按需更改）

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环：需要 n-1 轮
        for (int i = 0; i < n - 1; i++) {
            // 内层循环：相邻比较，每轮比较次数减少
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5};
        bubbleSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

选择排序

每次从待排序的序列中选出最小（或最大）的元素，放到已排序序列的末尾。

数组：[5, 2, 9, 1, 5]

第一轮（找最小，放到索引0）

  • 扫描整个数组 [5, 2, 9, 1, 5]，最小值为 1（索引3）
  • 交换索引0和索引3 → [1, 2, 9, 5, 5]
    （此时 1 已在正确位置）

第二轮（找第二小，放到索引1）

  • 扫描剩余部分 [2, 9, 5, 5]，最小值 2（索引1本身）
  • 不用交换 → [1, 2, 9, 5, 5]

第三轮（找第三小，放到索引2）

  • 扫描 [9, 5, 5]，最小值 5（索引3）
  • 交换索引2和索引3 → [1, 2, 5, 9, 5]

第四轮（找第四小，放到索引3）

  • 扫描 [9, 5]，最小值 5（索引4）
  • 交换索引3和索引4 → [1, 2, 5, 5, 9]

排序完成。

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外层循环：每轮确定一个位置（0 到 n-2）
        for (int i = 0; i < n - 1; i++) {
            // 假设当前位置 i 的元素是最小值
            int minIndex = i;
            // 内层循环：在 i+1 到末尾找真正的最小值索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 如果最小值不在 i 位置，交换
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5};
        selectionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

插入排序

将 0 索引到 N 索引的数据认为是有序的，其余数据认为是无序的。

随后，遍历无序部分的数据，将其插入到有序部分中适当的位置。遇到相同的数据则放在后面。

public class InsertSort {
    public static void main(String[] args) {
        int[] array = new int[]{15,63,97,12,235,66};
        //控制拿去每一个元素
        for(int i=1;i<array.length;i++){
            //比较次数
            for (int j=i;j>=1;j--){
                //是否小于前面的元素
                if (array[j]<array[j-1]){
                    int temp = 0;
                    temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }else {
                    //continue 与 break
                    break;
                }
            }
        }
        System.out.println("排序后的结果："+ Arrays.toString(array));
    }
}

递归算法

方法中调用方法本身的现象。

如果我们直接在方法中调用方法本身，例如：

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

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

会发生栈内存溢出错误。

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

例如，我们利用递归求 1-100 之间的和。

public class test {
    public static void main(String[] args) {
        System.out.println(getSum(100));
    }

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

这就实现了把一个大问题拆解成多个小问题来解决。同时，程序会在 number == 1 时找到出口，所以不发生内存溢出错误。

快速排序

快速排序（Quick Sort）是从冒泡排序算法演变而来的，实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

先以 0 索引的数据作为基准数，随后设置两个指针，这里将起始位置叫作 start，终止位置叫作 end。我们将 end 同基准数比较，若大于基准数，不操作，随后 end 索引 -- 至上一个数。如果大于基准数，重复操作；如果小于基准数，则开始将 start 指针向右移动。重复。当 start 索引对应数据大于基准数时，将 start 与 end 索引对应数据交换。

重复以上操作。

多次交换，直到 start 与 end 指向同一个索引时，这个索引便是基准数在数组应当存入的位置。也就是基准数归位。将基准数与这个索引对应的数据交换。

现在，这个基准数将数组分为了两个部分。我们继续在左、右两边重复上述操作。

然后我们就可以应用递归的思想，不断将左右两部分再分别分为左右两部分。

代码示例：

public class quicksort {
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 12, 4, 5, 10 ,8 ,11};
        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;

        // 递归需要一个出口
        // 如果 start 大于 end，就说明这一部分是空区间，我们直接 return
        if (start > end) {
            return;
        }

        // 记录基准数
        int baseNumber = arr[i];
        
        while (start != end) {
            while (true) {
                if (end <= start || end < baseNumber) {
                    break;
                }
                end --;
            }
            
            while (true) {
                if (end <= start || end > baseNumber) {
                    break;
                }
                start ++;          
            }

            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        // 基准数归位
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        // 确定左右两部分的范围并重复操作，也就是递归的思想
        QuickSort(arr, i, start - 1);
        QuickSort(arr, start +1, j);
    }
}

快速排序排序一百万个数据，也只需要几百毫秒的时间。效率极高。

  • reward_image1
此作者没有提供个人介绍。
最后更新于 2026-04-11