Java算法之Gnome 排序

news/2024/9/20 1:57:10/ 标签: 算法, java, 排序算法

简介

Gnome 排序,又称为双向插入排序或鸡尾酒排序,是一种改进的插入排序算法。它在每次迭代中不仅将最小的元素移动到前面,同时也将最大的元素移动到后面。这种排序算法在每次迭代中同时向两个方向进行移动,因此得名。

算法步骤

  1. 从数组的两端开始,向中间进行扫描。
  2. 如果左侧元素大于右侧元素,则交换它们。
  3. 继续向中间移动,重复步骤2,直到两个指针相遇。
java">//gnomeSort 方法接受一个整型数组 arr 作为参数,执行Gnome排序。
//循环直到数组的末尾,如果当前元素大于前一个元素,则交换它们,并将索引i向前移动一位。
//如果当前元素小于或等于前一个元素,则将索引i向后移动一位。
//main 方法中,我们初始化一个数组,然后调用 gnomeSort 方法进行排序,并打印排序后的结果
public class GnomeSort {// Gnome 排序方法public static void gnomeSort(int[] arr) {int n = arr.length;int i = 0;while (i < n) {if (i == 0 || arr[i - 1] <= arr[i]) {// 如果当前元素大于前一个元素,或者这是第一个元素,则向前移动i++;} else {// 否则,交换当前元素和前一个元素int temp = arr[i];arr[i] = arr[i - 1];arr[i - 1] = temp;i--;}}}public static void main(String[] args) {int[] arr = {3, 1, 5, 2, 4};gnomeSort(arr);// 打印排序后的数组for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

优点

  • 视觉直观:Gnome 排序在每次迭代中都可以看到数组的变化,使得排序过程非常直观。
  • 稳定性:Gnome 排序是稳定的排序算法,相等元素的相对位置不会改变。

缺点

  • 效率较低:Gnome 排序的时间复杂度仍然是O(n^2),在最坏情况下与普通插入排序相同。
  • 空间复杂度:虽然空间复杂度为O(1),但由于需要额外的指针操作,实现起来可能比普通插入排序复杂。

时间复杂度和空间复杂度分析

  • 时间复杂度:平均和最坏情况下都是O(n^2)。
  • 空间复杂度:O(1),不需要额外的存储空间。

使用场景

  • 当需要一个直观的排序过程,并且数据量不是非常大时,可以考虑使用Gnome排序。
  • 适用于教学演示,因为它的双向移动特性使得排序过程易于理解

http://www.ppmy.cn/news/1518925.html

相关文章

如何开发针对不平衡分类的成本敏感神经网络 python

如何开发针对不平衡分类的成本敏感神经网络 深度学习神经网络是一类灵活的机器学习算法&#xff0c;可以在各种问题上表现良好。 神经网络使用误差反向传播算法进行训练&#xff0c;该算法涉及计算模型在训练数据集上产生的误差&#xff0c;并根据这些误差的比例更新模型权重…

240831-Qwen2-VL-7B/2B部署测试

A. 运行效果 B. 配置部署 如果可以执行下面就执行下面&#xff1a; pip install githttps://github.com/huggingface/transformers accelerate否则分开执行 git clone https://github.com/huggingface/transformers cd transformers pip install . accelerate随后&#xff0…

k8s-pod 实战一 (创建pod,启动命令,参数,pod故障排除,拉取命令)

1. 创建一个Pod Pod 是 Kubernetes 中最小的部署单元。它可以包含一个或多个容器。下面是一个简单的 YAML 文件,用于创建一个包含 Nginx 容器的 Pod。 示例 YAML 文件 (nginx-pod.yaml) apiVersion: v1 kind: Pod metadata:name: nginx-pod spec:containers:- name: nginx-…

STM32(八):定时器——输入捕获实验

目录 输入捕获模式测频率&#xff1a; 结构图&#xff1a; 步骤&#xff1a; 部分函数详解&#xff1a; 源码&#xff1a; PWMI模式测频率占空比&#xff1a; 结构图&#xff1a; ​编辑 举例说明 源码&#xff1a; 输入捕获模式测频率&#xff1a; 结构图&#xf…

C#中List集合使用Remove方法详解——List使用Remove方法需要注意的坑?

目录 一、基本使用 1、简单类型的例子 2、复杂类型的例子 二、思考 三、深度解析 四、正确的使用方式 1、重写 Equals 和 GetHashCode 2、使用 LINQ 的 FirstOrDefault 方法 五、性能考虑 六、注意事项 总结 在C#中&#xff0c;List<T> 是一个常用的数据结构&…

第四章 Java核心类库 第三节 集合框架

1. 集合框架概述与结构 首先&#xff0c;我们来简单了解一下Java集合框架的概述和结构。 集合框架的定义&#xff1a;Java集合框架是一组用来存储和操作数据集合的接口和类。它提供了一种统一的标准方法来操作不同的数据集合&#xff0c;极大简化了编程任务。 集合框架的结构…

我的电脑/资源管理器里无法显示新硬盘?

前情提要 我新&#xff01;买了一个京东京造的SATA3硬盘&#xff0c;一个绿联的SATA3转USB读取 现在我的电脑里只能显示我本地的C盘和D盘&#xff0c;不能显示这个接入的SATA盘。 系统环境&#xff1a;windows11 问题描述 在我的电脑里&#xff0c;只能看到我原本的C和D&…

互联网平台大模型网络架构设计

字节跳动&#xff1a;大模型网络实践分享 自2019年起&#xff0c;字节跳动公司便开始着手白盒项目。2020年&#xff0c;推出了首款接入交换机——25G型号&#xff0c;随后逐步实现软硬件的自主研发。在当前一代产品中&#xff0c;已经实现了100G接入、25.6T400G互联&#xff0c…

扩展——双向搜索

1. 基本概念 单向搜索&#xff1a;传统的搜索算法&#xff08;如广度优先搜索 BFS、深度优先搜索 DFS&#xff09;通常从起点开始&#xff0c;逐步扩展搜索到目标节点。搜索的时间复杂度与图的大小和结构有关。 双向搜索&#xff1a;双向搜索则同时从起点和终点进行搜索&#…

分享8个Python自动化实战脚本!

1. Python自动化实战脚本 1.1 网络自动化 网络上有丰富的信息资源&#xff0c;Python可以帮我们自动化获取这些信息。 爬虫简介&#xff1a;爬虫是一种自动提取网页信息的程序。Python有许多优秀的爬虫库&#xff0c;如requests和BeautifulSoup。 案例&#xff1a;使用Pytho…

软件测试学习笔记丨静态测试与代码审计 SonarQube

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/32049 一&#xff0c;SonarQube 平台搭建 1.1&#xff0c; 介绍 Sonar 是一个用于代码质量管理的开放平台。通过插件机制&#xff0c;Sonar 可以集成不同的测试工具、代码分析工具&#xff…

Having trouble using OpenAI API

题意&#xff1a;"使用OpenAI API遇到困难" 问题背景&#xff1a; I am having trouble with this code. I want to implement AI using OpenAI API in my React.js project but I cannot seem to get what the issue is. I ask it a question in the search bar in…

大语言模型数据增强与模型蒸馏解决方案

背景 在人工智能和自然语言处理领域&#xff0c;大语言模型通过训练数百亿甚至上千亿参数&#xff0c;实现了出色的文本生成、翻译、总结等任务。然而&#xff0c;这些模型的训练和推理过程需要大量的计算资源&#xff0c;使得它们的实际开发应用成本非常高&#xff1b;其次&a…

线程间数据传递之ThreadLocal、InheritableThreadLocal、TransmittableThreadLocal

线程间数据传递之ThreadLocal、InheritableThreadLocal、TransmittableThreadLocal 1、ThreadLocal介绍 spring 中基于 ThreadLocal 来实现事务。 多线程 访问同一个共享变量的时候容易出现并发问题&#xff0c;ThreadLocal是除了加锁这种同步方式之外的一种保证 规避多线程…

【bug记录7】导入Lottie的json格式动画,获取不到相对路径下的图片

一、问题背景 在vue3项目中&#xff0c;想把Lottie依赖的图片放在其相对路径下&#xff0c;但是发现即使修改其中的u参数&#xff0c;也无法拿到其相对路径中的图片。因为json解析绝对路径&#xff0c;只能将图片放在项目根目录下的public文件夹应急。 二、解决方法 将Lottie…

Lua 代码编码规范

lua代码格式 vscode stylua 插件 配置文件stylua.toml column_width 240 line_endings “Unix” indent_type “Spaces” --使用空格 很重要&#xff0c;保证不同编辑器打开是一样的 indent_width 4 quote_style “AutoPreferDouble” --字符串引号样式双引号 call_paren…

c++关于字符串的练习

提示并输入一个字符串&#xff0c;统计该字符串中字母个数、数字个数、空格个数、其他字符的个数 #include <iostream> #include<string> using namespace std;int main() {string s1;int letter0,digit0,space0,other0;cout<<"请输入一个字符串:"…

ISO C++ 和 GNU C++ 的区别

C 的 ios 标准和 gnu 标准是两种编译器标准或模式&#xff0c;主要由编译器在编译 C 代码时所遵循的规范决定。它们之间的区别主要在于是否包含标准之外的扩展以及对特定功能的支持。 1. ISO C 标准 (-stdc11, -stdc14, -stdc17, 等) 定义: ISO C 标准是由国际标准化组织 (IS…

3D打印透气钢与传统透气钢的差异

透气钢作为一种集金属强度与透气性能于一体的特殊材料&#xff0c;在注塑模具领域扮演着关键角色&#xff0c;通过有效排除模具内困气&#xff0c;显著提升制品成型质量与生产效率。当前&#xff0c;市场上主流的透气钢产品多源自日本、美国&#xff0c;其高昂成本与技术壁垒限…

Java算法之选择排序(Selection Sort)

简介 选择排序是一种简单直观的排序算法&#xff0c;它的工作原理是每次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;然后放到序列的起始位置。通过重复这个过程&#xff0c;直到所有元素都被排序。 算法步骤 在未排序序列中找到最小…