Java的六大排序

一、冒泡排序（Bubble Sort）

1. 基本思想：
  • 比较相邻的元素。如果第一个比第二个大（升序情况，降序则相反），就交换它们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样在经过一轮比较后，最大的元素就会 “浮” 到数组的末尾。
  • 针对所有的元素重复以上的步骤，除了已经排序好的最后一个元素（因为它已经是最大的了），直到整个数组都有序。
2. 示例代码：
public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;// 外层循环控制排序轮数，一共需要n - 1轮for (int i = 0; i < n - 1; i++) {// 内层循环控制每一轮比较的次数，每一轮比较次数逐渐减少for (int j = 0; j < n - 1 - i; j++) {// 如果当前元素大于下一个元素，则交换它们的位置if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j + 1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);// 输出排序后的数组for (int num : arr) {System.out.print(num + " ");}}
}
3. 注释说明：

  • 外层循环的i从0到n - 1，每一轮确定一个最大的数放到数组末尾，所以一共需要n - 1轮排序。

  • 内层循环的j从0到n - i - 1，因为每一轮排序后，末尾已经排好序的元素就不需要再参与比较了，所以每一轮比较次数逐渐减少。

  • 当arr[j] > arr[j + 1]时，通过临时变量temp交换两个元素的位置，实现将较大的数往后 “冒泡”。

二、选择排序（Selection Sort）

1. 基本思想：

  • 首先在未排序序列中找到最小（升序情况，降序则找最大）的元素，存放到排序序列的起始位置。

  • 然后，再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。

  • 重复以上步骤，直到所有元素均排序完毕。

2. 示例代码：
public class SelectionSort {public static void selectionSort(int[] arr) {int n = arr.length;// 外层循环控制选择的轮数，一共需要n - 1轮for (int i = 0; i < n - 1; i++) {int minIdx = i;// 内层循环用于找到当前未排序部分的最小值的索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIdx]) {minIdx = j;}}// 如果找到的最小值索引不是当前轮的起始索引，就交换这两个位置的元素int temp = arr[minIdx];arr[minIdx] = arr[i];arr[i] = temp;}}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};selectionSort(arr);for (int num : arr) {System.out.print(num + " ");}}
}
3. 注释说明：

  • 外层循环同样控制排序轮数，i从0到n - 1，每一轮确定一个最小的数放到数组开头（已排序部分的末尾），所以需要n - 1轮。

  • 内层循环从i + 1到n，用于在当前未排序部分找到最小值的索引minIndex。

  • 如果minIndex不等于当前轮的起始索引i，则通过临时变量temp交换这两个位置的元素，将最小值放到正确的位置

三、插入排序（Insertion Sort）

1. 基本思想：

  • 把待排序的元素插入到已经排序好的部分序列中的合适位置，使得插入后的序列仍然有序。

  • 从第二个元素开始，将其与前面已排序的元素依次比较，找到合适的插入位置并插入。

2. 示例代码：
public class InsertionSort {public static void insertionSort(int[] arr) {int n = arr.length;// 从第二个元素开始，将其插入到已排序部分的合适位置for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;// 在已排序部分中查找插入位置，将大于key的元素往后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}// 将key插入到合适的位置arr[j + 1] = key;}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};insertionSort(arr);for (int num : arr) {System.out.print(num + " ");}}
}
3. 注释说明：

  • 外层循环从第二个元素（索引为1）开始，因为第一个元素默认是已排序的。

  • 对于每一个要插入的元素key（即arr[i]），内层循环while从已排序部分的末尾（i - 1）开始往前找插入位置，只要当前元素arr[j]大于key，就将arr[j]往后移一位（arr[j + 1] = arr[j]），同时j减1。

  • 当找到合适的插入位置（arr[j] <= key或者j < 0）时，将key插入到j + 1的位置（arr[j + 1] = key）。

四、希尔排序（Shell Sort）

1. 基本思想：

  • 希尔排序是插入排序的一种改进版本。它先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序。

  • 分割子序列的方法是按照一定的间隔（称为增量）来选取元素，增量会逐渐减小，直到最后一次排序时增量为 1。

2. 示例代码：
public class ShellSort {public static void shellSort(int[] arr) {int n = arr.length;// 初始步长，一般取数组长度的一半int gap = n / 2;while (gap > 0) {// 对每个步长进行插入排序for (int i = gap; i < n; i++) {int key = arr[i];int j = i - gap;while (j >= 0 && arr[j] > key) {arr[j + gap] = arr[j];j -= gap;}arr[j + gap] = key;}// 缩小步长，一般取上一轮步长的一半gap = gap / 2;}}public static void main(String[] args) {int[] arr = {15, 74, 53, 42, 91};shellSort(arr);for (int num : arr) {System.out.print(num + " ");}}
}
3. 注释说明：

  • 首先确定初始步长gap，一般取数组长度的一半。然后通过循环，每次对步长为gap的子序列进行插入排序。

  • 在对步长为gap的子序列进行插入排序时，原理和普通插入排序类似，只是比较和移动元素的间隔是gap。

  • 每完成一轮步长为gap的插入排序后，将步长缩小为上一轮步长的一半，继续下一轮排序，直到步长为0为止。

五、快速排序（Quick Sort）

1. 基本思想：

  • 选择一个基准元素，通常选择数组的第一个元素（也可以选择其他元素）。

  • 通过一趟排序将待排序的数据分割成两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大。

  • 然后对这两部分数据分别进行快速排序，直到整个数组有序

2. 示例代码：
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 划分操作，获取分区点索引int pi = partition(arr, low, high);// 对分区点左边的子数组进行快速排序quickSort(arr, low, pi - 1);// 对分区点右边的子数组进行快速排序quickSort(arr, pi + 1, high);}}public static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换arr[i]和arr[j]的位置int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交换arr[i + 1]和arr[high]的位置，将分区点放到正确位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}public static void main(String[] args) {int[] arr = {10, 79, 48, 29, 91, 53};quickSort(arr, 0, arr.length - 1);for (int num : arr) {System.out.print(num + " ");}}
}
3. 注释说明：

  • quickSort方法是快速排序的主方法，通过递归调用对数组进行排序。首先判断low是否小于high，如果是，则进行划分操作找到分区点pivotIndex，然后分别对分区点左右两边的子数组进行快速排序。

  • partition方法用于实现划分操作。选择数组的最后一个元素pivot作为分区点，通过循环比较将小于等于pivot的元素放到左边，大于pivot的元素放到右边，最后将分区点放到正确的位置并返回其索引。

六、归并排序（Merge Sort）

1. 基本思想：

  • 采用分治策略，将待排序序列分成两部分，分别对这两部分进行排序，然后将排序好的两部分合并成一个有序序列。

  • 不断重复这个过程，直到整个序列都有序

2. 示例代码：
public class MergeSort {public static void mergeSort(int[] arr, int low, int high) {if (low < high) {int mid = (low + high) / 2;// 对左半部分数组进行归并排序mergeSort(arr, low, mid);// 对右半部分数组进行归并排序mergeSort(arr, mid + 1, high);// 合并左右两部分已排序的数组merge(arr, low, mid, high);}}private static void merge(int[] arr, int low, int mid, int high) {// 分别创建左右两个临时数组来存储左右两部分已排序的数组int[] leftArray = new int[mid - low + 1];int[] rightArray = new int[high - mid];// 将原数组的左半部分复制到leftArrayfor (int i = 0; i < mid - low + 1; i++) {leftArray[i] = arr[low + i];}// 将原数组的右半部分复制到rightArrayfor (int i = 0; i < high - mid; i++) {rightArray[i] = arr[mid + 1 + i];}int i = 0;int j = 0;int k = low;// 比较左右两个临时数组的元素，将较小的元素依次放回原数组while (i < leftArray.length && j < rightArray.length) {if (leftArray[i] <= rightArray[j]) {arr[k] = leftArray[i];i++;} else {arr[k] = rightArray[j];j++;}k++;}// 将leftArray中剩余的元素放回原数组while (i < leftArray.length) {arr[k] = leftArray[i];k++;i++;}// 将rightArray中剩余的元素放回原数组while (j < rightArray.joinsort>arr[k] = rightArray[j];k++;j++;}}public static void main(String[] args) {int[] arr = {85, 43, 39, 92, 61};mergeSort(arr, 0, arr.length - 1);// 输出排序后的数组for (int num : arr) {System.out.print(num + " ");}}
}
3. 注释说明：

  • mergeSort方法通过递归调用对数组进行排序。首先判断low是否小于high，如果是，则将数组分成左右两部分，分别对左右两部分进行归并排序，然后再将两部分已排序的数组合并。

  • merge方法用于实现合并操作。先创建左右两个临时数组来存储左右两部分已排序的数组，然后通过比较将较小的元素依次放回原数组，最后将剩余的元素也放回原数组。

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

永久免费！星火大模型接口源码分享（支持上下文、连续对话和历史对话保存）

永久免费！星火大模型接口源码分享（支持上下文、连续对话和历史对话保存）

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 星火大模型 📒🌟 接口功能📜 源码分享🎯 使用方法⚓️ 相关链接 ⚓️📖 介绍 📖 你是否在寻找一款国产的、永久免费的大模型接口？想要在自己的项目中轻松集成强大的自然语言处理能力？今天，将为你分享一份免费的星…
阅读更多...
小型内衣洗衣机哪个牌子好？五大超值优等品速来围观！

小型内衣洗衣机哪个牌子好？五大超值优等品速来围观！

小型洗衣机的存在无疑是懒人的福音&#xff0c;它帮助了许多忙碌的人们解决了洗衣烦恼。尤其对于年龄较小的婴幼儿需要勤换衣、洗衣的时候&#xff0c;它的功能就显得尤为重要了&#xff0c;同时还能够用于清洗大人的内衣裤、袜子这一系列的贴身衣物。小型洗衣机通常用于宿舍、…
阅读更多...
取代产品岗，又一新兴岗位在崛起！这才是产品经理未来5年最好的就业方向！

取代产品岗，又一新兴岗位在崛起！这才是产品经理未来5年最好的就业方向！

这是我入行产品经理的第1007天&#xff1a; 每天都是整理需求、开会、写文档、协调资源 被开发、运营diss一通&#xff0c;顺便为产品“背个锅” 熬夜加班做出来的产品&#xff0c;业务团队还是不愿意用…… 更让人头秃的是&#xff0c;干了3年&#xff0c;好像到了“职…
阅读更多...
打造自己的RAG解析大模型：(可商用)智能文档服务上线部署

打造自己的RAG解析大模型：(可商用)智能文档服务上线部署

通用版面分析介绍 版面解析是一种将文档图像转化为机器可读数据格式的技术&#xff0c;广泛应用于文档管理和信息提取等领域。通过结合OCR、图像处理和机器学习&#xff0c;版面解析能够识别文档中的文本块、图片、表格等版面元素&#xff0c;最终生成结构化数据&#xff0c;大…
阅读更多...
Spring

Spring

1、Spring框架中单例bean是线程安全的吗&#xff1f; 不是线程安全的。当多用户同时请求一个服务时&#xff0c;容器会给每个请求分配一个线程&#xff0c;这些线程会并发执行业务逻辑。如果处理逻辑中包含对单例状态的修改&#xff0c;比如修改单例的成员属性&#xff0c;就必…
阅读更多...
MathGPT的原理介绍，在中小学数学教学的应用场景，以及代码样例实现

MathGPT的原理介绍，在中小学数学教学的应用场景，以及代码样例实现

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下MathGPT的原理介绍&#xff0c;在中小学数学教学的应用场景&#xff0c;以及代码样例实现。MathGPT的核心架构是一个精心设计的多层次系统&#xff0c;旨在有效处理复杂的数学问题。其主要组成部分包括 数学知识图谱…
阅读更多...
【Linux】man 手册的使用指南

【Linux】man 手册的使用指南

man 手册的使用指南 man手册中文版上传至资源&#xff08;用心整理&#xff0c;感谢理解&#xff01;&#xff09; man手册官方下载链接&#xff1a;https://mirrors.edge.kernel.org/pub/linux/docs/man-pages/ man 手册页&#xff1a;https://linux.die.net/man/ Linux man…
阅读更多...
机器学习分析scRNA-seq解析急性髓系白血病中的疾病和免疫过程

机器学习分析scRNA-seq解析急性髓系白血病中的疾病和免疫过程

急性髓性白血病&#xff08;AML&#xff0c;Acute myeloid leukemia&#xff09;是一种存在于复杂微环境中的疾病。作者基于scRNA-seq分析了来自40例骨髓抽吸donor的38,410个细胞&#xff0c;包括16例AML患者和5例健康donor。然后&#xff0c;应用机器学习分类器来区分恶性细胞…
阅读更多...
【缓存策略】你知道 Write Back（回写）这个缓存策略吗？

【缓存策略】你知道 Write Back（回写）这个缓存策略吗？

&#x1f449;博主介绍&#xff1a; 博主从事应用安全和大数据领域&#xff0c;有8年研发经验&#xff0c;5年面试官经验&#xff0c;Java技术专家&#xff0c;WEB架构师&#xff0c;阿里云专家博主&#xff0c;华为云云享专家&#xff0c;51CTO 专家博主 ⛪️ 个人社区&#x…
阅读更多...
1小时构建Vue3知识体系-Vue的响应式，让数据动起来

1小时构建Vue3知识体系-Vue的响应式，让数据动起来

本文转载自&#xff1a;https://fangcaicoding.cn/course/12/62 大家好&#xff01;我是方才&#xff0c;目前是8人后端研发团队的负责人&#xff0c;拥有6年后端经验&3年团队管理经验。 系统学习践行者&#xff01;近期在系统化输出前端入门相关技术文章&#xff0c;期望能…
阅读更多...
Docker网络详解

Docker网络详解

安装Docker时&#xff0c;它会自动创建三个网络&#xff0c;bridge&#xff08;创建容器默认连接到此网络&#xff09;、 none 、host 网络模式简介Host容器将不会虚拟出自己的网卡&#xff0c;配置自己的IP等&#xff0c;而是使用宿主机的IP和端口。Bridge此模式会为每一个容…
阅读更多...
宝塔面板部署前端项目（包含ssl证书部署）

宝塔面板部署前端项目（包含ssl证书部署）

环境&#xff1a; ①nginx&#xff08;这里使用的版本为1.21.41&#xff09; ②前端项目文件&#xff08;以根目录打包的文件&#xff09; ③域名 ④SLL数字证书的key文件和.pem文件&#xff08;我们这里用的是nginx部署&#xff0c;因此下载证书的时候&#xff0c;下载nginx对…
阅读更多...
【区别】ONLYOFFICE心得体会，8.2与8.1区别

【区别】ONLYOFFICE心得体会，8.2与8.1区别

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》&#xff1a;python零基础入门学习 《python运维脚本》&#xff1a; python运维脚本实践 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8…
阅读更多...
Equity-Transformer：求解NP-Hard Min-Max路由问题的顺序生成算法（AAAI-24)(未完)

Equity-Transformer：求解NP-Hard Min-Max路由问题的顺序生成算法（AAAI-24)(未完)

文章目录 AbstractIntroduction问题表述MethodologyAbstract 最小最大路由问题旨在通过智能体合作完成任务来最小化多个智能体中最长行程的长度。这些问题包括对现实世界有重大影响的应用场景，但已知属于NP-hard问题。现有方法在大规模问题上面临挑战，尤其是在需要协调大量智…
阅读更多...
ScrumMaster认证机构及CSM、PSM、RSM价值解析

ScrumMaster认证机构及CSM、PSM、RSM价值解析

近十年Scrum在国内备受关注&#xff0c;成为一种最流行的现代敏捷工作方式。ScrumMaster这一独特的角色&#xff0c;在企业内部推动Scrum落地的过程中越来越重要。各种ScrumMaster认证课程也蜂拥而至&#xff0c;甚至鱼目混珠。 我们为大家梳理了目前市面上出现的ScrumMaster认…
阅读更多...
HLS实现图像二值化

HLS实现图像二值化

最近在学习HLS语言&#xff0c;所以就自己摸索尝试了用HLS实现了图像二值化&#xff0c;把这个内容总结一下&#xff0c;分享出来。 首先打开HLS&#xff0c;然后新建一个Project&#xff0c;之后再在Source栏点击右键&#xff0c;选择New File...&#xff0c;创建名为pixelBi…
阅读更多...
[ 内网渗透实战篇-1 ] 单域环境搭建与安装域环境判断域控定位CS插件装载CS上线

[ 内网渗透实战篇-1 ] 单域环境搭建与安装域环境判断域控定位CS插件装载CS上线

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…
阅读更多...
通过物流分拣系统来理解RabbitMQ的消息机制

通过物流分拣系统来理解RabbitMQ的消息机制

RabbitMQ作为一个消息中间件&#xff0c;通过队列和路由机制&#xff0c;帮助应用程序高效传递消息。而它的消息流转过程&#xff0c;其实可以用物流分拣系统来直观理解。 在一个典型的物流分拣系统中&#xff0c;包裹会经过多个节点&#xff08;比如分拣中心、配送站&#xf…
阅读更多...
别再乱搜了 这 5个宝藏AE模板网站，小白也能做出大片级动画

别再乱搜了 这 5个宝藏AE模板网站，小白也能做出大片级动画

Hello&#xff0c;大家好&#xff0c;我是后期圈&#xff01; 今天来聊聊一个后期人都绕不开的话题&#xff1a;AE模板网站&#xff01;模板可是后期人的福音&#xff0c;无论你是想要惊艳的开场动画&#xff0c;酷炫的转场效果&#xff0c;还是个性化的文字特效&#xff0c;一…
阅读更多...
CSS 编写位置详解及优先级分析

CSS 编写位置详解及优先级分析

在前端开发中，CSS 的编写位置对项目的组织结构和维护性至关重要。不同的编写位置不仅影响代码的可读性和复用性，还决定了样式应用的优先级。 本文将根据编写位置的不同，详细介绍其定义、使用场景和优先级。 行内样式（Inline Styles） 行内样式（又称：内联样式）是将 CS…
阅读更多...
最新文章

Copyright @ 2022~2023