慢速排序

✍ dations ◷ 2025-07-30 01:38:35 #慢速排序

慢速排序是一种排序算法。其基于合并排序的分而治之及递回的思想,并故意设计使排序过程非常缓慢。慢速排序由Andrei Broder及Jorge Stolfi在1986年发表的论文(论文名称是渐进最优算法及计算复杂性理论的戏仿)中提出。

慢速排序是一种原地算法的递回算法。

在简单的虚拟码中,此算法可以被表示为:

procedure slowsort(A, i, j)                           // 排序一個整數或浮點數數列 A,...,A ,若要使用其他的資料類型則必須重載大於或小於運算符    if i ≥ j then        return    m := ⌊(i+j) / 2⌋                                slowsort(A, i, m)                                 // (1.1)    slowsort(A, m+1, j)                               // (1.2)    if A < A then        swap A and A                            // (1.3)    slowsort(A, i, j-1)                               // (2)
  • 以慢速排序法排序前半部的元素(1.1)
  • 以慢速排序法排序后半部的元素(1.2)
  • 比较1.1及1.2排序结果的最后一个元素,选择相对较大的元素放到列表尾端(1.3)
  • 排除1.3的元素后,将列表剩下的元素以慢速排序法排序(2)

以 Haskell(纯函式编程语言)的实现如下:

slowsort :: Ord a =>  -> slowsort xs  | length xs <= 1 = xs  | otherwise      = slowsort xsnew ++   -- (2)    where        l     = slowsort $ take m xs  -- (1.1)      r     = slowsort $ drop m xs  -- (1.2)      llast = last l      rlast = last r      xsnew = init l ++ min llast rlast : init r      m     = fst (divMod (length xs) 2)

复杂度

慢速排序的运行时间关系式为 T ( n ) = 2 T ( n / 2 ) + T ( n 1 ) + 1 {displaystyle T(n)=2T(n/2)+T(n-1)+1} T ( n ) {displaystyle T(n)} 的渐近下限为 Ω ( n log 2 ( n ) ( 2 + ϵ ) ) {displaystyle Omega left(n^{frac {log _{2}(n)}{(2+epsilon )}}right)} for any ϵ > 0 {displaystyle epsilon >0} 。由于慢速排序渐近下限的时间复杂度不是多项式时间,即使在最好的情况下也比泡沫排序慢。

相关

  • 联邦州 (德国)联邦州(德语:Bundesland)是德国第一级的行政区划,共有16个;其中柏林、汉堡和不来梅为城市州。德国实行联邦制,联邦州享有较大的地方自治权力。德语为“Bundesland”,简称“Land”;英
  • 阿基姆·奥拉朱万阿基姆·阿卜杜勒·奥拉朱旺(英语:Hakeem Abdul Olajuwon,1963年1月21日-),出生于尼日利亚,非洲裔美国NBA联盟前职业篮球运动员。十八年职业生涯效力过休斯敦火箭和多伦多猛龙,场上
  • 雀科雀科(学名:Passeridae)又名麻雀科,为鸟纲雀形目的一个科。本科有8属43种。
  • 利奥波多二世 (托斯卡纳)利奥波多二世(Leopoldo Giovanni Giuseppe Francesco Ferdinando Carlo,1797年10月3日-1870年1月29日),托斯卡纳大公,1824年—1859年在位。利奥波多是斐迪南三世的次子(哥哥弗朗西
  • 红鞭蛇 Müller,1878红鞭蛇属(学名:)是蛇亚目游蛇科下的一个单型蛇属,属下只有红鞭蛇()一个品种。主要分布于保加利亚、以色列、约旦、黎巴嫩、叙利亚及土耳其。红鞭蛇普遍栖息于地中海类
  • 沃尔特·惠特曼·罗斯托沃尔特·惠特曼·罗斯托(英语:Walt Whitman Rostow 1916年10月7日-2003年2月13日)美国经济学家、教授和政治理论家,1966年至1969年担任美国总统林登·约翰逊的国家安全顾问。第
  • 卡克拉拉卡克拉拉(Kakrala),是印度北方邦Budaun县的一个城镇。总人口32380(2001年)。该地2001年总人口32380人,其中男性17286人,女性15094人;0—6岁人口6612人,其中男3416人,女3196人;识字率42.
  • 奈杰尔·肖特奈杰尔·肖特(英语:Nigel Short,1965年6月1日-),英国国际象棋棋手、特级大师。1984年,19岁的肖特获得国际象棋特级大师称号。1988年1月至1989年7月,他的排名曾达到历史最高的世界第
  • 神鹰突击队《神鹰突击队》(英语:Magic Eagle)是中国大陆游戏开发商金盘电子制作的一款战棋游戏,于1994年10月发行,1995年由LG在韩国推出韩文版。游戏是中国大陆最早的原创商业电子游戏,也是第一部出口海外的中国大陆原创电子游戏。斯达拜恩公国公主“夏娃·查尔斯”被邻国的马洛绑架,囚困于郊外的海伦大厦,并由野鹅敢死队驻守当地。玩家在游戏中指挥一支特种部队“神鹰突击队”去解救人质,玩家的敌人是野鹅敢死队,敌人由电脑人工智能控制。玩家控制角色为九名军人,敌人同样有九名军人。玩家可以向麾下军人下达移动、潜伏、攻
  • 福金和雾尼福金(Hugin)和雾尼(Munin),是北欧神话奥丁(Odin)养的两只乌鸦,福金的名字有“思想”(Thought)的意思,雾尼则是“记忆”(Memory)之意。它们两个每天早上一破晓就飞到人间,到了晚上再回去跟奥丁报告。它们总是栖息于奥丁的肩头同他窃窃耳语。也因此奥丁又被称为“乌鸦神”。