珠排序

珠排序（英語：Bead sort）是一种自然排序算法，由約書亞·J·阿魯拉南達姆（Joshua J. Arulanandham）、克里斯蒂安·S·卡魯德（英语：Cristian S. Calude）和邁克爾·狄寧Michael Dinneen（英语：邁克爾·狄寧Michael Dinneen）于2002年发展而来，并且在欧洲理论计算机协会（英语：European Association for Theoretical Computer Science）（EATCS）的新闻简报上发表了该算法。无论是电子还是实物上的实现，珠排序都能在 时间内完成；然而，该算法在电子上的实现明显比实物要慢很多，并且只能用于对正整数序列进行排序。并且，即使在最好的情况，该算法也需要 的空间。

算法概述

第一步：将珠子悬挂在竖直杆上
第二步：让珠子掉落

在珠排序中，一行（row）表示一个数字。如果一行里有2颗珠子，该行代表数字2；如果一行里有4颗珠子，该行代表数字4。当给定一个数组，数组里有多少个数字，就要有多少行；数组里最大的数字是几，就要准备多少根杆子。

准备就绪后，释放珠子，珠子按重力下落，就完成了排序。

珠排序可以类比于珠子在平行的竖直杆上滑动，就像算盘一样。然而，每一竖直杆都有珠子数目的限制。因此，初始化就相当于在竖直的杆上悬挂珠子，在第一步中，排列就被显示为n=5行的珠子在m=4列队竖直杆上。每一行右边的数字意味着该行在问题中被表示的数；第1，2行表示正整数3（因为它们都有3个珠子）而顶层的一行表示正整数2（因为它只含有2个珠子）。

如果我们要允许珠子掉落，那么每行表示已排序的整数。第1行表示在集合中最大的数，而第n行表示最小的数。如果按照前面提到的规则（行包含一系列在竖直杆1到k的珠子，并且让k+1到m竖直杆都空），那么它会出现这种情况。

允许珠子掉落的行为在物理意义上就是允许珠子从高的行掉落至低的行。如果被行a表示的值小于被行a+1表示的值，那么一些珠子就会从a+1掉落至a；因为行a不包含足够的珠子防止珠从a+1行掉落，所以这一定会发生。

用机械装置实现的珠排序类似于计数排序；每一杆上的数字与那些在所有数中等于或大于该数字的数量相当。

复杂度

珠排序可以是以下复杂度级别：

  • O(1)：即所有珠子都同时移动，但这种算法只是概念上的，无法在计算机中实现。
  • O()：在真实的物理世界中用引力实现，所需时间正比于珠子最大高度的平方根，而最大高度正比于n。
  • O(n)：一次移动一列珠子，可以用模拟和数字的硬件实现。
  • O(S)，S是所有输入数据的和：一次移动一个珠子，能在软件中实现。

Python 實现

def bead_sort(l):
    b = []
    l_len = len(l) - 1 
    index = 0 
    count = 0 
 
    while(any(l)):
        if l[index] != 0:
            count += 1
            l[index] -= 1
 
        if index == l_len:
            b.append(count)
            index = 0 
            count = 0 
        else:
            index += 1
 
    if count != 0:
        b.append(count)

    result = []
    for i, v in enumerate(b[:-1]):
        if v == b[i+1]:
            continue
        else:
            result.extend([i + 1 for _ in range(v - b[i + 1])])
 
    result.extend([len(b) for _ in range(max(b) - len(result))])
 
    return result

if __name__ == "__main__":
    print(bead_sort([2, 4, 1, 3, 3]))

外部链接

Read other articles:

Aborigin Australia

Halaman ini berisi artikel tentang Orang Aborigin Australia. Untuk informasi tentang Pribumi Australia secara umum, termasuk Orang Kepulauan Selat Torres, lihat Pribumi-Australia. Aborigin AustraliaBendera Aborigin AustraliaAtas: Windradyne, David Gulpilil, Albert Namatjira, David Unaipon, Mandawuy Yunupingu Bawah: Truganini, Yagan, Geoffrey Gurrumul Yunupingu, Bennelong, Robert TudawaliJumlah populasi759.705 (2016)[1]3,1% dari populasi AustraliaDaerah dengan populasi signifikanWilaya...

 

 

Abhisit Vejjajiva

Abhisit Vejjajivaอภิสิทธิ์ เวชชาชีวะ Perdana Menteri ThailandMasa jabatan17 Desember 2008 – 5 Agustus 2011Penguasa monarkiRama IX PendahuluChaovarat Chanweerakulpelaksana tugasPenggantiYingluck Shinawatra Informasi pribadiLahir8 Maret 1964Newcastle-upon-Tyne, InggrisPartai politikDemokratSuami/istriDr. Pimpen SakuntabhaiSunting kotak info • L • B Abhisit Mark Vejjajiva (Thai: อภิสิทธิ์ เวชชาชีวะ, ...

 

 

Prior-appropriation water rights

Legal doctrine for rights to water use Property law Part of the common law series Types Personal property Community property Real property Unowned property Acquisition Gift Adverse possession Deed Conquest Discovery Accession Lost, mislaid, and abandoned property Treasure trove Bailment License Alienation Estates in land Allodial title Fee simple Fee tail Life estate Defeasible estate Future interest remainder Concurrent estate Leasehold estate Condominiums Real estate Land tenure Conveyancin...

Gunung Kelinabe

KelinabeGunung Kelinabe di sekitar tahun 1915Titik tertinggiKetinggian961 m (3.152 ft 10+1⁄2 in)Koordinat8°50′04″S 121°45′48″E / 8.8344229°S 121.7634674°E / -8.8344229; 121.7634674Koordinat: 8°50′04″S 121°45′48″E / 8.8344229°S 121.7634674°E / -8.8344229; 121.7634674 GeografiKelinabeLokasi Gunung Kelinabe di Pulau Flores, NTTTampilkan peta FloresKelinabeKelinabe (Nusa Tenggara Timur)Tampilkan pet...

 

 

Khalkis

Pelabuhan Chalcis Khalkis merupakan sebuah kota di Yunani. Kota ini letaknya di bagian tengah. Tepatnya di Yunani Tengah. Pada tahun 2001, kota ini memiliki jumlah penduduk sebesar 92.202 jiwa dan memiliki luas wilayah 412 km². Kota ini memiliki angka kepadatan penduduk 224 jiwa/km². Pranala luar Situs resmi Wikivoyage memiliki panduan wisata Calcis. Artikel bertopik geografi atau tempat Yunani ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs

 

 

Manizha

Russian-Tajik singer and songwriter (born 1991) In this name that follows Eastern Slavic naming customs, the patronymic is Dalerovna and the family name is Khamrayeva. ManizhaBackground informationBirth nameManizha Dalerovna KhamrayevaAlso known asManizha SanginBorn (1991-07-08) 8 July 1991 (age 32)Dushanbe, Tajik SSR, Soviet UnionOriginMoscow, RussiaGenresArt popfolktronicaOccupation(s)SingersongwriterYears active2003–presentSpouse(s) Lado Kvataniya ​(m. 2022...

Football Club Sterilgarda Castiglione 2011-2012

Questa voce sull'argomento stagioni delle società calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Voce principale: Football Club Castiglione Società Sportiva Dilettantistica. Football Club Sterilgarda CastiglioneStagione 2011-2012Sport calcio SquadraFootball Club Castiglione Serie D1º posto nel girone B (promosso in Lega Pro Seconda Divisione). 2012-2013 Si invita a seguire il m...

 

 

Airco DH.11 Oxford

DH.11 Oxford Role BomberType of aircraft Manufacturer Airco Designer Geoffrey de Havilland First flight January 1919 Status Abandoned Number built One Developed from Airco DH.10 Amiens The Airco DH.11 Oxford (later de Havilland) was a British twin-engined biplane bomber which was designed to replace the earlier Airco DH.10 Amiens. It was designed to use the unsuccessful ABC Dragonfly engine and was abandoned after the first prototype was built. Development The DH.11 Oxford was designed by Ge...

 

 

Tiye (20th dynasty)

This article is about Tiye, the Egyptian queen. For other uses, see Tiye (disambiguation). Queen consort of Egypt TiyeQueen consort of EgyptA Queen from the time of Ramesses IIISpousePharaoh Ramesses IIIIssuePentawere, Khaemwaset, Meryatum, Ramesses VIII, Duatentopet (only daughter)Dynasty20th Dynasty of EgyptReligionAncient Egyptian religion Tijein hieroglyphs Era: New Kingdom(1550–1069 BC) Tiye was an Ancient Egyptian queen of the Twentieth Dynasty; a secondary wife of Ramesses III, ...

Famiglia francescana

Con l'espressione famiglia francescana viene genericamente indicato un ordine o istituto sia religioso sia di vita apostolica o anche secolare che, canonicamente approvato dalla competente autorità della Chiesa, si rifà in modo esplicito all'esperienza di san Francesco d'Assisi seguendo una delle regole date per il Primo, il Secondo o il Terzo ordine francescano sia regolare sia secolare o anche una regola propria, come accade ad esempio per alcune comunità di nuova fondazione. Francescani...

 

 

Шаблон:Мифология

МифологияРитуально-мифологическийкомплекс Система ценностей Сакральное Миф Мономиф Теория основного мифа Ритуал Обряд Праздник Жречество Мифологическое сознание Магическое мышление Низшая мифология Модель мира Цикличность Сотворение мира Мировое яйцо Мифическое �...

 

 

GTF2E2

GTF2E2 التراكيب المتوفرة بنك بيانات البروتينOrtholog search: PDBe RCSB قائمة رموز معرفات بنك بيانات البروتين 1D8J, 1D8K, 5IY9, 5IYA, 5IYC, 5IYB, 5IY7, 5IY8, 5IYD, 5IY6 المعرفات الأسماء المستعارة GTF2E2, FE, TF2E2, TFIIE-B, TTD6, general transcription factor IIE subunit 2 معرفات خارجية الوراثة المندلية البشرية عبر الإنترنت 189964 MGI: MGI:1915403 HomoloGene: 37...

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

 

 

Amar Lenin

1970 film by Ritwik Ghatak Amar LeninA scene from the documentaryDirected byRitwik GhatakScreenplay byRitwik GhatakProduced bySumana FilmsStarringArun KumarCinematographyDhruba Kumar BasuShakti BanerjeeMusic byJyotirindra MoitroBinoy RoyRelease date 1970 (1970) CountryIndiaLanguageBengali Amar Lenin (Bengali: আমার লেনিন, subtitle: My Lenin) is a 1970 black and white documentary film directed by film director Ritwik Ghatak made[1] for Government of West Bengal in...

 

 

Unity makes strength

Motto of many countries L'Union fait la force redirects here. For the game show, see L'Union fait la force (game show). For the Chinese song, see Unity is Strength. Netherlands, gold ducat (1729) with the motto concordia res parvae crescent on the obverse, found in the Dutch East India Company (VOC) shipwreck 't Vliegend Hert Token coin found in Borneo with the motto concordia res parvae crescent. Unity makes strength[n 1] is a motto that has been used by various states and entities t...

Conservative Party (UK)

British political party The subject of this article is participating in the 2024 general election to the House of Commons of the United Kingdom on 4 July, and has had no MPs in the House of Commons since Parliament was dissolved on 30 May. Some parts of this article may be out of date during this period. Please feel free to improve this article (but note that updates without valid and reliable references will be removed) or discuss changes on the talk page. Conservative and Unionist...

 

 

Francisco I. Madero

President of Mexico from 1911 to 1913 Francisco Madero redirects here. For the Argentine politician, see Francisco Bernabé Madero. For the municipality in Hidalgo, see Francisco I. Madero Municipality, Hidalgo. In this Spanish name, the first or paternal surname is Madero and the second or maternal family name is González. Francisco I. MaderoFrancisco I. Madero, c. 1910–1337th President of MexicoIn office6 November 1911 – 19 February 1913Vice PresidentJosé Ma...

 

 

Tallahatchie County, Mississippi

County in Mississippi, United States County in MississippiTallahatchie CountyCountyTallahatchie County courthouse in SumnerLocation within the U.S. state of MississippiMississippi's location within the U.S.Coordinates: 33°57′N 90°10′W / 33.95°N 90.17°W / 33.95; -90.17Country United StatesState MississippiFoundedDecember 31, 1833Named forChoctaw word roughly meaning “River of rocksSeatCharleston and SumnerLargest cityCharlestonArea • Tota...

مستعر كواركي

المستعر الكواركي (كوارك نوفا) هو انفجار عنيف افتراضي ناجم عن تحويل نجم نيوتروني (انهيار بُنى النيوترونات داخل النجم النيوتروني)[1] إلى نجم كواركات. على غرار انفجار المستعر الأعظم الذي يبشر بولادة نجم نيوتروني، فإن الكوارك نوفا يبشر بإنشاء نجم كوارك. صيغ واقترح مصطلح كو�...

 

 

اسم فعل

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) جزء من سلسلة مقالات حولالنحو والتصريف في العربية الإعراب أقسام الكلام اسم فعل حرف أقسام الجُمَل اسمية فع...