当前位置: 首页 > 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),改用插入排序或希尔排序等算法,可提升整体性能。

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

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

相关文章:

  • ESP8266 创建TCP连接
  • OceanBase内存管理小窍门
  • 【问题解决】git status中文文件名乱码
  • 探索数据结构:AVL树的分析与实现
  • 使用 C++ 实现简单的插件系统
  • 使用Python创建省份城市地图选择器
  • 【Java 数据结构】Stack和Queue介绍
  • Docker基本语法
  • uniapp 对于scroll-view滑动和页面滑动的联动处理
  • opencv基础的图像操作
  • Java | Leetcode Java题解之第337题打家劫舍III
  • 本地查看的Git远程仓库分支与远程仓库分支数量不一致
  • opencv-python实战项目九:基于拉普拉斯金字塔的图像融合
  • 浅谈JDK
  • 爬虫案例3——爬取彩票双色球数据
  • C++ | Leetcode C++题解之第337题打家劫舍III
  • 软件架构设计师-UML知识导图
  • 在使用transformers和pytorch时出现的版本冲突的问题
  • uniapp粘贴板地址识别
  • C语言 | Leetcode C语言题解之第335题路径交叉
  • TypeScript学习第十三篇 - 泛型
  • 工业智能网关在汽车制造企业的应用价值及功能-天拓四方
  • LLM - 在服务器中使用 Ollama + OpenWebUI 部署最新大模型
  • 重启人生计划-积蓄星火
  • 2024.08.11 校招 实习 内推 面经
  • LCA(Lowest Common Ancestor)
  • 张钹院士:大模型时代的企业AI发展趋势
  • php连接sphinx的长连接事宜以及sphinx的排除查询以及关于sphinx里使用SetSelect进行复杂的条件过滤或复杂查询
  • 抓包分析排查利器TCPdump
  • 八种排序算法的复杂度(C语言)