慢速排序

✍ dations ◷ 2025-11-17 15:30:12 #慢速排序

慢速排序是一种排序算法。其基于合并排序的分而治之及递回的思想，并故意设计使排序过程非常缓慢。慢速排序由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$ 。由于慢速排序渐近下限的时间复杂度不是多项式时间，即使在最好的情况下也比泡沫排序慢。

相关

小柴昌俊小柴昌俊（日语：小柴昌俊／こしばまさとし Koshiba Masatoshi ?，1926年9月19日－），日本物理学家，日本学士院会员。现任东京大学国际基本粒子物理中心（ICEPP）高级顾问，东京大学最初4名
神游科技神游科技（中国）是于2002年成立的中国大陆游戏公司，起初是美籍华人科学家、企业家颜维群博士和日本著名游戏公司任天堂于2002年合资成立。现时则已经成为任天堂的全资子公司。公
耶罕·阿兰耶罕·阿里斯特·阿兰（法语：Jehan Ariste Alain，1911年2月3日－1940年6月20日），法国作曲家，管风琴家。父亲是一位出色的管风琴师，妹妹是著名管风琴家玛丽-克莱尔·阿兰。阿兰1927年进
戈兰·戈基奇戈兰·戈基奇（Goran Gogić，塞尔维亚语：Горан Гогић，1986年4月24日－2015年7月3日）是一名塞尔维亚的足球运动员，曾效力中国足球甲级联赛的青岛海牛。2015年7月3日，戈基奇于
尤睦佳·泽登巴尔尤睦佳·泽登巴尔（蒙古语：Юмжаагийн Цэдэнбал，1916年9月17日－1991年4月20日）蒙古族杜尔伯特部人，生于乌布苏省达布斯特，蒙古政治家，曾任蒙古人民革命党中央委员会
注册机注册机（英语：Keygen或Keymaker），又称序号机、序号产生器、注册码生成器、序列号生成器，为一种可破解商业软件注册程序之程序。大部分注册机可根据用户输入注册内容来生成对应注册
海迪·穆尔西海迪·穆尔西（Haydy Morsy，1999年9月20日－）是一名埃及现代五项运动员。她曾获得非洲现代五项锦标赛女子个人冠军。她也参加了2016年里约奥运，获得
1972年大西洋飓风季时间轴1972年大西洋飓风季是纪录以来仅有的5个没有形成大型飓风的大西洋飓风季之一，另外4个分别是1968、1986、1994和2013年大西洋飓风季。全季一共形成了7个热带或亚热带低气压并且全部都发展成了热带或亚热带风暴甚至飓风。本季从1972年6月1日正式开始，同年11月30日结束，传统上这样的日期界定了一年中绝大多数热带气旋在大西洋盆地形成的时间段。这个时间轴中记录了本季所有热带气旋形成、增强、减弱、登陆、转变成温带气旋以及消散的具体信息。还包括实际操作中没有发布的信息，如美国国家飓风中心在风暴过后进行的
塞尔焦·巴莱西奥塞尔焦·巴莱西奥（意大利语：Sergio Ballesio，1934年9月15日－），意大利男子曲棍球运动员。他曾代表意大利国家队参加1960年夏季奥林匹克运动会曲棍球比赛，获得第十三名。
弗朗西斯科·阿马特弗朗西斯科·阿马特（西班牙语：Francisco Amat，1943年3月21日－），西班牙男子曲棍球运动员。他曾代表西班牙参加1964年、1968年和1972年夏季奥林匹克运动会曲棍球比赛，最好名次为1964年奥运会的第四名。哥哥佩德罗·阿马特、海梅·阿马特，弟弟胡安·阿马特。儿子波尔·阿马特。侄子豪梅·阿马特、桑蒂·弗雷克萨。Template:1964年夏季奥林匹克运动会男子曲棍球比赛西班牙队阵容Template:1968年夏季奥林匹克运动会男子曲棍球比赛西班牙队阵容Template:1972年夏季奥