Java常见算法_常见的查找算法和排序算法——简介及代码演示

        在本文中我将介绍Java中的常见算法，查找算法包括基本查找、二分查找、插值查找和分块查找。排序算法包括冒泡排序、选择排序、插入排序和快速排序

查找算法：

1.基本查找：
代码：
public class BasicSearchDemo {
    public static void main(String[] args) {
        int[] arr = {1,21,31,41,51,61,71,81};
        Scanner sc = new Scanner(System.in);
        String numStr = sc.nextLine();
        int num = Integer.parseInt(numStr);
        boolean result = basicSearch(arr, num);
        System.out.println(result);
    }
    //基本查找方法
    public static boolean basicSearch(int[] arr, int number) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number) {
                return true;
            }
        }
        return false;
    }
}

这是简单的基本查找，通过遍历数组来查看元素是否存在

运行结果：

基本查找小练习：
代码（含题目要求）：
public class BasicSearchTest {
    public static void main(String[] args) {
        /*
        练习1：
        需求：定义一个方法利用基本查找，查询某个元素在数组中的索引
        要求：不需要考虑数组中元素是否重复
         */

        /*
        练习2：
        需求：定义一个方法利用基本查找，查询某个元素在数组中的索引
        要求：需要考虑数组中元素有重复的可能性
        例如：{1，1，1，2，3，4，5，6，1}
        若查找1，则需要返回所有元素1的索引，即0,1,2,8
         */

        //生成一个数组
        int[] arr = {1,11,21,31,41,51,51,61,51,61};

        //键盘录入一个元素
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入您要查找的元素：");
        String numStr = sc.nextLine();
        int num = Integer.parseInt(numStr);
        System.out.println(getIndex(arr, num));
        System.out.println(getAllIndex(arr, num));
    }

    //练习1
    public static int getIndex(int[] arr, int number) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number) {
                return i;
            }
        }

        return -1;
    }

    //练习2
    public static ArrayList<Integer> getAllIndex(int[] arr, int number) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == number) {
                list.add(i);
            }
        }

        return list;
    }
}
运行结果：

2.二分查找：

特点：

        二分查找的数据必须是按大小顺序排好的
        二分查找可以很大的提高查找效率
代码：
public class BinarySearchDemo1 {
    public static void main(String[] args) {
        //二分查找的数据必须是按大小顺序排好的
        //二分查找可以很大的提高查找效率

        //定义数组
        int[] arr = {1,21,31,41,51,61,71,81};
        //键盘录入一个要查找的元素
        System.out.println("输入要查找的元素：");
        Scanner sc = new Scanner(System.in);
        String numStr = sc.nextLine();
        int num = Integer.parseInt(numStr);
        System.out.println(binarySearch(arr, num));

    }

    //定义二分查找方法
    public static int binarySearch(int[] arr, int num) {
        //用min和max表示当前查找范围
        int min = 0;
        int max = arr.length - 1;
        while (true) {
            //这种情况说明元素不存在
            if(min > max) {
                return -1;
            }
            //定义中间指针
            int mid = (min + max) / 2;
            //进行判断
            if(arr[mid] < num) {
                //元素在右边
                min = mid + 1;
            } else if(arr[mid] > num) {
                //元素在左边
                max = mid - 1;
            } else {
                //找到了
                return mid;
            }
        }
    }
}
3.插值查找：

        改变mid位置时使用数学公式使其更靠近要查找的元素

特点：

        适用于数据分布较均匀的情况下
代码：
public class InterpolationSearch {
    public static void main(String[] args) {
        //适用于数据分布较均匀的情况下
        int[] arr = {1,2,3,5,6,8,9,10};
        System.out.println("请输入要查找的元素值：");
        Scanner sc = new Scanner(System.in);
        String numStr = sc.nextLine();
        int num = Integer.parseInt(numStr);
        int index = interpolationSearch(arr, num);
        System.out.println(index);

    }

    public static int interpolationSearch(int[] arr, int num) {
        //定义查找范围
        int min = 0;
        int max = arr.length - 1;

        while(true) {
            if(min > max) {
                return -1;
            }
            //mid = min + (key - arr[min]) / (arr[max] - arr[min]) * (max - min)
            int mid = min + (num - arr[min]) / (arr[max] - arr[min]) * (max - min);
            if(arr[mid] > num) {
                max = mid - 1;
            } else if(arr[mid] < num) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
    }
}
4.分块查找：

        对数据先进行分块，通过先确定要查找的元素属于哪个块，再只需对那个块进行遍历

代码：
public class BlockSearch {
    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};

        //分块
        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};

        //输入要查找的元素
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入要查找的元素");
        String numStr = sc.nextLine();
        int num = Integer.parseInt(numStr);

        int index = getIndex(arr, blockArr, num);
        System.out.println(index);

    }

    private static int getIndex(int[] arr, Block[] blockArr, int num) {
        int blockIndex = getBlock(blockArr, num);
        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] == num) {
                return i;
            }
        }
        return -1;
    }

    private static int getBlock(Block[] blockArr, int num) {
        for (int i = 0; i < blockArr.length; i++) {
            if(num < 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.冒泡排序：
特点：
        相邻的元素两两比较，大的放右边，小的放左边（从小到大情况）
        第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
        如果数组中有n个数据，那总共执行n-1轮代码就可以
代码：
public class BubbleSort {
    public static void main(String[] args) {
        //相邻的元素两两比较，大的放右边，小的放左边（从小到大情况）
        //第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
        //如果数组中有n个数据，那总共执行n-1轮代码就可以

        //创建一个数组
        int[] arr = {1,4,5,2,3,9,5,6};
        int[] resultArr = bubbleSort(arr);
        for (int i = 0; i < resultArr.length; i++) {
            System.out.println(resultArr[i]);
        }
    }

    private static int[] bubbleSort(int[] arr) {
        //外循环：要进行几轮
        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;
                }
            }
        }

        return arr;
    }
}
2.选择排序：
特点：
        从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较
        小的放前面，大的放后面（从小到大情况），以此类推
        第一轮循环结束后，最小的数据已经确定
        第二轮循环从1索引开始，以此类推
代码：
public class SelectionSort {
    public static void main(String[] args) {
        //从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较
        //小的放前面，大的放后面（从小到大情况），以此类推
        //第一轮循环结束后，最小的数据已经确定
        //第二轮循环从1索引开始，以此类推

        //创建数组
        int[] arr = {4,3,9,5,6,8,2,1};
        int[] resultArr = bubbleSort(arr);
        for (int i = 0; i < resultArr.length; i++) {
            System.out.println(resultArr[i]);
        }

    }

    public static int[] bubbleSort(int[] arr) {
        //外循环：表示几轮
        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;
                }
            }
        }

        return arr;
    }
}
3.插入排序：
特点：
        将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个元素当成是无序的。
        遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
代码：
public class InsertionSort {
    public static void main(String[] args) {
        //将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个元素当成是无序的。
        //遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

        //创建数组
        int[] arr = {1,6,5,3,9,7,16,1,22,3};
        int[] resultArr = insertionSort(arr);
        for (int i = 0; i < resultArr.length; i++) {
            System.out.println(resultArr[i]);
        }
    }

    public static int[] insertionSort(int[] arr) {
        //判断有序元素个数
        int index = 0;
        for (int i = 1; i < arr.length; i++) {
            if(arr[index] < arr[index + 1]) {
                index++;
            } else {
                break;
            }
        }
        //index为最后一个有序元素的索引

        //有序元素后面的每个元素要插入有序元素中   插入后有序元素加1   索引也++

        //我的其他思路   复杂了。。
        /*
        for (; index < arr.length - 1; index++) {
            int i = index + 1;
            for(int j = index; j >= 0; j--) {
                if(arr[i] >= arr[j]) {
                    break;
                } else {
                    //有序元素后面的无序元素只要比前面的小就交换位置
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i--;
                    continue;
                }
            }
        }
        */

        //从有序数组后的第一个元素到最后一个元素
        for (int i = index + 1; 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--;
            }
        }

        return arr;
    }
}
4.快速排序

        这里展示快速排序之前要先学会递归思想，我先来放两个递归思想的小练习

递归练习一 题目及代码：
public class RecursionAlgorithmTest1 {
    public static void main(String[] args) {
        //核心：找出口 找规律
        //方法中再次调用方法时，参数应更接近出口

        //求1~100所有整数的和
        int sum = getSum(100);
        System.out.println(sum);
    }

    //1~100所有整数的和 = 100 + 1~99的和
    //1~99的和 = 99 + 1~98的和
    //…………
    public static int getSum(int num) {
        //出口
        if(num == 1) {
            return 1;
        }
        return num + getSum(num - 1);
    }
}
递归练习二 题目及代码：
public class RecursionAlgorithmTest2 {
    public static void main(String[] args) {
        //需求：用递归求5的阶乘，并把结果在控制台输出
        int factorail = getFactorail(5);
        System.out.println(factorail);
    }

    //5的阶乘 = 5 * 4的阶乘
    //4的阶乘 = 4 * 3的阶乘
    //…………
    public static int getFactorail(int num) {
        //出口
        if(num == 1) {
            return 1;
        }
        return num * getFactorail(num - 1);
    }
}

        接下来开始讲解快速排序：

过程：
//将排序范围中的第一个数字作为基准数，在定义两个变量start，end
//start从前往后找比基准数大的，end从后往前找比基准数小的。
/*找到之后交换start和end指向的元素，并循环这一过程，直到start和end处于同一个位置，
该位置是基准数在数组中应存入的位置，再让基准数归位*/
//归为后的效果：基准数左边的都比基准数小，右边的都比基准数大
代码演示：
public class QuickSort {
    public static void main(String[] args) {
        //创建数组
        int[] arr = {6,2,3,1,7,5,8};
        int start = 0;
        int end = arr.length - 1;
        quickSort(arr, start, end);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }

    private static void quickSort(int[] arr, int i, int j) {
        //出口
        if(i >= j) {
            return;
        }
        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++;
            }
            //交换位置
            int temp = arr[end];
            arr[end] = arr[start];
            arr[start] = temp;
        }
        //将基准数与当前start和end索引所在位置交换
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        //基准数左边继续重复刚才所做的事
        quickSort(arr, i, start - 1);
        //基准数右边继续重复刚才所做的事
        quickSort(arr, start + 1, j);


    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/529947.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

电商技术揭秘十五：数据挖掘与用户行为分析

电商技术揭秘十五：数据挖掘与用户行为分析

相关系列文章 电商技术揭秘一&#xff1a;电商架构设计与核心技术 电商技术揭秘二&#xff1a;电商平台推荐系统的实现与优化 电商技术揭秘三&#xff1a;电商平台的支付与结算系统 电商技术揭秘四&#xff1a;电商平台的物流管理系统 电商技术揭秘五&#xff1a;电商平台…
阅读更多...
Harmony鸿蒙南向驱动开发-ADC

Harmony鸿蒙南向驱动开发-ADC

ADC&#xff08;Analog to Digital Converter&#xff09;&#xff0c;即模拟-数字转换器&#xff0c;可将模拟信号转换成对应的数字信号&#xff0c;便于存储与计算等操作。除电源线和地线之外&#xff0c;ADC只需要1根线与被测量的设备进行连接&#xff0c;其物理连线如图1所…
阅读更多...
《前端面试题》- JS基础 - call()、apply()、bind() 的区别

《前端面试题》- JS基础 - call()、apply()、bind() 的区别

call 、bind 、 apply 这三个函数的功能都是改变this的指向问题&#xff0c;但是也存在一定的区别。 call 的参数是直接放进去的&#xff0c;第二第三第 n 个参数全都用逗号分隔,apply 的所有参数都必须放在一个数组里面传进去bind 除了返回是函数以外&#xff0c;它 的参数和…
阅读更多...
Idea中 maven 下载jar出现证书问题

Idea中 maven 下载jar出现证书问题

目录 1&#xff1a; 具体错误&#xff1a; 2&#xff1a; 忽略证书代码&#xff1a; 3&#xff1a; 关闭所有idea&#xff0c; 清除缓存&#xff0c; 在下面添加如上忽略证书代码 4&#xff1a;执行 maven clean 然后刷刷新依赖 完成&#xff0c;撒花&#xff01;&#x…
阅读更多...
DRF的认证、权限、限流、序列化、反序列化

DRF的认证、权限、限流、序列化、反序列化

DRF的认证、权限、限流、序列化、反序列化 一、认证 1、直接用&#xff0c;用户授权 实现方法 编写 ->认证组件 应用组件 编写 ->认证组件 from rest_framework.authentication import BaseAuthentication from rest_framework.exceptions import AuthenticationF…
阅读更多...
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图

基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1遗传算法与模拟退火算法简介 4.2 GSAHO算法应用于JSSP 5.完整程序 1.程序功能描述 车间作业调度问题&#xff08;Job Shop Scheduling Problem, JSSP&#xff09;是一种典型的生产调度问…
阅读更多...
数据仓库的概念和作用？如何搭建数据仓库？

数据仓库的概念和作用？如何搭建数据仓库？

随着企业规模的扩大和数据量的爆炸性增长&#xff0c;有效管理和分析海量数据成为企业数字化转型的关键。而在互联网的普及过程中&#xff0c;信息技术已深入渗透各行业&#xff0c;逐渐融入企业的日常运营。然而&#xff0c;企业在信息化建设中面临了一系列困境和挑战&#xf…
阅读更多...
登录压力测试

登录压力测试

目录 一、准备测试数据 1.1数据库存储过程添加数据 1.2导出为csv作为测试数据&#xff08;账号、密码&#xff09; 二、使用fiddler抓包查看接口 2.1.抓到相关接口信息 2.2添加线程组和http请求 2.3将前面接口需要的参数去json格式化 ​2.4填写相关信息 ​ 2.5添加http…
阅读更多...
gpt科普1 GPT与搜索引擎的对比

gpt科普1 GPT与搜索引擎的对比

GPT&#xff08;Generative Pre-trained Transformer&#xff09;是一种基于Transformer架构的自然语言处理模型。它通过大规模的无监督学习来预训练模型&#xff0c;在完成这个阶段后&#xff0c;可以用于各种NLP任务&#xff0c;如文本生成、机器翻译、文本分类等。 以下是关…
阅读更多...
【网络安全】WebPack源码（前端源码）泄露 + jsmap文件还原

【网络安全】WebPack源码（前端源码）泄露 + jsmap文件还原

前言 webpack是一个JavaScript应用程序的静态资源打包器。它构建一个依赖关系图&#xff0c;其中包含应用程序需要的每个模块&#xff0c;然后将所有这些模块打包成一个或多个bundle。大部分Vue等项目应用会使用webpack进行打包&#xff0c;使用webpack打包应用程序会在网站js…
阅读更多...
集成 LlamaIndex 和 Qdrant 相似性搜索以进行患者记录检索

集成 LlamaIndex 和 Qdrant 相似性搜索以进行患者记录检索

介绍 由于医疗技术、数字健康记录（EHR）和可穿戴健康设备的进步，医疗领域目前正在经历数据的显着激增。有效管理和分析这些复杂多样的数据的能力对于提供定制医疗保健、推进医学研究和改善患者健康结果至关重要。矢量数据库是专门为高效处理和存储多维数据而定制的，作为一系…
阅读更多...
image with CV

image with CV

""" 视觉&#xff1a;基本API应用&#xff08;OPENCV&#xff09; """ import cv2 import numpy as np"""图像读取方式3. 1.cv2.imread(filename or path, flags)flags0:灰度图像&#xff1b;flags1表示RGB图像&#xff1b;fl…
阅读更多...
每日Bug汇总--Day02

每日Bug汇总--Day02

Bug汇总—Day02 一、项目运行出错 1、问题&#xff1a;运行SpringBoot项目重新导入Maven报错 org.springframework.boot:spring-boot-dependencies:pom:2.2.2.RELEASE failed to transfer from https://repo.maven.apache.org/maven2 during a previous attempt. This failu…
阅读更多...
【示例】Spring-IOC理解

【示例】Spring-IOC理解

前言 本文从常规的开发示例&#xff08;DAO、Service、Client&#xff09;入手&#xff0c;逐步体会理解IOC的原理及实现。 文中示例的代码地址&#xff1a; GitHubhttps://github.com/Web-Learn-GSF/Java_Learn_Examples父工程Java_Framework_Spring 示例 | 常规三层开发示…
阅读更多...
智能合约NFT代币系统的开发：构建数字资产生态

智能合约NFT代币系统的开发：构建数字资产生态

随着区块链技术的迅速发展和数字资产市场的不断壮大&#xff0c;智能合约NFT&#xff08;非同质化代币&#xff09;代币系统成为了吸引眼球的焦点之一。本文将深入探讨智能合约NFT代币系统的开发&#xff0c;以及它如何构建数字资产生态。 引言 数字资产市场的迅速发展和区块链…
阅读更多...
RAGFlow：基于OCR和文档解析的下一代 RAG 引擎

RAGFlow：基于OCR和文档解析的下一代 RAG 引擎

一、引言 在人工智能的浪潮中&#xff0c;检索增强生成&#xff08;Retrieval-Augmented Generation&#xff0c;简称RAG&#xff09;技术以其独特的优势成为了研究和应用的热点。RAG技术通过结合大型语言模型&#xff08;LLMs&#xff09;的强大生成能力和高效的信息检索系统…
阅读更多...
抖音评论ID批量提取采集软件|视频评论下载工具

抖音评论ID批量提取采集软件|视频评论下载工具

抖音评论ID批量提取采集软件&#xff1a;拓展你的抖音市场营销&#xff01; 正文&#xff1a; 在当今社交媒体兴盛的时代&#xff0c;抖音作为一款风靡全球的短视频应用&#xff0c;成为了企业营销的热门平台之一。然而&#xff0c;如何获取并利用抖音用户的评论信息进行精准…
阅读更多...
电脑更新到win11后不能上网,更新win11后无法上网

电脑更新到win11后不能上网,更新win11后无法上网

越来越多的用户升级了win11系统使用&#xff0c;然而有些用户发现电脑更新到win11后不能上网了&#xff0c;这是怎么回事呢?而且奇怪的是&#xff0c;网络状态显示已连接&#xff0c;但就是无法上网&#xff0c;原本以为重置网络就能搞定&#xff0c;但结果相反。针对这一情况…
阅读更多...
Windows系统上运行appium连接iOS真机自动化测试

Windows系统上运行appium连接iOS真机自动化测试

步骤： 1、windows安装tidevice工具 2、Mac系统打包安装WebDriverAgent（WDA）工具 3、安装Appium 4、连接iOS手机 iOS自动化的实现和执行都依赖Mac系统，因为需要通过Xcodebuild编译安装WDA (WebDriverAgent)到iOS设备中，通过WDA实现对被测应用进行操作。而Windows系统无…
阅读更多...
1.Godot引擎|场景|节点|GDS|介绍

1.Godot引擎|场景|节点|GDS|介绍

Godot介绍 Godot是一款游戏引擎 可以通过在steam商城免费下载 初学者和编程基础稍差的推荐学习使用GDScript&#xff0c;和python有些相似 Godot节点 Godot的开发思想——围绕节点 节点的特征与优势 最常用基本的开发组件大部分都具有具体的功能&#xff0c;如图片&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023