【JAVA入门】Day24 - 排序算法

【JAVA入门】Day24 - 排序算法


文章目录

  • 【JAVA入门】Day24 - 排序算法
    • 一、冒泡排序
    • 二、选择排序
    • 三、插入排序
    • 四、快速排序
      • 4.1 递归
      • 4.2 快速排序


        排序,是把混乱的数据排成从小到大或从大到小。
        排序一共有十种左右,它们是:冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序、堆排序、计数排序、桶排序、基数排序
        在这里,我们着重介绍前四种。

一、冒泡排序

        冒泡排序:相邻的数据两两比较,小的放前面,大的放后面。
        每经过一轮的两两比较,最大的数据一定会被放在最右边。此时只需要对除它之外的剩余元素继续做相同操作即可。第二轮可以比第一轮少循环一次,以此类推。
        如果数组中有 n 个数据,我们总共只需要执行 n-1 轮的代码就可以了。

package SortTest;public class SortDemo1 {public static void main(String[] args) {//BubbleDemo//1.定义数组int[] arr = {2, 4, 5, 3, 1};//2.利用冒泡排序将数组中的数据变成 1 2 3 4 5//注意循环的截止要减一,防止越界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;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

二、选择排序

        选择排序:从0索引开始,拿着每一个索引上的元素,跟后面的元素依次比较,小的放前面,大的放后面,依此类推。
        每一轮循环结束后,最小的数据一定是跑到了左边,那么后面的下一轮循环就可以少循环一次。

package SortTest;public class SortDemo2 {public static void main(String[] args) {//SelectionSort//1.定义数组int[] arr = {2, 4, 5, 3, 1};//2.利用选择排序让数组变成正序//从0索引开始,跟后面的元素一一比较for(int i = 0; i < arr.length - 1; 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;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

三、插入排序

        插入排序:我们将0索引的元素到N索引的元素看作是有序的,把N+1开始的索引的元素到最后一个元素当成是无序的。遍历无序的元素,我们将遍历到的元素插入到有序序列中适当的位置,若遇到相同数据了,插在后面。N的取值范围:0~最大索引。
        每次插入时,我们是从后往前插,分别跟当前索引的数据比大小,比它小,往前继续走,直到找到比当前索引大的情况,插在后面。

package SortTest;public class SortDemo3 {public static void main(String[] args) {//插入排序:我们将0索引的元素到N索引的元素看作是有序的,把N+1开始的索引的元素到最后一个元素当成是无序的。遍历无序的元素,我们将遍历到的元素插入到有序序列中适当的位置,若遇到相同数据了,插在后面。N的取值范围:0~最大索引。int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};//1.找到无序的哪一组数组是从哪个数组开始的int startIndex = -1;for(int i = 0; i < arr.length - 1; i++) {if(arr[i] > arr[i + 1]) {//System.out.println(i); //有序的那一组数据到i索引就结束了,再加一就是无序数据的第一个索引startIndex = i + 1;break;}}//2.遍历从startIndex开始到最后一个元素,得到无序的每一个元素for (int i = startIndex; 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--;}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}

四、快速排序

4.1 递归

        递归指的是方法中调用方法本身的现象。
        递归一定要有出口,否则就会出现内存溢出。
        递归算法可以把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
【练习1】利用递归求1~100之间的和。

package SortTest;public class RecursionDemo {public static void main(String[] args) {//求1~100的和//1~100的和 = 100 + (1~99的和)//1~99的和 = 99 + (1~98的和)//...//1~2的和 = 2 + (1~1的和)//1~1的和 = 1 (递归的出口)System.out.println(getSum(100));}public static int getSum(int number){if(number == 1) {return 1;}return number + getSum(number - 1);}}

【练习2】用递归求5!。
5! = 5 * 4 * 3 * 2 * 1

package SortTest;public class RecursionDemo1 {public static void main(String[] args) {//5! = 5 * 4!//4! = 4 * 3!//3! = 3 * 2!//2! = 2 * 1!//1! = 1System.out.println(getFactorialRecursion(5));}public static int getFactorialRecursion(int number) {if(number == 1) {return 1;}return number * getFactorialRecursion(number - 1);}
}

4.2 快速排序

        第一轮:把0索引的数字作为基准数,确定基准数在数组中正确的位置。比基准数小的全部在左边,比基准数大的全部在右边。
在这里插入图片描述
在这里插入图片描述
        找到 start 和 end 的位置后,交换两个位置上的数据。
在这里插入图片描述
        直到 start 和 end 指向同一个位置时,这个位置就是基准数要存入的位置(基准数归位)。
在这里插入图片描述
        此时就需要把基准数和它们指向的位置交换。
在这里插入图片描述
        此时,6 左侧的数据都比 6 小,6 右侧的数据都比 6 大。

package SortTest;public class SortDemo4 {public static void main(String[] args) {//QuickSortint[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};quickSort(arr, 0, arr.length - 1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}/*参数一:要排序数组的起始数组参数二:要排序数组的起始索引参数三:要排序数组的结束索引*/public static void quickSort(int[] arr, int i , int j) {//定义两个变量记录要查找的范围int start = i;int end = j;//递归出口//start > endif(start > end) {return;}//记录基准数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++;}//把end和start指向的元素进行交换int temp = arr[start];arr[start] = arr[end];arr[end] = temp;//直到start == end,循环结束}//表示已经找到了基准数在数组中应该存入的位置//基准数归位int temp = arr[i];arr[i] = arr[start];arr[start] = temp;//确定基准数左边的范围,重复刚刚所有的事情quickSort(arr, i, start - 1);//确定基准数右边的范围,重复刚刚所有的事情quickSort(arr, end + 1, j);}
}

        在所有排序算法中,快速排序的速度是最快的,被广泛使用。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Ciallo~(∠・ω・ )⌒☆第二十二篇 入门request请求库使用

请求库是用于发送HTTP请求的工具。常见的请求库有requests&#xff0c;它是一个功能强大且易于使用的HTTP库。 使用requests库发送GET请求&#xff1a; import requests url "https://httpbin.org/get"# 携带get请求参数 params {"pn": 10,"size&q…

Android大脑--systemserver进程

用心坚持输出易读、有趣、有深度、高质量、体系化的技术文章&#xff0c;技术文章也可以有温度。 本文摘要 系统native进程的文章就先告一段落了&#xff0c;从这篇文章开始写Java层的文章&#xff0c;本文同样延续自述的方式来介绍systemserver进程&#xff0c;通过本文您将…

8个我平时每天都会看的网站,涵盖办公、娱乐、学习等

分享8个我平时每天都会看的网站&#xff0c;涵盖办公、娱乐、学习等多种类别&#xff0c;试过就知道有多好用&#xff01; 1、MyFreeMP3 tools.liumingye.cn/music/#/ 一个可以免费听歌的平台&#xff0c;不用充会员&#xff0c;里面收录了大多数的国内外知名流行歌手、乐队的…

电脑开机LOGO修改教程_BIOS启动图片替换方法

准备工具&#xff1a;刷BIOS神器和change logo&#xff0c;打包下载地址&#xff1a;https://download.csdn.net/download/baiseled/89374686 一.打开刷BIOS神器&#xff0c;点击备份BIOS&#xff0c;保存到桌面 二.打开change logo&#xff0c;1.点击load image&#xff0c;选…

Linux云计算 |【第二阶段】SECURITY-DAY1

主要内容&#xff1a; 监控基础&#xff08;系统监控命令、监控软件&#xff09;、Zabbix监控服务端部署、Zabbix监控客户端部署、创建监控主机、调用监控模板、自定义key、创建模板、应用集、监控项、绑定模板&#xff1b; 一、监控概述 1&#xff09;监控的目的 ① 实时报…

LED电子看板优化生产线的管理

在当今竞争激烈的制造业领域&#xff0c;企业不断寻求提高生产效率、降低成本和提升产品质量的方法。而 LED 电子看板作为一种先进的管理工具&#xff0c;正逐渐成为优化生产线管理的关键利器。 一、LED电子看板能够清晰地展示生产进度信息 在繁忙的生产线上&#xff0c;工人和…

18105 银行的叫号顺序

### 详细分析 为了模拟银行的叫号过程&#xff0c;我们可以使用优先队列&#xff08;堆&#xff09;来管理客户的服务顺序。优先级越高的客户会先得到服务&#xff0c;同级别的客户按到达时间先后顺序得到服务。如果优先级和到达时间都相同&#xff0c;则按输入顺序服务。 ##…

表达式求值 - 整形提升和截断

文章目录 一、整形提升二、为什么要整形提升&#xff1f;三、截断四、示例1&#xff0c;23① c1 c2② c3 c1 c2 4 一、整形提升 C语言的整形算数运算总是至少以缺省整形类型的精度来进行的。 为了获得这个精度&#xff0c;表达式中的字符类型和短整型操作数在使用之前被转换…

深度学习基础之前馈神经网络

目录 基本结构和工作原理 神经元和权重 激活函数 深度前馈网络 应用场景 优缺点 深度前馈神经网络与卷积神经网络&#xff08;CNN&#xff09;和循环神经网络&#xff08;RNN&#xff09;的具体区别和联系是什么&#xff1f; 具体区别 联系 如何有效解决前馈神经网络…

爬虫案例4——爬取房天下数据

简介&#xff1a;个人学习分享&#xff0c;如有错误&#xff0c;欢迎批评指正 任务&#xff1a;从房天下网中爬取小区名称、地址、价格和联系电话 目标网页地址&#xff1a;https://newhouse.fang.com/house/s/ 一、思路和过程 目标网页具体内容如下&#xff1a; ​​​​ …

成为Python砖家(3): 何时产生字节码 .pyc 文件

好奇&#xff1a;.pyc和 __pycache__是啥&#xff1f; 你是否好奇&#xff0c;在某些 Python 工程中&#xff0c;当执行了 xxx.py脚本后&#xff0c;多出了 __pycache__目录&#xff1f;这个目录下存放的是一些 .pyc结尾的文件。 这些文件&#xff0c;叫做 python bytecode。 …

深度剖析数字媒体产业链的无限潜力与创新生态

在当今信息爆炸的时代&#xff0c;数字媒体产业链正以势不可挡的姿态展现出其令人瞩目的无限潜力与创新生态。 数字媒体的发展潜力简直无可限量。从在线视频的爆发式增长&#xff0c;到虚拟现实和增强现实技术带来的沉浸式体验&#xff0c;再到社交媒体平台上丰富多彩的内容创…

Windows 应用程序加密 - 功能强大、可定制、开源且完全免费

先进而优雅的 Windows 应用程序加密 - 功能强大、可定制、开源且完全免费&#xff01; 项目地址&#xff1a;FadCrypt GitHub 工作原理&#xff1a; 1. 密码创建&#xff1a;设置密码后&#xff0c;密码会与锁定应用程序的配置文件一起加密保存。监控期间&#xff0c;这些文…

望繁信科技入选2024年第3批上海市高新技术成果转化项目名单

近日&#xff0c;上海望繁信科技有限公司&#xff08;以下简称“望繁信科技”&#xff09;凭借其自主研发的“数字北极星流程挖掘分析软件”项目&#xff0c;成功入选2024年第3批上海市高新技术成果转化项目名单。这一殊荣根据《上海市高新技术成果转化项目认定办法》&#xff…

linux 中docker git 容器磁盘占满如何解决

1.问题描述 git之前还使用ok&#xff0c;突然出现访问500 错误&#xff0c;懵圈了 2.问题排查 1. 服务器查看&#xff0c;服务正常&#xff0c;没有异常出现。 2. 查找资料&#xff0c;需要查看是否磁盘已经满了果然使用df-h 后显示磁盘已经满了&#xff0c;且容器和本地都…

WPF篇(20)- Menu菜单+ContextMenu上下文菜单+StatusBar状态栏

Menu菜单 Menu控件继承于MenuBase&#xff0c;而MenuBase继承于ItemsControl。所以学习Menu之前&#xff0c;要先了解一下MenuBase基类。它是一个抽象类&#xff0c;拥有一个ItemContainerTemplateSelector模板选择器&#xff0c;并重写了一些关于键盘和鼠标的方法。 Menu的子…

电脑监控怎样看回放视频?一键解锁电脑监控回放,守护安全不留死角!高效员工电脑监控,回放视频随时查!

你是否曾好奇那些键盘敲击背后的秘密&#xff1f;电脑监控不仅是守护企业安全的隐形盾牌&#xff0c;更是揭秘高效与合规的魔法镜&#xff01;一键解锁安企神监控回放&#xff0c;就像打开时间宝盒&#xff0c;让过去的工作瞬间跃然眼前。无论是精彩瞬间还是潜在风险&#xff0…

【Android】adb devices 出现devices offline的问题

1 问题 adb devices 出现devices offline 2 解决方法 adb kill-serveradb start-server 然后&#xff0c;adb devices查看。 adb devices 问题解决啦。。。&#x1f49b; &#x1f499; &#x1f49c; ❤️ &#x1f49a; &#x1f49b; &#x1f499; &#x1f49c; ❤️…

12/24/30v/36转固定5v输出芯片

设计电源芯片的应用方案时&#xff0c;必须保证输入电压在DC6V至30V范围内&#xff0c;输出电压为固定的5V&#xff0c;同时电流需在200至300mA之间。在这种需求下&#xff0c;推荐使用AH1405芯片&#xff0c;因其输入电压范围宽&#xff08;6-40V&#xff09;&#xff0c;内置…

自闭症寄宿语言开发全托学校

在自闭症儿童的世界里&#xff0c;语言往往是一座难以跨越的高山。语言问题作为自闭症儿童的核心障碍之一&#xff0c;给他们的生活、学习和社交带来了极大的困扰。因此&#xff0c;语言开发对于自闭症儿童来说至关重要。那么&#xff0c;怎样才能更好地对自闭症儿童进行语言开…