侏儒排序- 维基百科，自由的百科全书

此后Dick Grune（英语：Dick Grune）也描述了这一算法，称其为“侏儒排序”。

此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。

从 ... 侏儒排序 维基百科，自由的百科全书 跳到导航 跳到搜索 侏儒排序使用侏儒排序法对一列数字进行排序的过程概况类别排序算法数据结构数组复杂度平均时间复杂度 O ( n 2 ) {\displaystyleO(n^{2})} 最坏时间复杂度 O ( n 2 ) {\displaystyleO(n^{2})} 最优时间复杂度 Ω ( n ) {\displaystyle\Omega(n)} 空间复杂度 O ( 1 ) {\displaystyleO(1)} 辅助空间最佳解No相关变量的定义 侏儒排序（英语：GnomeSort）或愚人排序（英语：StupidSort）是一种排序算法，最初在2000年由伊朗电脑工程师HamidSarbazi-Azad（谢里夫理工大学电脑工程教授）提出，他称之为“愚人排序”[1]。

此后DickGrune（英语：DickGrune）也描述了这一算法，称其为“侏儒排序”[2]。

此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。

从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。

它的平均运行时间是O(n2)，如果列表已经排序好则只需O(n)的运行时间。

[3] 目录 1解释  1.1样例  2参考文献 3外部链接  解释 [编辑] 下面是侏儒排序的伪代码，其中使用的数组是下标从零开始的： proceduregnomeSort(a[]): pos :=0 whilepos=a[pos-1]): pos :=pos+1 else: swapa[pos]anda[pos-1] pos :=pos-1 样例 [编辑] 给定一个未排序的数组a=[5,3,2,4]，侏儒排序在while循环中执行以下步骤。

粗体表示pos变量当前所指的元素。

当前数组 下一步操作 [5,3,2,4]   a[pos]=a[pos-1]，pos自增 [3,5,2,4]   a[pos]1，pos自减 [3,2,5,4]   a[pos]=a[pos-1]，pos自增 [2,3,5,4]   a[pos]1，pos自减 [2,3,4,5] a[pos]>=a[pos-1]，pos自增 [2,3,4,5] a[pos]>=a[pos-1]，pos自增 [2,3,4,5]   pos==length(a)，完成 参考文献[编辑] ^Sarbazi-Azad,Hamid.StupidSort:Anewsortingalgorithm(PDF).Newsletter(ComputingScienceDepartment,Univ.ofGlasgow).2October2000,(599):4[25November2014].（原始内容存档(PDF)于2012-03-07）.  ^GnomeSort-TheSimplestSortAlgorithm.Dickgrune.com.2000-10-02[2017-07-20].（原始内容存档于2017-08-31）.  ^PaulE.Black.gnomesort.DictionaryofAlgorithmsandDataStructures.U.S.NationalInstituteofStandardsandTechnology.[2011-08-20].（原始内容存档于2011-08-11）.  外部链接 [编辑] 侏儒排序（页面存档备份，存于互联网档案馆） 查论编排序算法理论 计算复杂性理论 大O符号 全序关系 数据结构术语列表 原地算法 稳定性 比较排序 自适应排序（英语：Adaptivesort） 排序网络（英语：Sortingnetwork） 整数排序（英语：Integersorting） X+Y排序（英语：X+Ysorting） 量子排序（英语：Quantumsort） 交换排序 冒泡排序 鸡尾酒排序 奇偶排序 梳排序 侏儒排序 快速排序 慢速排序 臭皮匠排序 Bogo排序 选择排序 选择排序 堆排序 平滑排序（英语：Smoothsort） 笛卡尔树排序（英语：Cartesiantreesort） 锦标赛排序（英语：Tournamentsort） 圈排序（英语：Cyclesort） 弱堆排序（英语：Weakheap） 插入排序 插入排序 希尔排序 伸展排序 二叉查找树排序 图书馆排序 耐心排序 归并排序 归并排序 梯级归并排序（英语：Cascademergesort） 振荡归并排序（英语：Oscillatingmergesort） 多相归并排序（英语：Polyphasemergesort） 分布排序 美国旗帜排序（英语：Americanflagsort） 珠排序 桶排序 爆炸排序（英语：Burstsort） 计数排序 比较计数排序 插值排序 鸽巢排序 相邻图排序（英语：Proxmapsort） 基数排序 闪电排序（英语：Flashsort） 并发排序 双调排序器（英语：Bitonicsorter） Batcher归并网络 两两排序网络（英语：Pairwisesortingnetwork） 混合排序 块排序（英语：Blocksort） Tim排序 内省排序 Spread排序（英语：Spreadsort） 归并插入排序（英语：Merge-insertionsort） 其他 拓扑排序 煎饼排序 意粉排序（英语：Spaghettisort） 查论编算法排序比较排序 冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 堆排序 鸡尾酒排序 梳排序 侏儒排序 图书馆排序 内省排序 奇偶排序 线性时间排序 鸽巢排序 基数排序 计数排序 桶排序 并行排序 排序网络（英语：Sortingnetwork） Batcher归并网络 不实用的 Bogo排序 臭皮匠排序 图 拓扑排序 搜索列表 线性搜索 二分搜索 插值搜索 树・图 广度优先搜索 最良优先搜索（英语：Best-firstsearch） 均一开销搜索 A* 深度优先搜索 迭代深化深度优先搜索 深度限制搜索（日语：深さ制限探索） 双向搜索 分枝限定法（英语：Branchandbound） 字符串 KMP算法 博耶-穆尔字符串搜索算法 AC自动机算法 拉宾-卡普算法 bitap算法 最短路问题 戴克斯特拉算法 贝尔曼-福特算法 A*搜索算法 Floyd-Warshall算法 最小生成树 普林姆算法 克鲁斯克尔算法 最大流最小割 福特-富尔克森算法 埃德蒙兹-卡普算法 迪尼茨算法 线性规划 单纯形法 卡马卡尔算法（英语：Karmarkar'salgorithm） 顺序统计量 选择算法 中位数的中位数（英语：Medianofmedians） 种类 近似算法 随机化算法 其他 分治法 动态规划 贪心算法 Category:算法 取自“https://wiki.kfd.me/w/index.php?title=侏儒排序&oldid=71905605” 分类：​排序算法隐藏分类：​使用过时图像语法的页面含有英语的条目 导航菜单 个人工具 没有登录讨论贡献创建账号登录 命名空间 条目讨论 新加坡简体 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 阅读编辑查看历史 更多 搜索 导航 首页分类索引特色内容新闻动态最近更改随机条目资助维基百科 帮助 帮助维基社群方针与指引互助客栈知识问答字词转换IRC即时聊天联络我们关于维基百科 工具 链入页面相关更改上传文件特殊页面固定链接页面信息引用本页维基数据项目 打印/导出 下载为PDF可打印版本 其他语言 CatalàDeutschEnglishEspañolفارسیMagyarՀայերենItaliano日本語PolskiPortuguêsРусскийСрпски/srpskiไทยTürkçeУкраїнська 编辑链接