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

排序算法之梳排序


title: 梳排序
date: 2024-7-30 14:46:27 +0800
categories:

  • 排序算法
    tags:
  • 排序
  • 算法
  • 梳排序
    description: 梳排序(Comb Sort)是一种由弗拉基米尔·多博舍维奇(Wlodzimierz Dobosiewicz)于1980年所发明的不稳定排序算法,并由史蒂芬·莱西(Stephen Lacey)和理查德·博克斯(Richard Box)于1991年四月号的Byte杂志中推广。梳排序是改良自冒泡排序和快速排序,其要旨在于消除“乌龟”,亦即在数组尾部的小数值,这些数值是造成冒泡排序缓慢的主因。相对地,“兔子”,亦即在数组前端的大数值,不影响冒泡排序的性能。
    math: true

梳排序

梳排序(Comb Sort)是一种改进的冒泡排序算法。它通过消除“乌龟”(即数组中的小值)和“兔子”(即数组中的大值)来提高排序效率。梳排序的核心思想是先使用较大的间隙(gap)进行比较和交换,然后逐渐减小间隙,最终进行常规的冒泡排序。

梳排序的原理

梳排序的关键在于间隙的选择和逐渐缩小。初始间隙通常设置为数组长度,然后在每次迭代中将间隙除以一个因子(通常为1.3),直到间隙缩小到1,此时进行最后的冒泡排序。

图示

在这里插入图片描述

梳排序的步骤

  1. 设置初始间隙:初始间隙为数组长度。
  2. 调整间隙:在每次迭代中,将间隙除以因子(通常为1.3)。
  3. 比较和交换:在当前间隙下比较并交换元素。
  4. 重复步骤2和3:直到间隙缩小到1,进行最后的冒泡排序。

梳排序示例

假设待数组[10 4 3 9 6 5 2 1 7 8]

第一次循环

待排数组长度为10,而10÷1.3=8,则比较10和7,4和8,并做交换
交换后的结果为[7 4 3 9 6 5 2 1 10 8]

第二次循环

更新间距为8÷1.3=6,比较7和2,4和1,3和10,9和8,7和2,4和1,9和8,需要交换
交换后的结果为[2 1 3 8 6 5 7 4 10 9]

第三次循环

更新距离为4,比较2和6,1和5,3和7,8和4,6和10,5和9,8和4,需要交换
[2 1 3 4 6 5 7 8 10 9]

第四次循环

更新距离为3,比较2和4,1和6,3和5,4和7,6和8,5和10,7和9,不需要交换

第五次循环

更新距离为2,比较2和3,1和4,3和6,4和5,6和7,5和8,7和10,8和9,不需要交换

第六次循环

更新距离为1,为冒泡排序。

[1 2 3 4 5 6 7 8 9 10]

交换后排序结束,顺序输出即可得到[1 2 3 4 5 6 7 8 9 10]

复杂度分析

递减率的设置影响着梳排序的效率,原作者以随机数作实验,得到最有效递减率为1.3的。如果此比率太小,则导致一循环中有过多的比较,如果比率太大,则未能有效消除数组中的乌龟。

亦有人提议用 1 / ( 1 − 1 e φ ) ≈ 1.247330950103979 1/\left(1-{\frac {1}{e^{\varphi }}}\right)\approx 1.247330950103979 1/(1eφ1)1.247330950103979作递减率,同时增加换算表协助于每一循环开始时计算新间距。

因为编程语言中乘法比除法快,故会取递减率倒数与间距相乘, 1 1.247330950103979 = 0.801711847137793 ≈ 0.8 \frac{1}{1.247330950103979}=0.801711847137793\approx 0.8 1.2473309501039791=0.8017118471377930.8

时间复杂度

  • 最佳情况 O ( n log ⁡ n ) O(n\log n) O(nlogn)
  • 最坏情况 Ω ( n 2 ) \Omega(n^2) Ω(n2)
  • 平均情况 Ω ( n 2 2 p ) \Omega (\frac{n^2}{2^p}) Ω(2pn2)

空间复杂度

  • 空间复杂度 O ( 1 ) O(1) O(1)

Java代码实现

import java.util.Arrays;public class CombSort {public static void combSort(int[] arr) {int n = arr.length;int gap = n;boolean swapped = true;while (gap != 1 || swapped) {// 调整间隙gap = getNextGap(gap);swapped = false;// 比较和交换for (int i = 0; i < n - gap; i++) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + gap];arr[i + gap] = temp;swapped = true;}}}}// 计算下一个间隙private static int getNextGap(int gap) {gap = (gap * 10) / 13;if (gap < 1) {return 1;}return gap;}public static void main(String[] args) {int[] arr = {6, 4, 3, 7, 1, 9, 8, 2, 5};System.out.println("Given Array:");System.out.println(Arrays.toString(arr));// 调用梳排序函数combSort(arr);System.out.println("Sorted Array:");System.out.println(Arrays.toString(arr));}
}

变异形式

梳排序-11

设置递减率为1.3时,最后只会有三种不同的间距组合:(9, 6, 4, 3, 2, 1)、(10, 7, 5, 3, 2, 1)、或 (11, 8, 6, 4, 3, 2, 1)。实验证明,如果间距变成9或10时一律改作11,则对效率有明显改善,原因是如果间距曾经是9或10,则到间距变成1时,数值通常不是递增序列,故此要进行几次冒泡排序循环修正。加入此指定间距的变异形式称为梳排序-11(Combsort11)_。

混合梳排序和其他排序算法

如同快速排序和归并排序,梳排序的效率在开始时最佳,接近结束时最差。如果间距变得太小时(例如小于10),改用插入排序或希尔排序等算法,可提升整体性能。

此方法最大好处是不需要检查是否进行过交换程序以将排序循环提早结束。

相关文章:

排序算法之梳排序

title: 梳排序 date: 2024-7-30 14:46:27 0800 categories: 排序算法 tags:排序算法梳排序 description: 梳排序&#xff08;Comb Sort&#xff09;是一种由弗拉基米尔多博舍维奇&#xff08;Wlodzimierz Dobosiewicz&#xff09;于1980年所发明的不稳定排序算法&#xff0c;并…...

ESP8266 创建TCP连接

TCP Client 使用WiFiClient类可以实现TCP Client 基本方法 连接Server&#xff0c;connect WiFiClient client; client.connect(host, port) 检测客户端是否存在数据流 client.available() 读取客户端的一个字符 client.read(); 检查连接状态 client.connected() 使用…...

OceanBase内存管理小窍门

本文来自OceanBase热心用户的实践分享。 本文主要是对OceanBase内存管理的实用技巧分享&#xff0c;而并非直接深入OceanBase的代码层面进行阐述。​​​​​​​ 阅读本文章你将了解&#xff1a; 重载运算符new 与malloc在返回值上区别&#xff1f;在ceph 双向链表新用法&am…...

【问题解决】git status中文文件名乱码

问题复现 解决办法 在git bash中直接执行如下命令 git config --global core.quotepath false原因 通过 git config --help 可以查看到以下内容&#xff1a; core.quotePath Commands that output paths (e.g. ls-files, diff), will quote “unusual” characters in the p…...

探索数据结构:AVL树的分析与实现

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;数据结构与算法 贝蒂的主页&#xff1a;Betty’s blog 1. AVL树的介绍 在前面我们学习二叉搜索树时知道&#xff0c;在数据有序…...

使用 C++ 实现简单的插件系统

使用 C 实现简单的插件系统 在现代软件开发中&#xff0c;插件系统是一种常见的架构模式&#xff0c;它允许开发者在不修改主程序的情况下&#xff0c;扩展应用程序的功能。通过插件&#xff0c;用户可以根据需要添加或移除功能模块&#xff0c;从而提高软件的灵活性和可维护性…...

使用Python创建省份城市地图选择器

在这篇博客中&#xff0c;我们将探讨如何使用Python创建一个简单而实用的省份城市地图选择器。这个项目不仅能帮助我们学习Python的基础知识&#xff0c;还能让我们了解如何处理JSON数据和集成网页浏览器到桌面应用程序中。 C:\pythoncode\new\geographicgooglemap.py 全部代码…...

【Java 数据结构】Stack和Queue介绍

Stack和Queue StackStack是什么Stack的使用构造方法常用方法 栈的模拟实现初始化和基本方法入栈出栈查看栈顶 栈的应用链栈的简单介绍 QueueQueue是什么Queue的使用队列的模拟实现初始化入队出队查看队头元素 循环队列循环队列的定义及其注意点循环队列的实现初始化和基本方法获…...

Docker基本语法

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、更新yum镜像仓库&#xff08;一&#xff09;查看本地yum镜像源地址&#xff08;二&#xff09;设置docker的镜像仓库&#xff08;1&#xff09;安装必要工具…...

uniapp 对于scroll-view滑动和页面滑动的联动处理

需求 遇到一个需求 解决方案 这个时候可以做一个内页面滑动判断 <!-- scroll-y 做true或者false的判断是否滑动 --> <view class"u-menu-wrap" style"background-color: #fff;"><scroll-view :scroll-y"data.isGo" scroll-wit…...

opencv基础的图像操作

1.读取图像&#xff0c;显示图像&#xff0c;保存图像 #图像读取、显示与保存 import numpy as np import cv2 imgcv2.imread(./src/1.jpg) #读取 cv2.imshow("img",img) #显示 cv2.imwrite("./src/2.jpg",img) #保存 cv2.waitKey(0) #让程序进入主循环(让…...

Java | Leetcode Java题解之第337题打家劫舍III

题目&#xff1a; 题解&#xff1a; class Solution {public int rob(TreeNode root) {int[] rootStatus dfs(root);return Math.max(rootStatus[0], rootStatus[1]);}public int[] dfs(TreeNode node) {if (node null) {return new int[]{0, 0};}int[] l dfs(node.left);i…...

本地查看的Git远程仓库分支与远程仓库分支数量不一致

说明&#xff1a;一次&#xff0c;在IDEA中想切换到某分支&#xff0c;但是查看Remote没有找到要切换的分支&#xff0c;但是打开GitLab&#xff0c;查看远程仓库&#xff0c;是有这个分支的。 解决&#xff1a;1&#xff09;在IDEA的Git中&#xff0c;点下面Fatch获取一下远程…...

opencv-python实战项目九:基于拉普拉斯金字塔的图像融合

文章目录 一&#xff0c;简介&#xff1a;二&#xff0c;拉普拉斯金字塔介绍&#xff1a;三&#xff0c;算法实现步骤3.1 构建融合拉普拉斯金字塔3.2 融合后的拉普拉斯金字塔复原&#xff1a; 四&#xff0c;整体代码实现&#xff1a;五&#xff0c;效果&#xff1a; 一&#x…...

浅谈JDK

JDK(Java Development Kit) JDK是Java开发工具包&#xff0c;是Java编程语言的核心软件开发工具。 JDK包含了一系列用于开发、编译和运行Java应用程序的工具和资源。其中包括&#xff1a; 1.Java编译器&#xff08;javac&#xff09;&#xff1a;用于将Java源代码编译成字节…...

爬虫案例3——爬取彩票双色球数据

简介&#xff1a;个人学习分享&#xff0c;如有错误&#xff0c;欢迎批评指正 任务&#xff1a;从500彩票网中爬取双色球数据 目标网页地址&#xff1a;https://datachart.500.com/ssq/ 一、思路和过程 目标网页具体内容如下&#xff1a; ​​​​​ 我们的任务是将上图中…...

C++ | Leetcode C++题解之第337题打家劫舍III

题目&#xff1a; 题解&#xff1a; struct SubtreeStatus {int selected;int notSelected; };class Solution { public:SubtreeStatus dfs(TreeNode* node) {if (!node) {return {0, 0};}auto l dfs(node->left);auto r dfs(node->right);int selected node->val…...

软件架构设计师-UML知识导图

软件架构设计师-UML知识导图&#xff0c;包含如下内容&#xff1a; 结构化设计&#xff0c;包含结构化设计的概念、结构化设计的主要内容、概要设计、详细设计及模块设计原则&#xff1b;UML是什么&#xff1a;介绍UML是什么&#xff1b;UML的结构&#xff1a;构造块、公共机制…...

在使用transformers和pytorch时出现的版本冲突的问题

在使用transformers和torch库的时候&#xff0c;出现了以下问题&#xff1a; 1、OSError: [WinError 126] 找不到指定的模块。 Error loading "D:\Program Files\anaconda3\envs\testenv\Lib\site-packages\torch\lib\fbgemm.dll" or one of its dependencies. 2、…...

uniapp粘贴板地址识别

1&#xff1a; 插件安装 主要是依靠 address-parse 这个插件&#xff1a; 官网 收货地址自动识别 支持pc、h5、微信小程序 - DCloud 插件市场 // 首先需要引入插件 npm install address-parse --save 2&#xff1a;html部分 <view class""><view class&quo…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...