查看“︁侏儒排序”︁的源代码

{{NoteTA
|G1 = IT
}}
{{Infobox Algorithm
|class=[[排序算法]]
|image=[[File:Sorting gnomesort anim.gif]]
|caption=使用侏儒排序法对一列数字进行排序的过程
|data=[[数组]]
|time=<math>O(n^2)</math>
|best-time=<math>\Omega(n)</math>
|average-time= <math>O(n^2)</math>
|space= <math>O(1)</math>辅助空间
|optimal= No
}}
'''侏儒排序'''（{{lang-en|Gnome Sort}}）或'''愚人排序'''（{{lang-en|Stupid Sort}}）是一种[[排序算法]]，最初在2000年由伊朗计算机工程师哈米德·薩爾巴齊-阿扎德（Hamid Sarbazi-Azad，[[谢里夫理工大学]]计算机工程教授）提出，他称之为“愚人排序”<ref>{{cite journal
 |last         = Sarbazi-Azad
 |first        = Hamid
 |last2        = 
 |first2       = 
 |date         = 2 October 2000
 |title        = Stupid Sort: A new sorting algorithm
 |url          = http://sina.sharif.edu/~azad/stupid-sort.PDF
 |journal      = Newsletter
 |publisher    = Computing Science Department, Univ. of Glasgow
 |volume       = 
 |issue        = 599
 |page         = 4
 |bibcode      = 
 |doi          = 
 |accessdate   = 25 November 2014
 |archive-date = 2012-03-07
 |archive-url  = https://web.archive.org/web/20120307235904/http://sina.sharif.edu/~azad/stupid-sort.PDF
 |dead-url     = no
}}</ref>。此后{{le|迪克·格魯納|Dick Grune}}也描述了这一算法，称其为“侏儒排序”<ref>{{cite web |url=http://www.dickgrune.com/Programs/gnomesort.html |title=Gnome Sort - The Simplest Sort Algorithm |website=Dickgrune.com |date=2000-10-02 |accessdate=2017-07-20 |archive-date=2017-08-31 |archive-url=https://web.archive.org/web/20170831222005/https://dickgrune.com/Programs/gnomesort.html |dead-url=no }}</ref>。此算法类似于[[插入排序]]，但是移动元素到它该去的位置是通过一系列类似[[冒泡排序]]的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。它的[[時間複雜度|平均运行时间]]是 <math>O(n^2)</math> ，如果列表已经排序好则只需 <math>O(n)</math> 的运行时间。<ref>{{cite web|
url=http://xlinux.nist.gov/dads/HTML/gnomeSort.html|
title=gnome sort|
work=Dictionary of Algorithms and Data Structures|
publisher=U.S. National Institute of Standards and Technology|
author=Paul E. Black|
accessdate=2011-08-20|
archive-date=2011-08-11|
archive-url=https://web.archive.org/web/20110811012120/http://xlinux.nist.gov/dads//HTML/gnomeSort.html|
dead-url=no}}</ref>

== 解释 ==
下面是侏儒排序的[[伪代码]]，其中使用的数组是[[從零開始的編號|下标从零开始的]]：

<syntaxhighlight lang="text">
procedure gnomeSort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1
</syntaxhighlight>

=== 样例 ===
给定一个未排序的数组a = [5, 3, 2, 4]，侏儒排序在while循环中执行以下步骤。粗体表示pos变量当前所指的元素。

{| class="wikitable"
|-
! 当前数组
! 下一步操作
|-
|    [5, '''3''', 2, 4]
|    a[pos] < a[pos-1]，交换
|-
|    [3, '''5''', 2, 4]
|    a[pos] >= a[pos-1]，pos自增
|-
|    [3, 5, '''2''', 4]
|    a[pos] < a[pos-1]，交换；pos > 1，pos自减
|-
|    [3, '''2''', 5, 4]
|    a[pos] < a[pos-1]，交换；pos <= 1，pos自增
|-
|    [2, 3, '''5''', 4]
|    a[pos] >= a[pos-1]，pos自增
|-
|    [2, 3, 5, '''4''']
|    a[pos] < a[pos-1]，交换；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)，完成
|}

==實作範例==
===[[Julia (程式語言)]]===
<syntaxhighlight lang="julia">
# Julia Sample : GnomeSort

function GnomeSort(A)
	pos = 1
	while pos<length(A)+1
		if (pos==1) || (A[pos]>=A[pos-1])
			pos+=1
		else
			A[pos],A[pos-1] = A[pos-1],A[pos] 
			pos-=1
		end
	end
	return A
end

# Main Code
A = [16,586,1,31,354,43,3]
println(A)              # Original Array
println(GnomeSort(A))   # Gnome Sort Array
</syntaxhighlight>

== 参考文献 ==
{{Reflist}}

== 外部链接 ==
* [http://dickgrune.com/Programs/gnomesort.html 侏儒排序] {{Wayback|url=http://dickgrune.com/Programs/gnomesort.html |date=20200930153142 }}

{{排序算法}}
{{算法}}

[[Category:排序算法]]