排序算法 | 珠排序(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

智能推荐

12.2. Embedded jBPM controller calls_jbpm <controller>-程序员宅基地

文章浏览阅读273次。When running Business Central with the embedded jBPM controller mode, a series of endpoints related to managing all aspects of KIE Server templates, instances, and containers are also available. For m..._jbpm

三分钟学会使用Git——命令行（一）_git commit 出现命令行-程序员宅基地

文章浏览阅读460次。这是一个简易的Git提交步骤1:检查你的提交的分支有没有出现，一般情况下都是有的git branch -a2:提交所有修改的文件。git add *3:查看是否添加正确git status4:提交你修改的文件，并且附属上说明内容git commit -a -m “填写你的修改文档”5:提交到服务器git push*记住一定是在..._git commit 出现命令行

End-to-end Flow Correlation Tracking with Spatial-temporal Attention && SINT && deep motion feature_end-to-end flow correlation tracking with spatial--程序员宅基地

文章浏览阅读673次。发表在CVPR2018，是朱政老师的一篇文章，论文链接：FlowTrack这篇文章提出的跟踪器叫作FlowTrack(an end-to-end framework for flow correlation tracking) ,是在具有深度卷积特征的DCF（discriminative correlation filters）上进行加入了flow information，提高了特征表示和跟踪..._end-to-end flow correlation tracking with spatial-temporal attention代码

Java字符串数组排序，选择排序，数组去重的几个实例-程序员宅基地

文章浏览阅读400次，点赞6次，收藏6次。从键盘输入若干人名、地名或者国家名，要求按照升序排序之后输出。7（表示将输入7个人名或者地名）Zhang3Li4Wang5Ma6Chen7Shu8Ren9Chen7Li4Ma6Ren9Shu8Wang5Zhang3输出样例: 这个题我们注意字符串的定义及获取即可！本题要求将给定的n个整数从大到小排序后输出。输入第一行给出一个不超过10的正整数n。第二行给出n个整数，其间以空格分隔。在一行中输出从大到小有序的数列，相邻数字间有一个空格，行末不得有多余空格。输出样例：

Pdf浏览器的移植-程序员宅基地

文章浏览阅读106次。pdf阅读器的跨平台移植。高层可以用qt技术，底层用poppler开源库支持，以及linux操作系统的支持。 移植时用到的环境： 1：linux下的qt4开发环境。 移植用到的知识： 1：熟悉linux下的工程编译方法和环境配置。（对linux比较熟悉） 2:可能会用到cmake生成相应的工程文件。（应掌握cmake生成Makefiel的方法以及cmake的简..._pdf阅读器的移植

Clojure世界：单元测试-程序员宅基地

文章浏览阅读171次。单元测试也是一个开发中最常见的需求，在Java里我们用JUnit或者TestNG，在clojure里也内置了单元测试的库。标准库的clojure.test，以及第三方框架midje。这里我将主要介绍clojure.test这个标准库，midje是个更加强大的测试框架，广告下，midje的介绍在第二次cn-clojure聚会上将有个Topic，我就不..._clojure deftest

随便推点

Java 自定义注解-注解器（Annotation）-程序员宅基地

文章浏览阅读60次。如果没有用来读取注解的方法和工作，那么注解也就不会比注释更有用处了。使用注解的过程中，很重要的一部分就是创建于使用注解处理器。Java SE5扩展了反射机制的API，以帮助程序员快速的构造自定义注解处理器。注解处理器类库(java.lang.reflect.AnnotatedElement)：　　Java使用Annotation接口来代表程序元素前面的注解，该接口是所有Ann..._ai annotations

linuxdeployqt-linux下Qt打包工具_fhs-like mode with prefix, fhsprefix: "/../..-程序员宅基地

文章浏览阅读4.5k次，点赞2次，收藏19次。linuxdeployqt简介基于Windows-Qt 发布的打包工具windeployqt，主要打包Qt相关依赖库，但是在linux，qt官方并未发布对应的打包版本。在github中，有人开源了这个版本linuxdeployqt，之前一直知道但是没怎么用，最近因为要打包对应工程，又拿出研究了一下。Windows介绍The Windows deployment tool windeployqt is designed to automate the process of creating a d_fhs-like mode with prefix, fhsprefix: "/../..

合约安全实战两则_合约最安全的操作方法-程序员宅基地

文章浏览阅读407次。1.//0x202E653dA93c2a06076FC95B0A07E39B6003C5f6 Ropstenpragma solidity ^0.4.23;/** * The CoinFlip contract does nothing... */contract CoinFlip { uint256 lashHash; uint256 Factor = 20244007718664171871063861089; mapping (address => uint)._合约最安全的操作方法

oracle for循环 break,Ruby循环 while, for, until, break, redo 和 retry-程序员宅基地

文章浏览阅读341次。Ruby中的循环用于执行相同的代码块指定的次数。本章将详细介绍Ruby支持的循环语句。Rubywhile语句:语法:whileconditional[do]codeend执行代码当条件为true时。while循环的条件是代码中的保留字，换行，反斜杠()或一个分号隔开。实例:#!/usr/bin/ruby$i=0$num=5while$i这将产生以下结果：Insidethe loop i=0In..._oracle break

使用node.ls和vue脚手架开发H5页面的上滑下拉滑动分页感悟_h5单页面开发有什么脚手架-程序员宅基地

文章浏览阅读456次。安装node.js安装node教程官网下载安装首先访问node.js的官方网站，下载你需要的node.js版本，然后选择安装,进入官网首页就会有下载提示，如下图所示，根据提示一步一步的来安装检查是否安装成功打开windows的命令行或者使用快捷键win + r，输入node -v出现以下信息表示安装成功，会显示你安装的node版本号通过上述两个步骤就已经完成对node.js的安装..._h5单页面开发有什么脚手架

内核错误: No rule to make target ‘debian/canonical-certs.pem‘, needed by ‘certs/x509_certificate_list‘_no rule to make target 'debian/canonical-certs.pem-程序员宅基地

文章浏览阅读3.2w次，点赞42次，收藏139次。编译内核报错解决方案编辑.config文件vim .config修改CONFIG_SYSTEM_TRUSTED_KEYS，将其置空。# 将该项原有内容删掉即可，如下CONFIG_SYSTEM_TRUSTED_KEYS=""重新编译内核，问题解决。_no rule to make target 'debian/canonical-certs.pem', needed by 'certs/x509_c

推荐文章

热门文章

相关标签