侏儒排序（英语：Gnome Sort）或愚人排序（英语：Stupid Sort）是一种排序算法，最初在2000年由伊朗计算机工程师Hamid Sarbazi-Azad（谢里夫理工大学计算机工程教授）提出，他称之为“愚人排序”。此后Dick Grune也描述了这一算法，称其为“侏儒排序”。此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。它的平均运行时间是O(n2)，如果列表已经排序好则只需O(n)的运行时间。

解释

下面是侏儒排序的伪代码，其中使用的数组是下标从零开始的：

1
2
3
4
5
6
7
8
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

样例

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

当前数组 下一步操作
[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 (编程语言)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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

原文地址：https://zh.wikipedia.org/wiki/%E4%BE%8F%E5%84%92%E6%8E%92%E5%BA%8F

在知识共享 署名-相同方式共享 3.0协议之条款下提供