慢速排序

✍ dations ◷ 2025-12-07 17:48:28 #慢速排序

慢速排序是一种排序算法。其基于合并排序的分而治之及递回的思想，并故意设计使排序过程非常缓慢。慢速排序由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)

复杂度

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

相关

杨智敬杨智敬（Allyn Cooke，1896年2月7日－1990年），中国内地会的美国籍传教士，曾经长期在中国云南省西北部怒江大峡谷以及缅甸、泰国的傈僳族中间传教。1896年2月7日，杨智敬出生在美国旧金
赤松祐高赤松祐高（あかまつすけたか）是战国时代、江户时代初期的武将。永禄2年（1559年）作为赤松政秀之子诞生。天正5年（1577年），与兄长斋村政广一起降服于中国征伐中的丰臣秀吉。之后跟随
GeorgyGeorgy／Georgiy（俄语：Георгий，保加利亚语：Георги）可以指：
不动点定理在数学中，不动点定理是一个结果表示函数在某种特定情况下，至少有一个不动点存在，即至少有一个点能令函数 F ( x ) = x
头转头转（Headspin），它是街舞技巧的一种。以头着地，向上支撑身体，使之与地面呈垂直轴线，再借由连续的旋转动作来平衡。这项动作通常运用在巴西武术卡波耶拉和地板舞。第一次出现头转的
温补振荡器温补振荡器（简称TCXO）是能在较宽的温度范围内工作且频率稳定性较高的频率发生器，它通过内置温度补偿系统来进行自动调节，而达到频率的稳定。
乌恩乌恩（Un），是印度古吉拉特邦Surat县的一个城镇。总人口28761（2001年）。该地2001年总人口28761人，其中男性18644人，女性10117人；0—6岁人口4077人，其中男2137人，女1940人；识字率68.99%，其
忽思慧忽思慧，又译和斯辉，生卒年不详，元朝蒙古族或回回人，中医营养和食疗学家。元仁宗延祐年间忽思慧充饮膳太医，元文宗天历三年（1330年）撰成《饮膳正要》一书。《饮膳正要》“虞集序”称
世界中风日世界中风日是每年的10月29日，目的是引起公众关注中风的问题, 提高预防及治疗中风的意识。每年的10月29日，世界各地的机构都会举行不同的活动，教育公众关注中风，以及减低中风对破坏大众健康的风险。此一年一度的活动自2006年开始，由世界中风组织（英语：World Stroke Organization）（WSO）举办。媒体及各专业机构每年都会参与世界中风日的活动。于2009年，有18个国家参与世界中风日的活动包括澳洲、巴西、沙地亚拉伯等地。同年，蒙古中风协会（Mongolian Stroke Assoc
林良实敦林良实医生（马来语：Ling Liong Sik，1943年9月18日－），马来西亚政治人物、马华公会第六任总会长、前马来西亚交通部长。他曾于1988年担任马来西亚过渡首相，也是当代马来西亚最具影响力的华人政治人物之一。名言“话到唇边留半句”。他也是现任拉曼大学名誉校长、前任拉曼大学理事会主席及拉曼学院理事会主席。担任拉曼学院理事会主席期间，他成功发展该学院至5所分院，分别坐落在槟城、霹雳、柔佛、彭亨及沙巴，在该大学创立过程中，他扮演举足轻重的角色。2012年，拉曼大学金宝校区建立敦林良实礼堂，并以他的