侏儒排序（Gnome sort或Stupid sort）是一種排序算法，最初由伊朗計算機工程師Hamid Sarbazi-Azad博士（謝里夫理工大學計算機工程教授）於2000年提出並被稱為“愚蠢排序”（不是 與bogosort混淆），然後由Dick Grune描述並命名為“gnome sort”。 它是一種類似於插入排序的排序算法，除了將元素移動到適當的位置是通過一系列交換完成的，如冒泡排序。 它在概念上很簡單，不需要嵌套循環。 平均或預期的運行時間是O（n2），但如果列表最初幾乎排序，則傾向於O（n）。
基本介紹
- 中文名：侏儒排序
- 外文名：Gnome sort或Stupid sort
描述,代碼,例子,最佳化,
描述
Dick Grune用以下故事描述了排序方法：
Gnome Sort基於標準Dutch Garden Gnome（Du。：tuinkabouter）使用的技術。
以下是花園侏儒如何對一系列花盆進行分類。
基本上，他看著旁邊的花盆和前一個花盆; 如果他們按照正確的順序，他會向前邁出一個底池，否則他會將它們交換掉，並向後踩一個底池。
邊界條件：如果沒有先前的底池，他會前進; 如果他旁邊沒有鍋，他就完成了。
- “Gnome Sort - 最簡單的排序算法”。Dickgrune.com
代碼
這是使用從零開始的數組的gnome排序的偽代碼：
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]，gnome排序將在while循環期間執行以下步驟。 “當前位置”以粗體突出顯示：
當前數組 | 操作 |
[5, 3, 2, 4] | a[pos] < a[pos-1], swap: |
[3, 5, 2, 4] | a[pos] >= a[pos-1], increment pos: |
[3, 5, 2, 4] | a[pos] < a[pos-1], swap and pos > 1, decrement pos: |
[3, 2, 5, 4] | a[pos] < a[pos-1], swap and pos <= 1, increment pos: |
[2, 3, 5, 4] | a[pos] >= a[pos-1], increment pos: |
[2, 3, 5, 4] | a[pos] < a[pos-1], swap and pos > 1, decrement pos: |
[2, 3, 4, 5] | a[pos] >= a[pos-1], increment pos: |
[2, 3, 4, 5] | a[pos] >= a[pos-1], increment pos: |
[2, 3, 4, 5] | pos == length(a), finished. |
最佳化
可以通過引入變數來最佳化gnome排序，以在遍歷到列表的開頭之前存儲位置。 這將允許“gnome”在移動花盆後傳送回其先前的位置。通過此最佳化，gnome排序將成為插入排序的變體。 本主題簡介中的動畫利用了此最佳化。
以下是使用從零開始的數組進行最佳化的gnome排序的偽代碼：
procedure optimizedGnomeSort(a[]):
for pos in 1 to length(a):
gnomeSort(a, pos)procedure gnomeSort(a[], upperBound):
pos := upperBound
while pos > 0 and a[pos-1] > a[pos]:
swap a[pos-1] and a[pos]
pos := pos - 1
