[科普中國]-侏儒排序

侏儒排序（Gnome sort或Stupid sort）是一種排序算法，最初由伊朗計(jì)算機(jī)工程師Hamid Sarbazi-Azad博士（謝里夫理工大學(xué)計(jì)算機(jī)工程教授）于2000年提出并被稱為“愚蠢排序”（不是 與bogosort混淆），然后由Dick Grune描述并命名為“gnome sort”。 它是一種類似于插入排序的排序算法，除了將元素移動到適當(dāng)?shù)奈恢檬峭ㄟ^一系列交換完成的，如冒泡排序。 它在概念上很簡單，不需要嵌套循環(huán)。 平均或預(yù)期的運(yùn)行時(shí)間是O（n2），但如果列表最初幾乎排序，則傾向于O（n）。

描述Dick Grune用以下故事描述了排序方法：

Gnome Sort基于標(biāo)準(zhǔn)Dutch Garden Gnome（Du。：tuinkabouter）使用的技術(shù)。

以下是花園侏儒如何對一系列花盆進(jìn)行分類。

基本上，他看著旁邊的花盆和前一個花盆; 如果他們按照正確的順序，他會向前邁出一個底池，否則他會將它們交換掉，并向后踩一個底池1。

邊界條件：如果沒有先前的底池，他會前進(jìn); 如果他旁邊沒有鍋，他就完成了。

- “Gnome Sort - 最簡單的排序算法”。Dickgrune.com

代碼這是使用從零開始的數(shù)組的gnome排序的偽代碼：

procedure gnomeSort(a[]): pos := 0 while pos = a[pos-1]): pos := pos + 1 else: swap a[pos] and a[pos-1] pos := pos - 1例子給定一個未排序的數(shù)組，a = [5,3,2,4]，gnome排序?qū)⒃趙hile循環(huán)期間執(zhí)行以下步驟。 “當(dāng)前位置”以粗體突出顯示：

|| ||

優(yōu)化可以通過引入變量來優(yōu)化gnome排序，以在遍歷到列表的開頭之前存儲位置。 這將允許“gnome”在移動花盆后傳送回其先前的位置。通過此優(yōu)化，gnome排序?qū)⒊蔀椴迦肱判虻淖凅w。 本主題簡介中的動畫利用了此優(yōu)化。

以下是使用從零開始的數(shù)組進(jìn)行優(yōu)化的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本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)