[科普中国]-侏儒排序

侏儒排序（Gnome sort或Stupid sort）是一种排序算法，最初由伊朗计算机工程师Hamid Sarbazi-Azad博士（谢里夫理工大学计算机工程教授）于2000年提出并被称为“愚蠢排序”（不是 与bogosort混淆），然后由Dick Grune描述并命名为“gnome sort”。 它是一种类似于插入排序的排序算法，除了将元素移动到适当的位置是通过一系列交换完成的，如冒泡排序。 它在概念上很简单，不需要嵌套循环。 平均或预期的运行时间是O（n2），但如果列表最初几乎排序，则倾向于O（n）。

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

Gnome Sort基于标准Dutch Garden Gnome（Du。：tuinkabouter）使用的技术。

以下是花园侏儒如何对一系列花盆进行分类。

基本上，他看着旁边的花盆和前一个花盆; 如果他们按照正确的顺序，他会向前迈出一个底池，否则他会将它们交换掉，并向后踩一个底池1。

边界条件：如果没有先前的底池，他会前进; 如果他旁边没有锅，他就完成了。

- “Gnome Sort - 最简单的排序算法”。Dickgrune.com

代码这是使用从零开始的数组的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例子给定一个未排序的数组，a = [5,3,2,4]，gnome排序将在while循环期间执行以下步骤。 “当前位置”以粗体突出显示：

|| ||

优化可以通过引入变量来优化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本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学