JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)

简介: JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)

认识算法

什么是算法?


算法就像是一个厨房里的食谱。当你想做一道菜时,你需要按照食谱上的步骤来操作,确保每一步都做对了,这样才能做出美味的菜肴。同样地,算法就是一系列解决问题的步骤,它告诉计算机如何处理数据,从而得到我们想要的结果

算法就像是一个聪明的助手,它可以帮助我们完成各种任务,比如排序、搜索、预测天气等等。只要我们给它正确的指令和数据,它就能按照预定的步骤,快速而准确地完成任务。


为什么要学习算法?


学习算法可以让我们更好地理解编程的本质,提高我们的编程能力。这样,我们就可以写出更好的程序,解决更复杂的问题。而且算法不仅可以用在计算机上,还可以用在生活中的很多地方。例如,烹饪食谱、旅行计划、投资策略等都可以看作是一种算法。

学习算法的技巧


  1. 理解问题:在尝试编写代码之前,首先要彻底理解问题。先搞清楚算法的流程。
  2. 逐步实现:将算法分解成小的、可管理的部分,并逐步实现它们。这可以使问题更容易处理,并允许你在每个步骤中进行测试和调试。
  3. 最后直接去推敲如何写代码。

那么下面就先来看两个简单的排序算法:

  • 冒泡排序
  • 选择排序

冒泡排序

介绍

从初始索引开始,当前索引与之后的索引两两比较,每比较完一次索引增加一次,每次从数组中找出最大值放在数组的后面去。

实现冒泡排序的关键步骤分析


  • 确定总共需要做几轮:数组的长度 - 1
  • 每轮比较几次:数组的长度 - i - 1  (i为当前的轮数 - 1)
  • 当前位置大于后一个位置则交换数据

详细图解

假设我们要将一个数组按升序排序,从数组的第一个数和第二个数开始进行比较;

我们先来看第一轮排序

第一轮比较的次数:3次 (也就是数组的长度4 - 0(当前轮数 - 1) - 1

接下来看第二轮排序:

   

第二轮比较的次数:2次 (也就是数组的长度4 - 1(当前轮数 - 1) - 1

那么第三轮比较的次数就为1次了。



该数组的长度为4,故而需要比较的轮数为:3次        (数组的长度 4 - 1)


由于冒泡排序的每一轮排序都会把一个最大或者最小的元素放在最后的位置,这个元素与前面所有的元素都比较过了,已经是确定的值,所以我们不再需要对它进行比较;所以每比较一轮,我们就少一个需要比较的元素。

代码部分

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

运行结果:

选择排序

介绍

  • 每轮选择当前位置,开始找出后面的较小值(或较大值)与该位置交换。

比如第一轮比较:第一个元素分别与后面所有的元素进行比较,根据升序或降序进行交换。

选择排序的关键

  • 确定总共需要选择几轮:数组的长度 - 1
  • 控制每轮从以前位置为基准,与后面元素选择几次

还是以上一个数组为例子,

详细图解

第一轮比较了3次

第二轮比较了2次

第三轮就比较一次:

代码部分

import java.util.Arrays;
 
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {5,1,3,2};
 
 
        for(int i = 0; i < arr.length - 1; i++){
 
            for(int j = i +1; j < arr.length; j++){
                if(arr[i] > arr[j]){
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

运行结果:


选择排序优化

对于选择排序,其实我们可以稍加优化。不再进行多次的元素交换,而改为每轮排序都只交换一次,也就是说,我们可以在后面的索引中找到最小值(或最大值)与当前索引位置的元素进行一次比较,然后作一次交换即可。

图解

以图解的形式演示

代码部分

import java.util.Arrays;
 
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {5,1,3,2};
        for(int i = 0; i < arr.length - 1; i++){
            int minIndex = i;   //记录最小值的索引
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if(arr[i] > arr[minIndex]){
                arr[i] = arr[i] ^ arr[minIndex];
                arr[minIndex] = arr[i] ^ arr[minIndex];
                arr[i] = arr[i] ^ arr[minIndex];
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

运行结果:



同样的环境下,效率对比:

import java.util.Arrays;
import java.util.Random;
 
public class SelectionSort {
    public static void main(String[] args) {
        Random r = new Random();
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(1000000) + 1;
        }
 
        long time1 = System.currentTimeMillis();
        for(int i = 0; i < arr.length - 1; i++){
 
            for(int j = i +1; j < arr.length; j++){
                if(arr[i] > arr[j]){
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
            }
        }
        long time2 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("执行时间:" + (time2 - time1) / 1000.0 + "s");
    }
}
import java.util.Arrays;
import java.util.Random;
 
public class SelectionSort {
    public static void main(String[] args) {
        Random r = new Random();
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(1000000) + 1;
        }
 
        long time1 = System.currentTimeMillis();
        for(int i = 0; i < arr.length - 1; i++){
            int minIndex = i;   //记录最小值的索引
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if(arr[i] > arr[minIndex]){
                arr[i] = arr[i] ^ arr[minIndex];
                arr[minIndex] = arr[i] ^ arr[minIndex];
                arr[i] = arr[i] ^ arr[minIndex];
            }
        }
        long time2 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("执行时间:" + (time2 - time1) / 1000.0 + "s");
    }
}

END



目录
相关文章
|
3天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
16 7
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
2天前
|
机器学习/深度学习 算法 计算机视觉
通过MATLAB分别对比二进制编码遗传优化算法和实数编码遗传优化算法
摘要: 使用MATLAB2022a对比了二进制编码与实数编码的遗传优化算法,关注最优适应度、平均适应度及运算效率。二进制编码适用于离散问题,解表示为二进制串;实数编码适用于连续问题,直接搜索连续空间。两种编码在初始化、适应度评估、选择、交叉和变异步骤类似,但实数编码可能需更复杂策略避免局部最优。选择编码方式取决于问题特性。
|
19小时前
|
传感器 算法 数据安全/隐私保护
基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
```markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合,模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略,优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例,旨在最小化未覆盖区域。 ```
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
|
3天前
|
算法 Python
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
12 0
|
4天前
|
存储 传感器 算法
基于ACO蚁群优化算法的WSN网络路由优化matlab仿真
摘要(Markdown格式): - 📈 ACO算法应用于WSN路由优化,MATLAB2022a中实现,动态显示迭代过程,输出最短路径。 - 🐜 算法模拟蚂蚁寻找食物,信息素更新与蚂蚁选择策略确定路径。信息素增量Δτ += α*τ*η,节点吸引力P ∝ τ / d^α。 - 🔁 算法流程:初始化→蚂蚁路径选择→信息素更新→判断结束条件→输出最优路由。优化WSN能量消耗,降低传输成本。