排序算法 | 珠排序(bead sort)详解 Python实现-程序员宅基地

技术标签: 算法  python  python脚本  

01 什么是bead sort(珠排序)?

这是一种自然排序算法,类似于算盘纵向平行柱上面的珠子,纵向平行柱的数量代表待排序数字的最大值,每根柱子上面的柱子数量代表待排序数个数(如待排序数组L = [1, 5, 3, 2, 7, 4],则需要纵向平行柱m=7,每根柱子珠子数量n=6),然后珠子会在重力作用下自由降落。

在这里插入图片描述

然而这个算法在真实实现时性能比较『拉夸』,最好情况下时间复杂度为O(n^2),而且只能对正整数进行排序。

02 算法流程

在这里插入图片描述

待排数组[6 2 4 1 5 9](图A),让所有珠子在重力作用下自由落体,9、5、1都有支撑点,不需要滑落;4除第一个珠子不动外,其它三颗全部下落到1的位置(图B);剩余几个数字做同样自由落地;最终从上到下顺序输出即可得到结果:[ 1 2 4 5 6 9]。

03 Python实现

def bead_sort(sequence: list) -> list:
    """
    >>> bead_sort([6, 11, 12, 4, 1, 5])
    [1, 4, 5, 6, 11, 12]
    >>> bead_sort([9, 8, 7, 6, 5, 4 ,3, 2, 1])
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> bead_sort([5, 0, 4, 3])
    [0, 3, 4, 5]
    >>> bead_sort([8, 2, 1])
    [1, 2, 8]
    >>> bead_sort([1, .9, 0.0, 0, -1, -.9])
    Traceback (most recent call last):
    ...
    TypeError: Sequence must be list of nonnegative integers
    >>> bead_sort("Hello world")
    Traceback (most recent call last):
    ...
    TypeError: Sequence must be list of nonnegative integers
    """
    if any(not isinstance(x, int) or x < 0 for x in sequence):
        raise TypeError("Sequence must be list of nonnegative integers")
    for _ in range(len(sequence)):
        for i, (rod_upper, rod_lower) in enumerate(zip(sequence, sequence[1:])):
            if rod_upper > rod_lower:
                sequence[i] -= rod_upper - rod_lower
                sequence[i + 1] += rod_upper - rod_lower
    return sequence


if __name__ == "__main__":
    assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43716478/article/details/116164067

智能推荐

div 中img 有间隙问题的解决,line-height=0 line-height 等于0-程序员宅基地

文章浏览阅读4.2k次。方案1:img添加display:block 方案2:外层div添加 line-height:0px;

OJ搭建_oj judger.service-程序员宅基地

文章浏览阅读1.1k次。前期准备(Ubuntu 17.10版本)vim安装:sudo apt-get install vimmysql安装:sudo apt-get install mysql-serverapt-get isntall mysql-clientsudo apt-get install libmysqlclient-devaparch2安装apt-get install apache2PHP7.0安装ap..._oj judger.service

关于xs128单片机的一点小小学习心得--认识xs128_当abe为地址/数据总线时,pupae和pupbe无效-程序员宅基地

文章浏览阅读2k次,点赞2次,收藏10次。XS128_当abe为地址/数据总线时,pupae和pupbe无效

ASP.NET中防止注入攻击-程序员宅基地

文章浏览阅读41次。概述 :  你应该在程序中验证所有的不信任输入.你应该假定所有的用户输入都是非法的.用户可以在应用程序中提供表单字段,查询字串,客户端cookies和浏览器环境值比如用户代理字串和IP地址等.  弱输入校验通常为注入攻击提供了机会.下面是常见的利用弱输入校验或无输入校验进行攻击的手段.SQL 注入(SQL injection). 如果你使用用户的输入值来动态构造SQL语句,那么数据库可能执..._如何绕过asp.net中的请求验证进行注入

队列1:队列的基本结构和基本操作-程序员宅基地

文章浏览阅读2.7k次。​1.队列的主要内容从今天开始我们一起学习队列的内容。队列专题相对其他部分来说比较简单一点,不那么烧脑。队列的特点是节点的排队次序和出队次序按入队时间先后确定,即先入队者先出队,后入队者后出队,即我们常说的FIFO(first in first out)先进先出。作为java程序员去面试的时候,你知道在队列方面主要考察什么吗?我告诉你,主要两个方面:一个是Java的并发编程中阻塞队列的原理。具体就是JUC家族中AQS、condition关键字,优先级锁、CountDownLantch等的实现原理_队列

ZYNQ GP总线实现PS与PL交互(一)_zynq如何完成ps和pl的交互-程序员宅基地

文章浏览阅读5.7k次,点赞4次,收藏41次。1,需要对 ZYNQ7 Processing System(PS)配置页面做更改。选中PS-PL Configuration 项,展开 AXI Non Secure Enablement--> GP Master AXI Interface,勾选 M AXI GP0 interface,相当于开启 PS 系统的 AXI GP0 的主机功能。注意下面还有一个 M AXI GP1 interface,也就是说 Zynq 最多可以有 2 个 AXI GP 主机外设。_zynq如何完成ps和pl的交互

随便推点

js获取当前Unix时间戳_js unix时间戳-程序员宅基地

文章浏览阅读1.1w次。JavaScript 获取当前时间戳:第一种方法:var timestamp = Date.parse(new Date());第二种方法:var timestamp=new Date().getTime();第三种方法:var timestamp = (new Date()).valueOf();第一种:获取的时间戳是把毫秒改成000显示,_js unix时间戳

Hopfield神经网络的通俗理解_hopfield神经网络简单理解-程序员宅基地

文章浏览阅读1.6w次,点赞5次,收藏40次。Hopfield网络 和BP神经网络区别和联系。 前馈型神经网络通过引入隐层及非线性转移函数(激活函数)使得网络具有复杂的非线性映射能力。前馈网络的输出仅由当前输入和权矩阵决定,而与网络先前的输出状态无关。而Hopfield神经网络,会把其输出反馈给输出,从而具有时序性的特定。因此需要通过微分方程或差分方程描述网络的动态数学模型。Hopfield神经网络_hopfield神经网络简单理解

android之表格布局_andriod 表格-程序员宅基地

文章浏览阅读2.2k次。表格布局1、表格布局就是往里面加行组成,tableraw2、在tableraw加内容实现列3、子容器中设置属性weight来瓜分tableraw4、图片属性是tableview_andriod 表格

【LATEX】如何并排并列插入图片_texstudio中怎么并排插入图片-程序员宅基地

文章浏览阅读4k次。有一个任务就是如何将四张pdf(当然也可以是其他格式的)合并为一个文件,并且是两行两列排列。在网上找了半天的资料,很多代码跑不通,最后修改了一些内容,终于成功了~ps:里面很多宏包并没有用到,因为我是直接从以前写实验报告的tex文件里复制过来的,只是新增加了\usepackage{subfigure}\usepackage{graphicx}这些宏包基本上能满足所有的需求啦~\documentclass{zjureport}%自己创建的一个文件\usepackage{times}\usepa_texstudio中怎么并排插入图片

Kotlin学习笔记(九)协程简单概念与简单使用_kotlin 协程 join-程序员宅基地

文章浏览阅读864次。1. 协程,就是任务调度框架,可以在一个线程里调度,也可以在一个线程池里调度。2. Kotlin的协程和RxJava一样的功能。至少协程有的,RxJava都有。3.协程和线程的相同点是,都一个“程”字,也就是说,都是要被执行的代码流。4.Kotlin协程的优点是,以“阻塞式的代码”实现“非阻塞式的代码”。都说比RxJava简单一些。........._kotlin 协程 join

I.MX6 eMMC分区挂载-程序员宅基地

文章浏览阅读244次。/********************************************************************* * I.MX6 eMMC分区挂载 * 说明: * 如果想要修改分区的挂载情况,可以修改fstab.freescale文件。 * * ..._imx6 分区挂载

推荐文章

热门文章

相关标签