Java_常见算法

发布时间:2023年12月18日

一、常见算法

1.1 认识算法

接下来,我们认识一下什么是算法。算法其实是解决某个实际问题的过程和方法。比如百度地图给你规划路径,计算最优路径的过程就需要用到算法。再比如你在抖音上刷视频时,它会根据你的喜好给你推荐你喜欢看的视频,这里也需要用到算法。

我们为什么要学习算法呢?主要目的是训练我们的编程思维,还有就是面试的时候,面试官也喜欢问一下算法的问题来考察技术水平。最后一点,学习算法是成为一个高级程序员的必经之路。

1.2 冒泡排序

接下来,我们学习一种算法叫排序算法,它可以将无序的整数,排列成从小到大的形式(升序),或者从大到小的形式(降序)

排序算法有很多种,我们这里只学习比较简单的两种,一种是冒泡排序,一种是选择排序。学习算法我们先要搞清楚算法的流程,然后再去“推敲“如何写代码。(注意,我这里用的次是推敲,也就是说算法这样的代码并不是一次成型的,是需要反复修改才能写好的)。

先来学习冒泡排序,先来介绍一下,冒泡排序的流程:

冒泡排序核心思路:每次将相邻的两个元素继续比较
如下图所示:
   第一轮比较 3次
   第二轮比较 2次
   第三轮比较 1

在这里插入图片描述

public class Test1 {
    public static void main(String[] args) {
        // 1、准备一个数组
        int[] arr = {5, 2, 3, 1};
 
        // 2、定义一个循环控制排几轮
        for (int i = 0; i < arr.length - 1; i++) {
            // i = 0  1  2           【5, 2, 3, 1】    次数
            // i = 0 第一轮            0   1   2         3
            // i = 1 第二轮            0   1             2
            // i = 2 第三轮            0                 1
 
            // 3、定义一个循环控制每轮比较几次。
            for (int j = 0; j < arr.length - i - 1; j++) {
                // 判断当前位置的元素值,是否大于后一个位置处的元素值,如果大则交换。
                if(arr[j] > arr[j+1]){
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

1.2 选择排序

刚才我们学习了冒泡排序,接下来我们学习了另一种排序方法,叫做选择排序。按照我们刚才给大家介绍的算法的学习方式。先要搞清楚算法的流程,再去推敲代码怎么写。

所以我们先分析选择排序算法的流程:选择排序的核心思路是,每一轮选定一个固定的元素,和其他的每一个元素进行比较;经过几轮比较之后,每一个元素都能比较到了。
在这里插入图片描述
接下来,按照选择排序的流程编写代码

public class Test2 {
    public static void main(String[] args) {
        // 1、准备好一个数组
        int[] arr = {5, 1, 3, 2};
        //           0  1  2  3
 
        // 2、控制选择几轮
        for (int i = 0; i < arr.length - 1; i++) {
            // i = 0 第一轮    j = 1 2 3
            // i = 1 第二轮    j = 2 3
            // i = 2 第三轮    j = 3
            // 3、控制每轮选择几次。
            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;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

每一次都交换效率低,可以先找出后面较小值的索引再进行交换
在这里插入图片描述

1.3 查找算法

接下来,我们学习一个查找算法叫做二分查找。在学习二分查找之前,我们先来说一下基本查找,从基本查找的弊端,我们再引入二分查找,这样我们的学习也会更加丝滑一下。

先聊一聊基本查找: 假设我们要查找的元素是81,如果是基本查找的话,只能从0索引开始一个一个往后找,但是如果元素比较多,你要查找的元素比较靠后的话,这样查找的此处就比较多。性能比较差。
在这里插入图片描述

再讲二分查找:二分查找的主要特点是,每次查找能排除一般元素,这样效率明显提高。但是二分查找要求比较苛刻,它要求元素必须是有序的,否则不能进行二分查找。

  • 二分查找的核心思路
1步:先定义两个变量,分别记录开始索引(left)和结束索引(right)2步:计算中间位置的索引,mid = (left+right)/2;3步:每次查找中间mid位置的元素,和目标元素key进行比较
        如果中间位置元素比目标元素小,那就说明mid前面的元素都比目标元素小
            此时:left = mid+1
        如果中间位置元素比目标元素大,那说明mid后面的元素都比目标元素大
            此时:right = mid-1
        如果中间位置元素和目标元素相等,那说明mid就是我们要找的位置
            此时:把mid返回       
注意:一搬查找一次肯定是不够的,所以需要把第1步和第2步循环来做,只到left>end就结束,如果最后还没有找到目标元素,就返回-1.

在这里插入图片描述

在这里插入图片描述

/**
 * 目标:掌握二分查找算法。
 */
public class Test3 {
    public static void main(String[] args) {
        // 1、准备好一个数组。
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
 
        System.out.println(binarySearch(arr, 150));
 
        System.out.println(Arrays.binarySearch(arr, 81));
    }
 
    public static int binarySearch(int[] arr, int data){
        // 1、定义两个变量,一个站在左边位置,一个站在右边位置
        int left = 0;
        int right = arr.length - 1;
 
        // 2、定义一个循环控制折半。
        while (left <= right){
            // 3、每次折半,都算出中间位置处的索引
            int middle = (left + right) / 2;
            // 4、判断当前要找的元素值,与中间位置处的元素值的大小情况。
            if(data < arr[middle]){
                // 往左边找,截止位置(右边位置) = 中间位置 - 1
                right = middle - 1;
            }else if(data > arr[middle]){
                // 往右边找,起始位置(左边位置) = 中间位置 + 1
                left = middle + 1;
            }else {
                // 中间位置处的元素值,正好等于我们要找的元素值
                return middle;
            }
        }
        return -1; // -1特殊结果,就代表没有找到数据!数组中不存在该数据!
    }
}
文章来源:https://blog.csdn.net/qq_48083892/article/details/135021819
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。