鸡尾酒排序解读

在数据处理的海洋中,排序算法无疑是引领我们探索数据规律的灯塔。今天,我们要探讨的是一种有趣且独特的排序算法——鸡尾酒排序。鸡尾酒排序,也被称为定向冒泡排序、双冒泡排序或搅拌排序,是冒泡排序的一种变体,它通过改变冒泡排序的单向性,实现了更为高效的排序过程。

一 冒泡排序的优化

让我们回顾一下刚才上一章冒泡排序描述的排序细节,如果[5,8,6,3,9,2,1,7]这个列表为例,当排序算法分别执行到第6、第7轮时,数列状态如下。
在这里插入图片描述
经过六轮排序时,整个列表已经时有序了,而冒泡排序不会感知排序的状态,会继续进行第七次排序。如果列表为[2, 1, 3, 4, 5, 6, 7, 8]呢,其实只是经过一次排序就能得出结构,但是还是会进行6次排序,所以冒泡排序算法的效率并不高。

优化:加标志位

我们知道冒泡排序有可能在提前就知道了排序的结果,那能不能加一个标志位来记录,排序好了就提前退出呢

外层循环加标志位

def optimized_bubble_sort(arr):
    sorted_num = 0
    n = len(arr)
    for i in range(n - 1):
        # 标志位,记录本轮是否有交换发生
        swapped = False
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素,则交换它们
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                # 发生了交换,将标志位设为True
                swapped = True
                # 如果本轮没有发生交换,说明序列已经有序,可以提前终止
        # 统计排序次数
        sorted_num += 1
        if not swapped:
            break           
    print("排序次数:", sorted_num)
    return arr


# 示例
arr = [2, 1, 3, 4, 5, 6, 7, 8]
sorted_arr = optimized_bubble_sort(arr)
print("Sorted array is:", sorted_arr)

其实上面只是优化是通过减少排序的次数,也就是减少最外层循环的次数来优化排序算法,那能不能继续优化呢,答案是肯定的。

我们来看一个列表[3, 4, 2, 1, 5, 6, 7, 8]的冒泡排序

第一轮循环
在这里插入图片描述
后面的5, 6, 7, 8是有序,在第一次排序时内层循环4和1交换位置之后其实已经完成了,但是冒泡排序还是会继续将4和后面的5,6,7,8进行比较,同样内层循环也能加标志位来优化来减少内层循环的执行次数。

内层循环加标志位

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # 标志位,记录本轮内层循环是否有交换发生  
        swapped = False
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素,则交换它们  
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                # 发生了交换,将标志位设为True  
                swapped = True
                # 如果内层循环中没有发生交换,说明该部分已经有序,可以提前终止本轮外层循环  
        if not swapped:
            break
    return arr


# 示例  
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = optimized_bubble_sort(arr)
print("Sorted array is:", sorted_arr)

如上如的代码,每轮内层循环中已经排好序了就直接跳出循环直接进行下一轮循环。但是这两次优化都不是最优的解,下面的鸡尾酒排序是对冒泡排序更进一步的优化。

二、鸡尾酒排序的原理

鸡尾酒排序的核心思想是在序列中来回进行升序和降序的冒泡排序。这种排序方式就像是调制一杯鸡尾酒,来回搅拌,直到所有的元素都按照预定的顺序排列好。

具体来说,鸡尾酒排序的步骤如下:

  1. 首先,从左到右进行一轮升序的冒泡排序,使得较大的元素逐渐向右移动。
  2. 然后,从右到左进行一轮降序的冒泡排序,使得较小的元素逐渐向左移动。
  3. 通过不断重复上述两个步骤,序列中的元素会逐渐变得有序。每一轮排序后,未排序的部分会逐渐缩小,直到整个序列完全有序。

三、鸡尾酒排序的实现

鸡尾酒排序的实现相对简单,但需要注意边界的处理。下面是一个使用Python编写的鸡尾酒排序算法示例:
在这里插入图片描述

def cocktail_sort(arr):  
    n = len(arr)  
    swapped = True  
    start = 0  
    end = n - 1  
    while (swapped == True):  
        swapped = False  
        for i in range(start, end):  
            if arr[i] > arr[i + 1]:  
                arr[i], arr[i + 1] = arr[i + 1], arr[i]  
                swapped = True  
        if swapped == False:  
            break  
        swapped = False  
        end = end - 1  
        for i in range(end - 1, start - 1, -1):  
            if arr[i] > arr[i + 1]:  
                arr[i], arr[i + 1] = arr[i + 1], arr[i]  
                swapped = True  
        start = start + 1  
    return arr

在这个实现中,我们使用了两个指针startend来标记当前排序的边界。通过不断缩小边界并交替进行升序和降序的冒泡排序,最终实现了整个序列的有序化。

四、鸡尾酒排序的效率与应用

鸡尾酒排序通过改变冒泡排序的单向性,提高了排序的效率。虽然其时间复杂度仍然是O(n^2),但在某些情况下,鸡尾酒排序的性能优于冒泡排序。特别是在数据已经部分有序或者数据规模适中的情况下,鸡尾酒排序能够更快地完成排序任务。

鸡尾酒排序在实际应用中可能不是最优的排序算法,但其独特的排序方式和简洁的实现代码使得它成为学习排序算法和算法设计思想的一个好例子。通过学习和实践鸡尾酒排序,我们可以更好地理解排序算法的原理和实现方法,为后续学习和应用更复杂的排序算法打下基础。

五、总结

鸡尾酒排序以其独特的排序方式和简洁的实现代码吸引了众多算法爱好者的关注。通过学习和实践鸡尾酒排序,我们可以更加深入地理解排序算法的原理和设计思想。同时,我们也可以从中体会到算法设计的巧妙之处和计算机科学的魅力所在。无论是作为学习排序算法的入门之选,还是作为探索算法设计的有趣案例,鸡尾酒排序都值得我们深入研究和探讨。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[计算机效率] 磁盘空间分析工具:FolderSize

3.15 磁盘空间分析工具:FolderSize FolderSize是一款磁盘管理工具,提供预约交互式磁盘空间分析体验,可以可视化观察磁盘空间使用情况。程序可以帮助用户快速查看并统计硬盘中的各个分区所占用的空间大小以及文件夹和文件的大小,并…

CCleaner如何还原系统 CCleaner怎么恢复注册表 ccleaner官方下载

CCleaner是一款电脑清理软件,其中的注册表清理功能是该软件很重要的功能。注册表作为电脑的重要文件,不可以随便清理,而CCleaner可以帮我们安全,快速地清除注册表。同时,CCleaner还有还原系统的功能。下面将为大家介绍…

Windows与Linux路径分隔符对比及Java代码实战

在Windows中,磁盘中用反斜杠(又称为右斜杠)\表示路径的分隔。在浏览器中用正斜杠/来表示路径的分隔。 Linux则是统一用/表示路径的分隔的。下面给出Linux中一些常见的路径表示: / 表示根目录./ 表示当前目录…/ 表示上级目录 …

如果夸克网盘开了会员下载还是很慢怎么办

最近发现一个windows系统下很奇怪的bug,通过夸克网盘客户端下载别人分享的夸克网盘内容的时候,莫名其妙的会在10M/s和0M/s之间来回徘徊,速度慢到不能忍。 在尝试了几种方法之后,发现一种神奇的方法居然可以解决这个奇怪的bug...所…

C++:初步接触C++(2)

hello,各位小伙伴,本篇文章跟大家一起学习C,感谢大家对我上一篇的支持,如有什么问题,还请多多指教 ! 文章目录 内联函数1.概念2.特性 auto关键字1.auto简介2.auto的使用细则3.auto不能推导的场景 基于范围…

「每日跟读」英语常用句型公式 第3篇

「每日跟读」英语常用句型公式 第3篇 1. I don’t know how to ____ 我不知道如何_____ I don’t know how to play soccer (我不知道怎么踢足球) I don’t know how to study(我不知道如何学习) I don’t know how to play chess (我不知道如何下国…

备战蓝桥杯---刷二分与前缀和题

刷点题~ 1.二分多路归并算法 对于每一个技能,我们把它看成一个等差数列,我们把所有可能都放到一个集合里,排个序,取前m个大即可,现在考虑优化,假如m不是很大,我们直接用优先队列即可&#xff0…

普通Java工程可执行JAR两种打包方式探讨

文章目录 一、需求概述二、代码结构三、运行结果四、打包设置1. 一体化可执行包2. 带外部依赖lib的可执行包 五、打包运行1. 源码放送2. 打包执行3. 打包结果 一、需求概述 普通Java工程 docker-show 实现了定时打印docker应用信息,现在需要将其打包成可执行Jar部署…

设计模式总结-装饰者模式

模式动机 一般有两种方式可以实现给一个类或对象增加行为: 继承机制,使用继承机制是给现有类添加功能的一种有效途径,通过继承一个现有类可以使得子类在拥有自身方法的同时还拥有父类的方法。但是这种方法是静态的,用户不能控制增…

使用msf进行有防火墙限制的3389端口转发

使用msf进行有防火墙限制的3389端口转发 这里主要是针对在内网中遇到需要开启3389的时候,发现存在防火墙,就没有办法直接远程连接,这个时候就可以使用端口转发使用msf,使用前记得先初始化,连接好数据库这里先使用msf进…

如何部署上线项目

❤️ Author: 老九 ☕️ 个人博客:老九的CSDN博客 🙏 个人名言:不可控之事 乐观面对 😍 系列专栏: 文章目录 多环境多环境分类前端多环境实战请求地址启动方式项目配置 后端多环境实战 项目部署原始部署前端…

深入理解计算机系统 家庭作业 2.84

这题没有这个要求所以可以用 ? > : < 这种运算 以下代码用的是位级运算.因为我误解了题意 呜呜呜 想看用判断的代码请自行百度 ((((ux<<9>>9)<<((ux<<1>>24)-127)) - ((uy<<9>>9)<<((uy<<1>>24)-127)))>…

当代软件专业大学生与青年在新质生产力背景下的发展探究

在新质生产力的浪潮中,信息技术以前所未有的速度革新,为软件专业的大学生和青年带来了丰富的机遇,同时也伴随着一系列的挑战。他们如何把握时代的脉搏,实现个人的发展,成为了值得深入探讨的话题。 一、新质生产力背景下的机遇 随着新质生产力的不断发展,信息技术在各个领…

一篇文章带你掌握二叉树(附带二叉树基本操作完整代码演示,和两种思路)

【本长内容】 1. 掌握树的基本概念 2. 掌握二叉树概念及特性 3. 掌握二叉树的基本操作 4. 完成二叉树相关的面试题练习 1. 树形结构 1.1 概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是…

考研数据结构——中缀转后缀(用栈实现)

算法目的&#xff1a;给计算机一个中缀表达式&#xff0c;输出一个后缀表达式。 考点&#xff1a;考察进行到某一步时&#xff0c;栈内的情况是怎么样的&#xff0c;选择题。 学习目标&#xff1a;能用笔算的方式模拟整个过程&#xff0c;不需要会写代码。 过程&#xff1a;…

分类预测 | Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据分类预测

分类预测 | Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据分类预测 目录 分类预测 | Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现GWO-LSSVM灰狼算法优化最小二乘支持向量机数据…

每日面经分享(Git经典题目,Git入门)

1. GitHub是什么 a. Git是一个分布式版本控制系统&#xff0c;作用是跟踪、管理和协调软件开发项目中的代码更改。 b. 提供了一种有效的方式来管理代码的版本历史&#xff0c;以及多人协作开发的能力。 2. Git的作用有哪些 a. 版本控制&#xff1a;Git可以记录每次代码更改的…

Anaconda换源和常用命令

设置Anaconda国内镜像加速下载 使用conda install python包非常便捷&#xff0c;但由于官方服务器位于国外&#xff0c;下载速度较慢。为了提升下载速度&#xff0c;国内清华大学提供了Anaconda的仓库镜像。 要将Anaconda设置为使用国内镜像&#xff0c;特别是清华镜像源&…

[java]网络编程

网络编程概述 计算机网络&#xff1a; 把分布在不同地理区域的具有独立功能的计算机,通过通信设备与线路连接起来&#xff0c;由功能完善的软件实现资源共享和信息传递的系统。 Java是 Internet 上的语言&#xff0c;它从语言级上提供了对网络应用程序的支持&#xff0c;程序…

软考之零碎片段记录(六)+复习巩固

A. 上新 一、关系模式 1. 决定属性 AB->C,函数依赖左侧出现为决定属性 AB->C,函数依赖右侧出现为非决定属性 候选键在决定属性中挑选&#xff0c;AB->C, CD->B中&#xff0c;A,D为侯选建 二、授权SQL 将权限授予用户&#xff08;grant <权限> on&#xf…