当前位置: 首页 > news >正文

归并排序,自顶向下

归并排序主要两步,一步是划分区间,另一步是合并两个区间

这个算法的稳定性更好,对比快排这种,如果整体是倒序的话,快排的复杂度会达到o(n^2),归并会更稳定。

划分区间主要是递归去实现,下面给出代码

package com.codeking.sortTest;/*** @author xiongjl* @since 2023/10/31  13:19*/
public class sortTest {public static void main(String[] args) {int[] arr = {1, 2, 5, 4, 9, 8, 7};mergeSort(arr, new int[arr.length], 0, arr.length - 1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]);}}// 归并排序static void mergeSort(int[] arr, int[] temp, int left, int right) {// 如果left和right相等,说明只有以一个元素if (left < right) {int mid = left + (right - left) / 2;// 处理左右区间mergeSort(arr, temp, left, mid);mergeSort(arr, temp, mid + 1, right);// 合并区间merge(arr, temp, left, mid, right);}}// 合并有序数组 [5,4,2,6]static void merge(int[] arr, int[] temp, int left, int mid, int right) {int leftPos = left, rightPos = mid + 1, pos = left;// 两边都有元素while (leftPos <= mid && rightPos <= right) {if (arr[leftPos] < arr[rightPos]) {temp[pos++] = arr[leftPos++];} else {temp[pos++] = arr[rightPos++];}}// 处理剩下的元素while (leftPos <= mid) {temp[pos++] = arr[leftPos++];}while (rightPos <= right) {temp[pos++] = arr[rightPos++];}// 覆盖原数组while (left <= right) {arr[left] = temp[left];left++;}}
}

有一个讲排序算法挺不错的up主,可以看看:排序算法:归并排序【图解+代码】_哔哩哔哩_bilibili

http://www.lryc.cn/news/214501.html

相关文章:

  • 【案例】3D地球(vue+three.js)
  • C语言中float byte char uint_8 转换方法
  • 瑞明达:脚踏实地,为实体经济贡献“瑞明达”力量
  • ChatGPT-自然语言处理模型
  • Apache Dolphinscheduler如何不重启解决Master服务死循环
  • 绝对好用!一个浏览器插件解决跨设备同步问题,吊打文件传输助手!
  • 阿昌教你如何优雅的数据脱敏
  • 力扣每日一题80:删除有序数组中的重复项||
  • SQL——插入已经存在的数据
  • 【网络安全 --- 任意文件上传漏洞靶场闯关 6-15关】任意文件上传漏洞靶场闯关,让你更深入了解文件上传漏洞以及绕过方式方法,思路技巧
  • 阿里云2核2G3M云服务器99元/年,新老同享,续费不涨价!
  • UWB 技术在机器人和移动领域的应用题】
  • 11.1 知识总结(JavaScript)
  • 【Java 进阶篇】Java Web开发:实现验证码功能
  • C++启动线程的方法
  • Distilling the Knowledge in a Neural Network学习笔记
  • JVM虚拟机:垃圾回收算法和垃圾回收器之间的关系
  • oracle sqlplus的使用 ,查询oracle实例名和服务名,查询oracle容器,切换oracle容器
  • golang工程——opentelemetry简介、架构、概念、追踪原理
  • Python 自动化(十六)静态文件处理
  • C#学习系列之密闭类、接口、结构和类
  • C++特殊类的设计
  • 量化交易Copula建模应对市场低迷
  • 美创科技位居IDC MarketScape:中国数据安全管理平台市场「领导者」类别
  • Go语言变量的使用
  • 在vitis中bit位赋值如何优化到一拍完成
  • 深度学习入门(二)之 简单手写数字识别实现
  • USART HMI串口屏+单片机通讯上手体验
  • Linux进程概念(1)
  • uniapp 查看安卓第三方插件抛出的异常