[数据结构与算法]常用排序、搜索算法总结 3 + 3 Java

先说一下，这篇文章主要是我自己的总结和回顾，主要是为了更深刻的理解，更熟练的运用这些基本算法。在相应的类中，这些算法在util中都有相关的现成的方法，可以直接使用（比如Arrays.binarySerch()）。

我会将总体代码放至最后。

如有错误，希望能帮忙指正（跪

由于我所有的代码都是有相应测试代码的，我先把测试代码放上，下面看的不会那么糊涂：

测试代码：

package test;
import java.util.*;
/**
 * @author WitMoy
 * @version V1.8
 * @date : 2022-07-15 16:43
 */
public class Main {
    private static final Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        quickSortTest();
        roundK();
        dichotomyTest();
        heapSortTest();
        topKTest();
        mergeSortTest();
        bfsSearchTest();
        dfsSearchTest();
        sc.close();
    }
    private static void timeCost(long begin, long end){
        System.out.println("\n用时： " + (end - begin) + "ms\n");
    }
    private static int[] getArray(){
        System.out.print("请输入数组长度： ");
        int length = sc.nextInt();
        int[] arr = new int[length];
        System.out.println("请输入数组内数据，数据之间用空格隔开： ");
        for(int i = 0; i < length; i++){
            arr[i] = sc.nextInt();
        }
        return arr;
    }
    private static void quickSortTest(){
        System.out.println("快排测试\n");
        int[] arr = getArray();
        System.out.print("请输入排序方式，升序输入true，降序输入false： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        Sort.QuickSort.sortAll(arr, 0, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("排好序的数组： " + Arrays.toString(arr));
        timeCost(begin, end);
    }
    private static void roundK(){
        System.out.println("roundK测试\n");
        int[] arr = getArray();
        System.out.print("请输入目标位置： ");
        int rank = sc.nextInt();
        System.out.print("升序第" + rank + "请输入true，否则请输入false： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        int t = Sort.QuickSort.largestK(arr, 0, arr.length, rank, style);
        long end = System.currentTimeMillis();
        System.out.println("该目标值为： " + t);
        timeCost(begin, end);
    }
    private static void dichotomyTest(){
        System.out.println("二分测试\n");
        int[] arr = getArray();
        System.out.print("请输入在该数组中要搜索的目标值： ");
        int round = sc.nextInt();
        System.out.print("请输入您需要的数组排序规律（升序true，降序false）： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        int ans = Search.binarySearch(arr, arr.length, round, style);
        long end = System.currentTimeMillis();
        if(ans < 0) System.out.println("无法找到目标值");
        else System.out.println("该目标脚标为： " + ans);
        timeCost(begin, end);
    }
    private static void heapSortTest(){
        System.out.println("堆排测试\n");
        int[] arr = getArray();
        System.out.print("输入true为升序，false为降序。请输入排序方式：");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        Sort.HeapSort.sortAll(arr, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("排好序的数组： " + Arrays.toString(arr));
        timeCost(begin, end);
    }
    private static void topKTest(){
        System.out.println("topK测试\n");
        int[] arr = getArray();
        System.out.print("寻找该数组前K小的数输入true，前K大输入false： ");
        boolean style = sc.nextBoolean();
        String tell;
        if(style) tell = "小";
        else tell = "大";
        System.out.print("您要找前几" + tell + "的数？请输入： ");
        int target = sc.nextInt();
        long begin = System.currentTimeMillis();
        int[] topK = Sort.HeapSort.topK(arr, target, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("前" + target + tell + "的数组： " + Arrays.toString(topK));
        timeCost(begin, end);
    }
    private static void mergeSortTest(){
        System.out.println("归并排序测试\n");
        int[] arr = getArray();
        System.out.print("请选择排序方式，升序输入true， 降序输入false： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        Sort.MergeSort.sort(arr, 0, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("排好序的数组： " + Arrays.toString(arr) + "\n");
        timeCost(begin, end);
    }
    private static void bfsSearchTest(){
        System.out.println("bfs测试\n");
        System.out.print("请输入节点数量： ");
        int nodeNum = sc.nextInt();
        boolean[][] maps = new boolean[nodeNum][nodeNum];
        System.out.print("请输入目标点。例：要求点 A 到点 B 的最短路，输入A B： ");
        int start = sc.nextInt();
        int tail = sc.nextInt();
        System.out.println("请输入点之间的关系，每行一对，节点最小从1开始，输入0 0 结束输入： " +
                "\n例： 点A可以到达点B， 输入A B");
        while(true){
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(a <= 0 || b <= 0) break;
            maps[a - 1][b - 1] = true;
        }
        long begin = System.currentTimeMillis();
        int ans = Search.BfsSearch.shortestPath(maps, start, tail);
        long end = System.currentTimeMillis();
        if(ans == -1){
            System.out.println(start + "无法到达" + tail);
        }else{
            System.out.println("节点 " + start + " 到达" +
                    "节点 " + tail + " 的最短路长度为： " + ans);
        }
        timeCost(begin, end);
    }
    private static void dfsSearchTest(){
        System.out.println("dfs测试\n");
        System.out.print("请输入节点数量： ");
        int nodeNum = sc.nextInt();
        System.out.print("请输入起始点和终点： ");
        int start = sc.nextInt();
        int tail = sc.nextInt();
        boolean[][] maps = new boolean[nodeNum][nodeNum];
        int[][] value = new int[nodeNum][nodeNum];
        System.out.println("请输入点之间的关系，每行三个数，节点最小从1开始，输入0 0 0结束输入： " +
                "\n例： 点A可以到达点B，权重为W， 输入A B W");
        while(sc.hasNext()){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if(a <= 0 || b <= 0 || c <= 0) break;
            maps[a - 1][b - 1] = true;
            value[a - 1][b - 1] = c;
        }
        long begin = System.currentTimeMillis();
        ArrayList<Integer> minimumValue = Search.dfsSearch(maps, value, start, tail);
        long end = System.currentTimeMillis();
        System.out.println("权重最小路径的权重为： " + minimumValue.get(minimumValue.size() - 1) +
                "\n走过的节点为： ");
        for(int i = 0; i < minimumValue.size() - 1; i++){
            System.out.print(minimumValue.get(i) + " ");
        }
        timeCost(begin, end);
    }
}

排序算法部分：

快速排序：

原理：通过寻找基准，不断分区，使每次区的两端的数值逐渐规律化，当区长度为1时，排序完成。具体请看：快速排序法

我用的是：单循环完成快速排序。这两种操作略差一些，思路完全一样

根据快速排序原理扩展的第K问题（roundK问题），基本原理是在分区过程中不断确定想要的基准值的位置，这种方法大多数情况下只用对数组排一部分序，甚至有时候几乎不用排序便能找到，整体来说是非常快的，在数据量较大的情况下非常吃香。

下面是快速排序和roundK问题的代码，其中sortElement是快排元（其实也就是我从两种需求中抠出来的相同代码部分）

    private static void swap(int[] arr, int placeA, int placeB) {
        int t = arr[placeA]; arr[placeA] = arr[placeB]; arr[placeB] = t;
    }
//快排
    public static class QuickSort{
        //快排元
        private static int sortElement(int[] arr, int left, int right, boolean way) {
            int p = left;
            int index = p + 1;//步子
            //寻找新基数位置
            for (int i = index; i < right; i++) {
                //控制升序降序
                boolean style = way ? arr[i] < arr[p]:arr[i] > arr[p];
                if (style) {
                    swap(arr, i, index);
                    index++;
                }
            }
            //刷新基数及其位置
            swap(arr, p, (index - 1));
            p = index - 1;
            return p;
        }
        //快排
        public static void sortAll(int[] arr, int left, int right, boolean style) {
            if (left < right) {
                int p = sortElement(arr, left, right, style);
                sortAll(arr, left, p, style);
                sortAll(arr, (p + 1), right, style);
            }
        }
        //快速找排序第k的数（降序）
        public static int largestK(int[] arr, int left, int right, int k, boolean style) {
            if (left < right) {
                int p = sortElement(arr, left, right, style);
                if(p == k - 1) return arr[p];
                else if(p > k - 1) return largestK(arr, left, p, k, style);
                else return largestK(arr, p + 1, right, k, style);
            }
            return -1;
        }
    }

堆排序:

原理：利用堆的结构特性和相应的维护方法，不断调整维护大/小顶堆结构并不断锁定堆尾来逐渐有序固定数组，直到堆中所有元素均被锁定，排序完成。

具体见：堆排序和基于其思路的topK问题

再简单说一下topK问题的应用吧。其实在数据相对较少的情况下，对数组直接排序再提取topK比较方便，然而当数据非常庞大的时候，直接排序会占用极大的额外空间，十分浪费资源，而且对程序整体造成了很大压力。利用调整堆的思路，空间复杂度直接降到O(1)。下面是堆排序和topK问题的代码。

//堆排（大量数据）
    public static class HeapSort{
        //向下调整函数，style为true，大顶堆；false，小顶堆；
        private static void down(int[] arr, int parent, int size, boolean style){
            int child = parent * 2 + 1;//二叉树，孩子角标。
            while(child < size){
                //创建style
                boolean t = false;
                if(child + 1 < size) {
                    t = style ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1];
                }
                //确定极端节点（谁大谁小）
                if(child + 1 < size && t) {
                    child++;
                }
                t = style ? arr[child] > arr[parent] : arr[child] < arr[parent];
                if(t){
                    swap(arr, child, parent);
                    parent = child;
                    child = parent * 2 + 1;
                }else break;
            }
        }
        //全排
        public static void sortAll(int[] arr, int size, boolean style){
            for(int i = (size - 2) / 2; i >= 0; i--){
                down(arr, i, size, style);
            }
            int end = size - 1;
            while(end > 0){
                swap(arr, 0, end);
                down(arr, 0, end, style);
                end--;
            }
        }
        //前K大问题（大量数据），style为true，前K小；false，前K大；
        public static int[] topK(int[] arr, int targetNumbers, int allNumbers, boolean style){
            int[] kNum = new int[targetNumbers];
            System.arraycopy(arr, 0, kNum, 0, targetNumbers);
            for(int i = (targetNumbers - 2) / 2; i >= 0; i--){
                down(kNum, i, targetNumbers, style);
            }
            for(int i = targetNumbers; i < allNumbers; i++){
                boolean t = style ? arr[i] < kNum[0] : arr[i] > kNum[0];
                if(t){
                    kNum[0] = arr[i];
                    down(kNum, 0, targetNumbers, style);//调整根节点维护堆结构
                }
            }
            QuickSort.sortAll(kNum,0, targetNumbers, style);
            return kNum;
        }
    }

?

归并排序：

归并排序的思路类似于快排但又有所不同。它是将大数组先无限折半递归分割成长为1的小数组，再不断退出一层一层的递归并不断比较调整，然后合并，最后合成一个有序完整的数组。具体请看：归并排序法

下面是归并排序的代码：

//归并
    public static class MergeSort{
        private static void mergeElement(int[] arr, int left, int right, int middle, boolean style){
            int[] spareArr = new int[right - left + 1];
            if (right + 1 - left >= 0) {
                System.arraycopy(arr, left, spareArr, 0, right + 1 - left);
            }
            int pointerA = left, pointerB = middle + 1;
            for(int i = left; i <= right; i++){
                int relaPlaceA = pointerA - left, relaPlaceB = pointerB - left;
                if(pointerA > middle){//左半部分分配完
                    arr[i] = spareArr[relaPlaceB];
                    pointerB++;
                }else if(pointerB > right){//右半部分分配完
                    arr[i] = spareArr[relaPlaceA];
                    pointerA++;
                }else{//正常的比较选择
                    boolean way = style ? spareArr[relaPlaceA] > spareArr[relaPlaceB] : spareArr[relaPlaceA] < spareArr[relaPlaceB];
                    if(way){
                        arr[i] = spareArr[relaPlaceB];
                        pointerB++;
                    }
                    else{
                        arr[i] = spareArr[relaPlaceA];
                        pointerA++;
                    }
                }
            }
        }
        private static void sortElement(int[] arr, int left, int right, boolean style){
            if(left >= right) return;
            //折半递归
            int middle = (left + right) / 2;
            sortElement(arr, left, middle, style);
            sortElement(arr, (middle + 1), right, style);
            mergeElement(arr, left, right, middle, style);
        }
        public static void sort(int[] arr, int left ,int right, boolean style){
            sortElement(arr, left, (right - 1), style);
        }
    }

查找算法部分?

二分查找

这个，，大家应该都会，我不过多赘述了。仅对于java来说，有直接可以实现二分查找的方法，我在开头也提到了。具体代码如下：

//二分
    public static int binarySearch(int[] arr, int length, int target, boolean style){
        Sort.QuickSort.sortAll(arr, 0, arr.length, style);
        int left = 0, right = length - 1;
        while(left <= right){
            int middle = (left + right) / 2;//二分
            if(arr[middle] == target) return middle;
            boolean t = style ? arr[middle] < target:arr[middle] > target;
            if(t) left = middle + 1;
            else right = middle - 1;
        }
        return -1;//查询失败
    }

?在这里先普及一下，存图的方法叫邻接矩阵，知道的请跳过，不知道的点击这里：邻接矩阵

后面的数组maps都是邻接矩阵的方式存的

BFS（广度优先搜索）

从选定节点开始，向上或向下不断横向搜索邻接节点，直到搜索到目标节点。比较适合处理最短路相关问题。将其与贪心稍作结合便是A*算法的雏形，先不多说了。BFS具体可以看这篇：广度优先搜索

下面是具体代码：

//BFS
    public static class BfsSearch{
        public static int shortestPath(boolean[][] maps, int start, int end){
            if(end == start) return 0;
            int nodeNum = maps.length;
            LinkedList<Integer> queue = new LinkedList<>();
            queue.offer(start);//将起点压入队列
            int path = 0;
            //在队列中的节点数、即将进队的节点数、已经弹出的节点数
            int queueInternalNum = 1, queueExternalNum = 0, popNum = 0;
            boolean[] flag = new boolean[nodeNum];
            while(path < nodeNum){
                path++;
                while(queueInternalNum > popNum){
                    int tailEnd = queue.poll();//搜索后弹出节点
                    popNum++;
                    for(int i = 0; i < nodeNum; i++){
                        if(maps[tailEnd - 1][i] && !flag[i]){
                            if(i == end - 1) {//如果搜索到指定终点，停止并弹出路径长度
                                return path;
                            }
                            flag[i] = true;//将搜索过的节点标记为已搜索（广度优先）
                            queueExternalNum++;
                            queue.offer((i + 1));//当前节点入队
                        }
                    }
                }
                queueInternalNum = queueExternalNum;//更新当前队列节点数目
                //重置计数器
                queueExternalNum = 0;
                popNum = 0;
            }
            return -1;//搜索失败
        }
    }

DFS（深度优先搜索）

与BFS天生一对。DFS较为擅长找有各种奇怪要求的路径，位置，方法种类...等。DFS也如字面意思上，它利用栈（或递归），深度优先的遍历所有节点直到达到要求或遍历完毕。具体请看：深度优先搜索

下面是具体的代码：

//DFS
    public static ArrayList<Integer> dfsSearch(boolean[][] maps, int[][] valueMap, int start, int tail){
        LinkedList<Integer> stack = new LinkedList<>();
        int nodeNum = maps.length;
        boolean[] flag = new boolean[nodeNum];
        boolean backtrackingFlag = false;//标记是否出栈，为权重计算做准备
        int lastPoint = 0;//出栈前栈顶元素
        stack.push(start);//将起点压入栈顶
        int minimumValue = 0x3f3f3f3f;//最短路径。初始值我赋了int型的一半
        int nowPathValue = 0;//当前查找到的路径长度
        ArrayList<Integer> finalAns = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        while(!stack.isEmpty()){
            int topNode = stack.peek();
            if(backtrackingFlag){
                nowPathValue -= valueMap[topNode - 1][lastPoint - 1];
            }
            if(!ans.contains(topNode)){
                ans.add(topNode);
            }
            boolean ifSucceed = false;
            for(int i = 0; i < nodeNum; i++){
                if(!flag[i] && maps[topNode - 1][i]){
                    backtrackingFlag = false;
                    nowPathValue += valueMap[topNode - 1][i];
                    if(i == tail - 1){
                        if(minimumValue > nowPathValue){
                            minimumValue = nowPathValue;
                            ans.add(tail);
                            finalAns = new ArrayList<>(ans);
                        }else {
                            ans.clear();
                        }
                    }
                    flag[i] = true;
                    ifSucceed = true;
                    stack.push((i + 1));
                    break;
                }
            }
            if(!ifSucceed){
                backtrackingFlag = true;
                lastPoint = stack.pop();
                ans.remove((ans.size() - 1));
            }
        }
        finalAns.add(minimumValue);
        return finalAns;
    }

完整代码：

Main部分：?

package test;
import java.util.*;
/**
 * @author WitMoy
 * @version V1.8
 * @date : 2022-07-15 16:43
 */
public class Main {
    private static final Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        quickSortTest();
        roundK();
        dichotomyTest();
        heapSortTest();
        topKTest();
        mergeSortTest();
        bfsSearchTest();
        dfsSearchTest();
        sc.close();
    }
    private static void timeCost(long begin, long end){
        System.out.println("\n用时： " + (end - begin) + "ms\n");
    }
    private static int[] getArray(){
        System.out.print("请输入数组长度： ");
        int length = sc.nextInt();
        int[] arr = new int[length];
        System.out.println("请输入数组内数据，数据之间用空格隔开： ");
        for(int i = 0; i < length; i++){
            arr[i] = sc.nextInt();
        }
        return arr;
    }
    private static void quickSortTest(){
        System.out.println("快排测试\n");
        int[] arr = getArray();
        System.out.print("请输入排序方式，升序输入true，降序输入false： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        Sort.QuickSort.sortAll(arr, 0, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("排好序的数组： " + Arrays.toString(arr));
        timeCost(begin, end);
    }
    private static void roundK(){
        System.out.println("roundK测试\n");
        int[] arr = getArray();
        System.out.print("请输入目标位置： ");
        int rank = sc.nextInt();
        System.out.print("升序第" + rank + "请输入true，否则请输入false： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        int t = Sort.QuickSort.largestK(arr, 0, arr.length, rank, style);
        long end = System.currentTimeMillis();
        System.out.println("该目标值为： " + t);
        timeCost(begin, end);
    }
    private static void dichotomyTest(){
        System.out.println("二分测试\n");
        int[] arr = getArray();
        System.out.print("请输入在该数组中要搜索的目标值： ");
        int round = sc.nextInt();
        System.out.print("请输入您需要的数组排序规律（升序true，降序false）： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        int ans = Search.binarySearch(arr, arr.length, round, style);
        long end = System.currentTimeMillis();
        if(ans < 0) System.out.println("无法找到目标值");
        else System.out.println("该目标脚标为： " + ans);
        timeCost(begin, end);
    }
    private static void heapSortTest(){
        System.out.println("堆排测试\n");
        int[] arr = getArray();
        System.out.print("输入true为升序，false为降序。请输入排序方式：");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        Sort.HeapSort.sortAll(arr, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("排好序的数组： " + Arrays.toString(arr));
        timeCost(begin, end);
    }
    private static void topKTest(){
        System.out.println("topK测试\n");
        int[] arr = getArray();
        System.out.print("寻找该数组前K小的数输入true，前K大输入false： ");
        boolean style = sc.nextBoolean();
        String tell;
        if(style) tell = "小";
        else tell = "大";
        System.out.print("您要找前几" + tell + "的数？请输入： ");
        int target = sc.nextInt();
        long begin = System.currentTimeMillis();
        int[] topK = Sort.HeapSort.topK(arr, target, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("前" + target + tell + "的数组： " + Arrays.toString(topK));
        timeCost(begin, end);
    }
    private static void mergeSortTest(){
        System.out.println("归并排序测试\n");
        int[] arr = getArray();
        System.out.print("请选择排序方式，升序输入true， 降序输入false： ");
        boolean style = sc.nextBoolean();
        long begin = System.currentTimeMillis();
        Sort.MergeSort.sort(arr, 0, arr.length, style);
        long end = System.currentTimeMillis();
        System.out.println("排好序的数组： " + Arrays.toString(arr) + "\n");
        timeCost(begin, end);
    }
    private static void bfsSearchTest(){
        System.out.println("bfs测试\n");
        System.out.print("请输入节点数量： ");
        int nodeNum = sc.nextInt();
        boolean[][] maps = new boolean[nodeNum][nodeNum];
        System.out.print("请输入目标点。例：要求点 A 到点 B 的最短路，输入A B： ");
        int start = sc.nextInt();
        int tail = sc.nextInt();
        System.out.println("请输入点之间的关系，每行一对，节点最小从1开始，输入0 0 结束输入： " +
                "\n例： 点A可以到达点B， 输入A B");
        while(true){
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(a <= 0 || b <= 0) break;
            maps[a - 1][b - 1] = true;
        }
        long begin = System.currentTimeMillis();
        int ans = Search.BfsSearch.shortestPath(maps, start, tail);
        long end = System.currentTimeMillis();
        if(ans == -1){
            System.out.println(start + "无法到达" + tail);
        }else{
            System.out.println("节点 " + start + " 到达" +
                    "节点 " + tail + " 的最短路长度为： " + ans);
        }
        timeCost(begin, end);
    }
    private static void dfsSearchTest(){
        System.out.println("dfs测试\n");
        System.out.print("请输入节点数量： ");
        int nodeNum = sc.nextInt();
        System.out.print("请输入起始点和终点： ");
        int start = sc.nextInt();
        int tail = sc.nextInt();
        boolean[][] maps = new boolean[nodeNum][nodeNum];
        int[][] value = new int[nodeNum][nodeNum];
        System.out.println("请输入点之间的关系，每行三个数，节点最小从1开始，输入0 0 0结束输入： " +
                "\n例： 点A可以到达点B，权重为W， 输入A B W");
        while(sc.hasNext()){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if(a <= 0 || b <= 0 || c <= 0) break;
            maps[a - 1][b - 1] = true;
            value[a - 1][b - 1] = c;
        }
        long begin = System.currentTimeMillis();
        ArrayList<Integer> minimumValue = Search.dfsSearch(maps, value, start, tail);
        long end = System.currentTimeMillis();
        System.out.println("权重最小路径的权重为： " + minimumValue.get(minimumValue.size() - 1) +
                "\n走过的节点为： ");
        for(int i = 0; i < minimumValue.size() - 1; i++){
            System.out.print(minimumValue.get(i) + " ");
        }
        timeCost(begin, end);
    }
}

Sort部分

package test;

import java.util.Arrays;
import java.util.LinkedHashSet;

/**
 * @author WitMoy
 * @version V1.8
 * @date : 2022-07-09 10:07
 */
public class Sort {
    private static void swap(int[] arr, int placeA, int placeB) {
        int t = arr[placeA]; arr[placeA] = arr[placeB]; arr[placeB] = t;
    }
//快排
    public static class QuickSort{
        //快排元
        private static int sortElement(int[] arr, int left, int right, boolean way) {
            int p = left;
            int index = p + 1;//步子
            //寻找新基数位置
            for (int i = index; i < right; i++) {
                //控制升序降序
                boolean style = way ? arr[i] < arr[p]:arr[i] > arr[p];
                if (style) {
                    swap(arr, i, index);
                    index++;
                }
            }
            //刷新基数及其位置
            swap(arr, p, (index - 1));
            p = index - 1;
            return p;
        }
        //快排
        public static void sortAll(int[] arr, int left, int right, boolean style) {
            if (left < right) {
                int p = sortElement(arr, left, right, style);
                sortAll(arr, left, p, style);
                sortAll(arr, (p + 1), right, style);
            }
        }
        //快速找排序第k的数（降序）
        public static int largestK(int[] arr, int left, int right, int k, boolean style) {
            if (left < right) {
                int p = sortElement(arr, left, right, style);
                if(p == k - 1) return arr[p];
                else if(p > k - 1) return largestK(arr, left, p, k, style);
                else return largestK(arr, p + 1, right, k, style);
            }
            return -1;
        }
    }
//堆排（大量数据）
    public static class HeapSort{
        //向下调整函数，style为true，大顶堆；false，小顶堆；
        private static void down(int[] arr, int parent, int size, boolean style){
            int child = parent * 2 + 1;//二叉树，孩子角标。
            while(child < size){
                //创建style
                boolean t = false;
                if(child + 1 < size) {
                    t = style ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1];
                }
                //确定极端节点（谁大谁小）
                if(child + 1 < size && t) {
                    child++;
                }
                t = style ? arr[child] > arr[parent] : arr[child] < arr[parent];
                if(t){
                    swap(arr, child, parent);
                    parent = child;
                    child = parent * 2 + 1;
                }else break;
            }
        }
        //全排
        public static void sortAll(int[] arr, int size, boolean style){
            for(int i = (size - 2) / 2; i >= 0; i--){
                down(arr, i, size, style);
            }
            int end = size - 1;
            while(end > 0){
                swap(arr, 0, end);
                down(arr, 0, end, style);
                end--;
            }
        }
        //前K大问题（大量数据），style为true，前K小；false，前K大；
        public static int[] topK(int[] arr, int targetNumbers, int allNumbers, boolean style){
            int[] kNum = new int[targetNumbers];
            System.arraycopy(arr, 0, kNum, 0, targetNumbers);
            for(int i = (targetNumbers - 2) / 2; i >= 0; i--){
                down(kNum, i, targetNumbers, style);
            }
            for(int i = targetNumbers; i < allNumbers; i++){
                boolean t = style ? arr[i] < kNum[0] : arr[i] > kNum[0];
                if(t){
                    kNum[0] = arr[i];
                    down(kNum, 0, targetNumbers, style);//调整根节点维护堆结构
                }
            }
            QuickSort.sortAll(kNum,0, targetNumbers, style);
            return kNum;
        }
    }
//归并
    public static class MergeSort{
        private static void mergeElement(int[] arr, int left, int right, int middle, boolean style){
            int[] spareArr = new int[right - left + 1];
            if (right + 1 - left >= 0) {
                System.arraycopy(arr, left, spareArr, 0, right + 1 - left);
            }
            int pointerA = left, pointerB = middle + 1;
            for(int i = left; i <= right; i++){
                int relaPlaceA = pointerA - left, relaPlaceB = pointerB - left;
                if(pointerA > middle){//左半部分分配完
                    arr[i] = spareArr[relaPlaceB];
                    pointerB++;
                }else if(pointerB > right){//右半部分分配完
                    arr[i] = spareArr[relaPlaceA];
                    pointerA++;
                }else{//正常的比较选择
                    boolean way = style ? spareArr[relaPlaceA] > spareArr[relaPlaceB] : spareArr[relaPlaceA] < spareArr[relaPlaceB];
                    if(way){
                        arr[i] = spareArr[relaPlaceB];
                        pointerB++;
                    }
                    else{
                        arr[i] = spareArr[relaPlaceA];
                        pointerA++;
                    }
                }
            }
        }
        private static void sortElement(int[] arr, int left, int right, boolean style){
            if(left >= right) return;
            //折半递归
            int middle = (left + right) / 2;
            sortElement(arr, left, middle, style);
            sortElement(arr, (middle + 1), right, style);
            mergeElement(arr, left, right, middle, style);
        }
        public static void sort(int[] arr, int left ,int right, boolean style){
            sortElement(arr, left, (right - 1), style);
        }
    }
}

Search部分

package test;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @author WitMoy
 * @version V1.8
 * @date : 2022-07-09 11:12
 */
public class Search {
    //二分
    public static int binarySearch(int[] arr, int length, int target, boolean style){
        Sort.QuickSort.sortAll(arr, 0, arr.length, style);
        int left = 0, right = length - 1;
        while(left <= right){
            int middle = (left + right) / 2;//二分
            if(arr[middle] == target) return middle;
            boolean t = style ? arr[middle] < target:arr[middle] > target;
            if(t) left = middle + 1;
            else right = middle - 1;
        }
        return -1;//查询失败
    }
    //BFS
    public static class BfsSearch{
        public static int shortestPath(boolean[][] maps, int start, int end){
            if(end == start) return 0;
            int nodeNum = maps.length;
            LinkedList<Integer> queue = new LinkedList<>();
            queue.offer(start);//将起点压入队列
            int path = 0;
            //在队列中的节点数、即将进队的节点数、已经弹出的节点数
            int queueInternalNum = 1, queueExternalNum = 0, popNum = 0;
            boolean[] flag = new boolean[nodeNum];
            while(path < nodeNum){
                path++;
                while(queueInternalNum > popNum){
                    int tailEnd = queue.poll();//搜索后弹出节点
                    popNum++;
                    for(int i = 0; i < nodeNum; i++){
                        if(maps[tailEnd - 1][i] && !flag[i]){
                            if(i == end - 1) {//如果搜索到指定终点，停止并弹出路径长度
                                return path;
                            }
                            flag[i] = true;//将搜索过的节点标记为已搜索（广度优先）
                            queueExternalNum++;
                            queue.offer((i + 1));//当前节点入队
                        }
                    }
                }
                queueInternalNum = queueExternalNum;//更新当前队列节点数目
                //重置计数器
                queueExternalNum = 0;
                popNum = 0;
            }
            return -1;//搜索失败
        }
    }
    //DFS
    public static ArrayList<Integer> dfsSearch(boolean[][] maps, int[][] valueMap, int start, int tail){
        LinkedList<Integer> stack = new LinkedList<>();
        int nodeNum = maps.length;
        boolean[] flag = new boolean[nodeNum];
        boolean backtrackingFlag = false;//标记是否出栈，为权重计算做准备
        int lastPoint = 0;//出栈前栈顶元素
        stack.push(start);//将起点压入栈顶
        int minimumValue = 0x3f3f3f3f;//最短路径。初始值我赋了int型的一半
        int nowPathValue = 0;//当前查找到的路径长度
        ArrayList<Integer> finalAns = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        while(!stack.isEmpty()){
            int topNode = stack.peek();
            if(backtrackingFlag){
                nowPathValue -= valueMap[topNode - 1][lastPoint - 1];
            }
            if(!ans.contains(topNode)){
                ans.add(topNode);
            }
            boolean ifSucceed = false;
            for(int i = 0; i < nodeNum; i++){
                if(!flag[i] && maps[topNode - 1][i]){
                    backtrackingFlag = false;
                    nowPathValue += valueMap[topNode - 1][i];
                    if(i == tail - 1){
                        if(minimumValue > nowPathValue){
                            minimumValue = nowPathValue;
                            ans.add(tail);
                            finalAns = new ArrayList<>(ans);
                        }else {
                            ans.clear();
                        }
                    }
                    flag[i] = true;
                    ifSucceed = true;
                    stack.push((i + 1));
                    break;
                }
            }
            if(!ifSucceed){
                backtrackingFlag = true;
                lastPoint = stack.pop();
                ans.remove((ans.size() - 1));
            }
        }
        finalAns.add(minimumValue);
        return finalAns;
    }
}