图解算法--排序算法

目录

1.冒泡排序算法

2.选择排序算法

3.插入排序算法

4.希尔排序算法

5.归并排序算法

6.快速排序算法

1.冒泡排序算法

原理讲解：

  1. 从待排序的数组中的第一个元素开始，依次比较当前元素和它相邻的下一个元素的大小。
  2. 如果当前元素大于相邻元素，则交换这两个元素的位置，将较大的元素向后冒泡。
  3. 继续比较相邻元素，重复以上步骤，直到遍历完整个数组。
  4. 一轮遍历完成后，最大的元素将会排在最后面。
  5. 重复执行上述步骤，每次遍历都将会使待排序的元素中最大的元素冒泡到正确的位置，直到所有元素都有序排列。

 传统的冒泡排序算法

package Sort.Bubble;

import java.util.Arrays;

public class javaDemo {
    public static void main(String[] args) {
        int nums[] = new int[]{1,4,36,7,42,2,12,5,2};
        int temp;
//        冒泡算法
        for (int i=0;i< nums.length-1;i++){
            for (int j=0;j< nums.length-i-1;j++){
                if (nums[j]>nums[j+1]){
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}

传统的排序算法有个缺点，那就是不管数据是否已经完成排序都会固定执行n(n-1)/2次，而如果加入岗哨的概念进行改造冒泡排序算法就可以提高程序的执行效率

传统冒泡执行已经快要排序好的数组结果如下：

可以看到在第二轮时候就已经排序好了，但是还是不断进行遍历，所以加入一个岗哨（flag）判断功能，当第三轮时候，如果没有元素进行交换后直接退出排序 。

改进型冒泡排序法

package Sort.Bubble;

import java.util.Arrays;

public class Sentry {
    public static void main(String[] args) {
        int num[] = new int[]{1,4,5,2,7,8,9};
        int flag;
        int temp;
        for (int i= num.length-1;i>0;i--){
            flag = 0;
//            如果发生了交换则不跳出
            for (int j=0;j<i-1;j++){
                if (num[j]>num[j+1]){
                 temp = num[j];
                 num[j] = num[j+1];
                 num[j+1] = temp;
                 flag ++;
                }
            }
//            如果从头遍历结束都没有交换则直接退出
            if (flag == 0){
                break;
            }
            System.out.println("第"+(num.length-i)+"轮排序结果为"+ Arrays.toString(num));
        }
    }
}

 算法分析：

  • 冒泡排序算法在最坏的情况下时间复杂度是O(n^2)
  • 在最好的情况下时间复杂度是O(n)

2.选择排序算法

原理讲解： 

  1. 遍历待排序的数组，将第一个元素作为当前最小值。
  2. 从当前位置之后的元素中找到最小的元素，并记录其位置。
  3. 如果找到了比当前最小值更小的元素，则将该元素的位置更新为当前最小值的位置。
  4. 遍历完整个数组后，将最小值与当前位置的元素进行交换。
  5. 继续从下一个位置开始重复以上步骤，直到遍历完整个数组。

案例代码

package Sort.Chose.chose;

import java.util.Arrays;

public class javaDemo {
    public static void main(String[] args) {
        int nums[] = new int[]{1,2,4,2,3,51,12,6,2};
        int min;
        int index;
        int temp;
        for (int i=0;i< nums.length-1;i++){
//            每一轮初始化最小值与最小值下角标
            min = nums[i];
            index = i;
            for (int j=i+1;j< nums.length;j++){
                if (min>nums[j]){
                    min = nums[j];
                    index = j;
                }
            }
             temp = nums[i];
            nums[i] = min;
            nums[index] = temp;
        }
        System.out.println(Arrays.toString(nums));
    }
}

 算法分析：

  • 冒泡排序算法无论在最坏还是最好的情况下时间复杂度都是O(n^2)

3.插入排序算法

 原理讲解：

  1. 将数组分为已排序和未排序两部分。一开始，将第一个元素视为已排序部分，其余元素视为未排序部分。
  2. 从未排序部分选择第一个元素，依次与已排序部分的元素比较。
  3. 如果选取的元素小于已排序部分的某个元素，则将该元素插入到正确的位置，同时将已排序部分中的元素向后移动一位。
  4. 重复上述步骤，将未排序部分的每个元素逐个插入到已排序部分的正确位置。
  5. 当所有元素都插入完成，即未排序部分为空时，排序完成。

案例代码  

package Sort.InsertSort;

import java.util.Arrays;

public class javaDemo {
    public static void main(String[] args) {
        int nums[] = new int[]{4,1,5,2,6,7,2};
        int temp;
        for (int i=0;i< nums.length;i++){
            for (int j=0;j<i;j++){
                if (nums[i]<nums[j]){
                    temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
            System.out.println("第"+(i+1)+"轮排序结果为"+ Arrays.toString(nums));
        }
    }
}

算法分析：

  • 冒泡排序算法在最坏的情况下时间复杂度是O(n^2)
  • 在最好的情况下时间复杂度是O(n)

4.希尔排序算法

  原理讲解：

  1. 首先，选择一个增量 gap，通常将数组长度的一半作为初始增量。
  2. 将数组按照增量进行分组，并对每个分组使用插入排序算法进行排序。
  3. 逐渐缩小增量，重复以上步骤，直到增量为 1。
  4. 最后使用增量为 1 的插入排序对整个数组进行最后一次排序

案例代码：

package Sort.Shell;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3, 6, 4};
        int n = arr.length;

        // 定义增量序列
        int[] increments = {5, 3, 1};
        System.out.println("原始数组顺序为"+Arrays.toString(arr));
        // 遍历增量序列
        for (int increment : increments) {

            // 对每个增量进行插入排序
            for (int i = increment; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // 在当前增量下，对子序列进行插入排序
                while (j >= increment && arr[j - increment] > temp) {
                    arr[j] = arr[j - increment];
                    j -= increment;
                }
                arr[j] = temp;
                System.out.println("当前增量为"+increment+"，当前数组为："+Arrays.toString(arr));
            }

        }
    }
}

算法分析：

  • 希尔排序算法无论在最坏还是最好的情况下时间复杂度都是O(n^3/2)
  • 空间最优解

5.归并排序算法

   原理讲解：

  1. 将待排序的数组递归地分成两个子数组，直到每个子数组只有一个元素。
  2. 对每个子数组进行合并操作，将两个有序的子数组合并成一个有序的数组。
  3. 重复以上步骤，直到所有的子数组都被合并成一个完整的有序数组。

案例代码：

package Sort.MergeSort;

import java.util.Arrays;

public class mergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp); // 递归排序左半部分
            mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分
            merge(arr, left, mid, right, temp); // 合并左右两个有序数组
        }
        System.out.println("当前顺序为"+Arrays.toString(arr));
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 左半部分起始索引
        int j = mid + 1; // 右半部分起始索引
        int k = 0; // 临时数组索引

        // 将左右两个有序数组按顺序合并到temp数组中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 处理剩余的元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将临时数组的元素拷贝回原数组
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3, 6, 4};
        System.out.println("原始数组："+ Arrays.toString(arr));
        mergeSort(arr);
    }
}

算法分析：

  • 归并排序算法无论在最坏还是最好的情况下时间复杂度都是O(nlogn)

6.快速排序算法

   原理讲解：

  1. 选择一个基准元素（通常是数组的第一个或最后一个元素）作为参考点。
  2. 将待排序的数组分成两个子数组，其中一个子数组中的元素小于等于基准元素，另一个子数组中的元素大于基准元素。
  3. 对这两个子数组分别重复上述步骤，递归地进行快速排序。
  4. 当子数组的长度为 1 或 0 时，递归终止。
  5. 将排序好的子数组合并起来，即可得到完整的有序数组。

案例代码：

package Sort.Quick;

import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high); // 将数组划分为两部分，返回中轴元素的索引
            quickSort(arr, low, pivotIndex - 1); // 递归排序左半部分
            quickSort(arr, pivotIndex + 1, high); // 递归排序右半部分
        }
        System.out.println("当前数组为"+Arrays.toString(arr));
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选择第一个元素作为中轴元素
        int left = low;
        int right = high;

        while (left < right) {
            // 从右向左找第一个小于等于中轴元素的位置
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            if (left < right) {
                arr[left] = arr[right];
                left++;
            }

            // 从左向右找第一个大于中轴元素的位置
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (left < right) {
                arr[right] = arr[left];
                right--;
            }
        }

        arr[left] = pivot; // 将中轴元素放置到最终位置
        return left; // 返回中轴元素的索引
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3, 6, 4};

        System.out.printf("原始数组：");
        System.out.println(Arrays.toString(arr));
        quickSort(arr);
    }
}

 算法分析：

  • 快速排序算法在最坏的情况下时间复杂度是O(nlog2n)
  • 在最好的情况下时间复杂度是O(n)
  • 公认最好的排序算法

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

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

相关文章

【Elasticsearch】spring-boot-starter-data-elasticsearch的使用以及Elasticsearch集群的连接

【Elasticsearch】spring-boot-starter-data-elasticsearch的使用以及Elasticsearch集群的连接

更多有关博主写的往期Elasticsearch文章 标题地址【ElasticSearch 集群】Linux安装ElasticSearch集群&#xff08;图文解说详细版&#xff09;https://masiyi.blog.csdn.net/article/details/131109454基于SpringBootElasticSearch 的Java底层框架的实现https://masiyi.blog.c…
阅读更多...
【Linux命令详解 | ssh命令】 ssh命令用于远程登录到其他计算机，实现安全的远程管理

【Linux命令详解 | ssh命令】 ssh命令用于远程登录到其他计算机，实现安全的远程管理

文章标题 简介一&#xff0c;参数列表二&#xff0c;使用介绍1. 连接远程服务器2. 使用SSH密钥登录2.1 生成密钥对2.2 将公钥复制到远程服务器 3. 端口转发3.1 本地端口转发3.2 远程端口转发 4. X11转发5. 文件传输与远程命令执行5.1 文件传输5.1.1 从本地向远程传输文件5.1.2 …
阅读更多...
时序预测 | MATLAB实现WOA-CNN-GRU鲸鱼算法优化卷积门控循环单元时间序列预测

时序预测 | MATLAB实现WOA-CNN-GRU鲸鱼算法优化卷积门控循环单元时间序列预测

时序预测 | MATLAB实现WOA-CNN-GRU鲸鱼算法优化卷积门控循环单元时间序列预测 目录 时序预测 | MATLAB实现WOA-CNN-GRU鲸鱼算法优化卷积门控循环单元时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 时序预测 | MATLAB实现WOA-CNN-GRU鲸鱼算法优化卷积…
阅读更多...
Linux 网络发包流程

Linux 网络发包流程

哈喽大家好&#xff0c;我是咸鱼 之前咸鱼在《Linux 网络收包流程》一文中介绍了 Linux 是如何实现网络接收数据包的 简单回顾一下&#xff1a; 数据到达网卡之后&#xff0c;网卡通过 DMA 将数据放到内存分配好的一块 ring buffer 中&#xff0c;然后触发硬中断CPU 收到硬中…
阅读更多...
nn.embedding会被反向传播更新吗？

nn.embedding会被反向传播更新吗？

https://developer.aliyun.com/article/1191215 这样是不可更新&#xff0c;但被我注释掉了。
阅读更多...
[oneAPI] 手写数字识别-VAE

[oneAPI] 手写数字识别-VAE

[oneAPI] 手写数字识别-VAE oneAPIVAE模型实现手写数字识别任务定义使用包定义参数加载数据VAE模型与介绍训练过程结果 比赛&#xff1a;https://marketing.csdn.net/p/f3e44fbfe46c465f4d9d6c23e38e0517 Intel DevCloud for oneAPI&#xff1a;https://devcloud.intel.com/one…
阅读更多...
记录一下基于jeecg-boot3.0的待办消息移植记录

记录一下基于jeecg-boot3.0的待办消息移植记录

因为之前没有记录&#xff0c;所以还要看代码进行寻找&#xff0c;比较费劲&#xff0c;所以今天记录一下&#xff1a; 1、后端 SysAnnouncementController 下面函数增加待办的几个显示内容给前端用 具体代码如下&#xff1a; /*** 功能&#xff1a;补充用户数据&#xff0c…
阅读更多...
Nginx 解决api跨域问题

Nginx 解决api跨域问题

环境: nginx 1.22.1 宝塔8.0 php lavarel 在nginx里加入下面的设置 #这里填*就是任何域名都允许跨域add_header Access-Control-Allow-Origin "*";#CORS请求默认不发送Cookie和HTTP认证信息。但是如果要把Cookie发到服务器&#xff0c;要服务器同意&#xff0c…
阅读更多...
JVM——类的生命周期

JVM——类的生命周期

文章目录 类加载过程加载验证准备解析初始化 卸载 一个类的完整生命周期如下&#xff1a; 类加载过程 Class 文件需要加载到虚拟机中之后才能运行和使用&#xff0c;那么虚拟机是如何加载这些 Class 文件呢&#xff1f; 系统加载 Class 类型的文件主要三步:加载->连接->…
阅读更多...
微服务实战项目-学成在线-项目部署

微服务实战项目-学成在线-项目部署

微服务实战项目-学成在线-项目部署 1 什么是DevOps 一个软件的生命周期包括&#xff1a;需求分析阶、设计、开发、测试、上线、维护、升级、废弃。 通过示例说明如下&#xff1a; 1、产品人员进行需求分析 2、设计人员进行软件架构设计和模块设计。 3、每个模块的开发人员…
阅读更多...
软考笔记——10.项目管理

软考笔记——10.项目管理

进度管理 进度管理就是采用科学的方法&#xff0c;确定进度目标&#xff0c;编制进度计划和资源供应计划&#xff0c;进行进度控制&#xff0c;在与质量、成本目标协调的基础上&#xff0c;实现工期目标。 具体来说&#xff0c;包括以下过程&#xff1a; (1) 活动定义&#…
阅读更多...
MES生产管理系统如何与ERP系统集成

MES生产管理系统如何与ERP系统集成

MES生产管理系统和ERP企业管理系统是制造企业信息化的重要组成部分&#xff0c;它们在生产管理、资源计划和业务流程等方面发挥着重要作用。实现MES与ERP系统的集成&#xff0c;可以更好地优化企业生产流程&#xff0c;提高生产效率和降低成本。本文将探讨MES管理系统解决方案如…
阅读更多...
传感网应用开发实训室建设方案

传感网应用开发实训室建设方案

传感网应用开发实训室概述 物联网是我国战略性新兴产业的重要组成部分&#xff0c;《物联网“十二五”发展规划》圈定了10大领域重点示范工程&#xff0c;第一个关键技术创新工程提出“充分发挥企业主体作用&#xff0c;积极利用高校和研究所实验室的现有研究成果&#xff0c;在…
阅读更多...
Vue 根据Upload组件的before-upload方法，限制用户上传文件的类型及大小

Vue 根据Upload组件的before-upload方法，限制用户上传文件的类型及大小

文章目录 一、前端 Vue Upload组件的before-upload方法二&#xff0c;使用方法 一、前端 Vue Upload组件的before-upload方法 判断用户上传的文件是否符合要求&#xff0c;可以根据文件类型或者大小做出限制。 文件类型值docapplication/msworddocxapplication/vnd.openxmlform…
阅读更多...
VS2019+Qt5.15.2 编译 QtWebEngine（带音视频解码）

VS2019+Qt5.15.2 编译 QtWebEngine（带音视频解码）

前言 QtWebEngine 是 Qt 框架的一部分&#xff0c;用于构建现代 Web 浏览器功能。本篇教程将向您展示如何在 Visual Studio 2019 中编译 QtWebEngine 5.15.2 源码&#xff0c;并配置以支持音视频解码功能。 准备工作 1、源码下载 2、源码修改&#xff0c;参考Qt Code Review…
阅读更多...
【Python】使用python解析someip报文，以someip格式打印报文

【Python】使用python解析someip报文，以someip格式打印报文

文章目录 1.安装scapy库2.示例 1.安装scapy库 使用 pip 安装 scapy 第三方库&#xff0c;打开 cmd&#xff0c;输入以下命令&#xff1a; pip install scapy出现如图所示&#xff0c;表示安装成功&#xff1a; 2.示例 要解析someip格式报文&#xff0c;需要导入someip模块&a…
阅读更多...
【electron】electron项目创建的方式：

【electron】electron项目创建的方式：

文章目录 【1】npm init quick-start/electron&#xff08;推荐&#xff09;【2】 克隆仓库&#xff0c;快速启动【3】 通过脚手架搭建项目【4】 手动创建项目 【Electron官网】https://www.electronjs.org/zh/docs/latest/api/app 【1】npm init quick-start/electron&#xf…
阅读更多...
Mysql_5.7下载安装与配置基础操作教程

Mysql_5.7下载安装与配置基础操作教程

目录 一、Mysql57下载与安装 二、尝试登录Mysql 三、配置Mysql环境变量 一、Mysql57下载与安装 首先&#xff0c;进入Mysql下载官网&#xff1a;MySQL Community Downloads 随后&#xff0c;选择版本5.7.43&#xff0c;系统选择Windows&#xff0c;随后下方会出现两个下载选…
阅读更多...
又双叒叕！五大数据库全方位注释，抗性宏基因组分析项目再次升级！

又双叒叕！五大数据库全方位注释，抗性宏基因组分析项目再次升级！

基于宏基因组测序的抗性基因分析是目前ARGs分析的重要手段&#xff0c;五大数据库全面注释分析&#xff0c;一网打尽ARGs、MRGs、BRGs、MGEs、致病菌注释。 项目报告不仅包含抗性基因的多样性、丰度和分布模式&#xff0c;还能获得包括抗性组变化驱动因素、指示基因识别、抗性组…
阅读更多...
Python爬虫:js逆向调式操作及调式中遇到debugger问题

Python爬虫:js逆向调式操作及调式中遇到debugger问题

Python爬虫:js逆向调式操作及调式中遇到debugger问题 1. 前言2. js逆向调式操作2.1 DOM事件断点2.2 XHR/提取断点(用于请求接口参数加密处理)2.3 请求返回的数据是加密的2.4 hook定位参数 3. 调式中遇到debugger问题3.1 解决方式(一律不在此处暂停)3.2 问题&#xff1a;点击一律…
阅读更多...
最新文章

Copyright @ 2022~2023