Java快速排序希尔排序归并排序

快速排序算法

在这里插入图片描述

快速排序的原理:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。

一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。

public void sort(int[] a, int low, int high) {int start = low;int end = high;int key = a[low];while (end > start) {//从后往前比较while (end > start && a[end] >= key)//如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较end--;if (a[end] <= key) {int temp = a[end];a[end] = a[start];a[start] = temp;}//从前往后比较while (end > start && a[start] <= key)//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置start++;if (a[start] >= key) {int temp = a[start];a[start] = a[end];a[end] = temp;}//此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用}//递归if (start > low) sort(a, low, start - 1);//左边序列。第一个索引位置到关键值索引-1if (end < high) sort(a, end + 1, high);//右边序列。从关键值索引+1 到最后一个}}
希尔排序算法

基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

  1. 操作方法:选择一个增量序列 t1,t2,…,tk,其中 ti>tj,tk=1;

  2. 按增量序列个数 k,对序列进行 k 趟排序;

  3. 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

在这里插入图片描述

private void shellSort(int[] a) {int dk = a.length / 2;while (dk >= 1) {ShellInsertSort(a, dk);dk = dk / 2;}}private void ShellInsertSort(int[] a, int dk) {//类似插入排序,只是插入排序增量是 1,这里增量是 dk,把 1 换成 dk 就可以了for (int i = dk; i < a.length; i++) {if (a[i] < a[i - dk]) {int j;int x = a[i];//x 为待插入元素a[i] = a[i - dk];for (j = i - dk; j >= 0 && x < a[j]; j = j - dk) {//通过循环,逐个后移一位找到要插入的位置。a[j + dk] = a[j];}a[j + dk] = x;//插入}}}
归并排序算法

image-20240107110801218

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

public class MergeSortTest {public static void main(String[] args) {int[] data = new int[]{5, 3, 6, 2, 1, 9, 4, 8, 7};print(data);mergeSort(data);System.out.println("排序后的数组:");print(data);}public static void mergeSort(int[] data) {sort(data, 0, data.length - 1);}public static void sort(int[] data, int left, int right) {if (left >= right)return;// 找出中间索引 int center = (left + right) / 2;// 对左边数组进行递归 sort(data, left, center);// 对右边数组进行递归 sort(data, center + 1, right);// 合并 merge(data, left, center, right);print(data);}/*** \* 将两个数组进行归并,归并前面 2 个数组已有序,归并后依然有序* <p>* \** <p>* \* @param data* <p>* \* 数组对象* <p>* \* @param left* <p>* \* 左数组的第一个元素的索引* <p>* \* @param center* <p>* \* 左数组的最后一个元素的索引,center+1 是右数组第一个元素的索引* <p>* \* @param right* <p>* \* 右数组最后一个元素的索引*/public static void merge(int[] data, int left, int center, int right) {// 临时数组 int[] tmpArr = new int[data.length];// 右数组第一个元素索引 int mid = center + 1;// third 记录临时数组的索引 int third = left;// 缓存左数组第一个元素的索引 int tmp = left;while (left <= center && mid <= right) {// 从两个数组中取出最小的放入临时数组 if (data[left] <= data[mid]) {tmpArr[third++] = data[left++];} else {tmpArr[third++] = data[mid++];}}// 剩余部分依次放入临时数组(实际上两个 while 只会执行其中一个) while (mid <= right) {tmpArr[third++] = data[mid++];}while (left <= center) {tmpArr[third++] = data[left++];}// 将临时数组中的内容拷贝回原数组中 // (原 left-right 范围的内容被复制回原数组) while (tmp <= right) {data[tmp] = tmpArr[tmp++];}}public static void print(int[] data) {for (int i = 0; i < data.length; i++) {System.out.print(data[i] + "\t");}System.out.println();}}

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

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

相关文章

基于Python实现身份证信息识别

目录 前言身份证信息识别的背景与意义自动识别身份证的需求 实现环境与工具准备Python编程语言OpenCV图像处理库Tesseract OCR引擎 身份证信息识别算法原理图像预处理步骤(图像裁剪、灰度化 、二值化、去噪)信息提取与解析 Python代码实现通过OCR提取身份证号码代码解析身份证信…

【QML COOK】- 008-自定义属性

前面介绍了用C定义QML类型&#xff0c;通常在使用Qt Quick开发项目时&#xff0c;C定义后端数据类型&#xff0c;前端则完全使用QML实现。而QML类型或Qt Quick中的类型时不免需要为对象增加一些属性&#xff0c;本篇就来介绍如何自定义属性。 1. 创建项目&#xff0c;并编辑Ma…

【Linux驱动】Linux的中断系统 | 中断的重要数据结构

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux驱动》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f3c0;Linux系统的中断⚽中断分类软中断和硬中断中断的上半部和下半部 ⚽tasklet⚽工…

基于uniapp封装的card容器 带左右侧两侧标题内容区域

代码 <template><view class"card"><div class"x_flex_header"><div><title v-if"title ! " class"title" :title"title" :num"num"></title></div><div><s…

系列四、Spring Security认证 授权(前后端不分离)

一、Spring Security认证 & 授权&#xff08;前后端不分离&#xff09; 1.1、MyWebSecurityConfigurerAdapter /*** Author : 一叶浮萍归大海* Date: 2024/1/11 21:50* Description:*/ Configuration public class MyWebSecurityConfigurerAdapter extends WebSecurityCo…

关注个人数据保护,肯尼亚发布新指南

近日&#xff0c;肯尼亚数据保护专员办公室&#xff08;ODPC&#xff09;发布了新的指导文件&#xff0c;旨在加强教育、通讯和数字信贷领域的数据保护措施&#xff0c;并提供了一个处理健康数据的通用指南。 这些指导意见是基于《数据保护法》&#xff08;DPA&#xff09;制定…

Appium 自动化测试

1.Appium介绍 1&#xff0c;appium是开源的移动端自动化测试框架&#xff1b; 2&#xff0c;appium可以测试原生的、混合的、以及移动端的web项目&#xff1b; 3&#xff0c;appium可以测试ios&#xff0c;android应用&#xff08;当然了&#xff0c;还有firefoxos&#xff09;…

《YOLO算法:基础+进阶+改进》报错解决 专栏答疑

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。《YOLO算法&#xff1a;基础进阶改进》专栏上线后&#xff0c;部分同学在学习过程中提出了一些问题&#xff0c;笔者相信这些问题其他同学也有可能遇到。为了让大家可以更好地学习本专栏内容&#xff0c;笔者特意推出了该篇…

canvas绘制流动的蚂蚁线(图文示例)

查看专栏目录 canvas示例教程100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…

汽配企业MES管理系统的特点与实践

随着汽车工业的飞速发展&#xff0c;汽车零部件制造企业面临着日益复杂的生产环境和多样化的市场需求。为了应对这些挑战&#xff0c;许多汽配企业开始引入MES管理系统解决方案&#xff0c;以提高生产效率、优化资源配置、提升产品质量。本文将重点探讨汽配企业MES管理系统的特…

Netty 介绍、使用场景及案例

Netty 介绍、使用场景及案例 1、Netty 介绍 https://github.com/netty/netty Netty是一个高性能、异步事件驱动的网络应用程序框架&#xff0c;用于快速开发可扩展的网络服务器和客户端。它是一个开源项目&#xff0c;最初由JBoss公司开发&#xff0c;现在由社区维护。Netty的…

k8s--集群调度(kube-scheduler)

了解kube-scheduler 由之前博客可知kube-scheduler是k8s中master的核心组件之一 scheduler&#xff1a;负责调度资源。把pod调度到node节点。他有两种策略&#xff1a; 预算策略&#xff1a;人为部署&#xff0c;指定node节点去部署新建的pod 优先策略&#xff1a;通过算法选…

怎么做微信秒活动_掀起购物狂潮,引爆品牌影响力

微信秒杀活动&#xff1a;掀起购物狂潮&#xff0c;引爆品牌影响力 在数字化时代&#xff0c;微信已经成为人们日常生活中不可或缺的一部分。作为中国最大的社交媒体平台&#xff0c;微信不仅为人们提供了便捷的通讯方式&#xff0c;还为商家提供了一个广阔的营销舞台。其中&a…

vue3的福音框架arco.design

前言&#xff1a; 在vue2于2023年底正式宣布不在维护&#xff0c;vue3使用越来越频繁的时刻&#xff0c;我们实现项目的辅助框架也越来越多。element, iview, antd 等经典框架继续风靡一时&#xff0c;不过也有很多好的框架&#xff0c;功能也强大&#xff0c;比如我们今天说的…

2.【CPP】入门(宏||内联函数||拷贝构造||析构函数||构造函数)

0x01.引言 1.实现一个宏函数ADD #define ADD(x,y) ((x)(y))//宏是预编译阶段完成替换&#xff0c;注意括号2.宏的优缺点 优点&#xff1a; 1.增强代码的复用性 2.宏函数不用建立栈帧&#xff0c;提高性能 缺点&#xff1a; 1.不方便调试 2.没有安全检查 0x02.内联函数 1.以空…

什么是冒泡排序?如何实现?

一、是什么 冒泡排序&#xff08;Bubble Sort&#xff09;&#xff0c;是一种计算机科学领域的较简单的排序算法 冒泡排序的思想就是在每次遍历一遍未排序的数列之后&#xff0c;将一个数据元素浮上去&#xff08;也就是排好了一个数据&#xff09; 如同碳酸饮料中二氧化碳的…

摄像头视频录制程序使用教程(Win10)

摄像头视频录制程序-Win10 &#x1f957;介绍&#x1f35b;使用说明&#x1f6a9;config.json 说明&#x1f6a9;启动&#x1f6a9;关闭&#x1f6a9;什么时候开始录制&#xff1f;&#x1f6a9;什么时候触发录制&#xff1f;&#x1f6a9;调参 &#x1f957;介绍 检测画面变化…

“数据要素×”行动计划发布,粮食安全监管如何应变?

近日&#xff0c;国家数据局发布“数据要素”三年行动计划&#xff08;2024-2026年&#xff09;&#xff0c;在“数据要素现代农业“部分提到&#xff1a;提升农业综合生产能力&#xff0c;支持农业生产经营主体和相关服务企业融合利用气象、土壤、农事作业、病虫害、市场等数据…

FineBI实战项目一(17):热门商品Top10分析开发

点击新建组件&#xff0c;创建热门商品Top10组件。 选择柱状图&#xff0c;拖拽cnt&#xff08;总数&#xff09;到横轴&#xff0c;拖拽goodName到纵轴。 选择排序规则。 修改横轴和纵轴的标签名称 切换到仪表板&#xff0c;拖拽组件到仪表板 效果如下&#xff1a;

别再纠结,这8款设计工具助你轻松绘制原型图!

原型图设计工具有很多优点。除了帮助设计师快速与客户达成协议&#xff0c;避免项目前景的冲突外&#xff0c;原型图设计工具还可以让客户看到正在创建的内容。如果需要更改&#xff0c;原型图设计工具也可以轻松完成。本文快速总结了8种原型图设计工具。无论你是专业设计师还是…