侏儒排序

介绍

侏儒排序是由 Hamid Sarbazi-Azad 在 2000 年提出的，也叫愚人排序法（Stupid sort）。这种排序算法一种简单的复杂度为平方级的排序算法，一般实际生产中不会用到。

Python 代码

	def gnomesort(seq):
	  i = 0
	  while i < len(seq):
	    if i==0 or seq[i-1]<=seq[i]:
	      i += 1
	    else:
	      seq[i], seq[i-1] = seq[i-1], seq[i]
	      i -= 1
	  return seq

说明

侏儒排序法中只有一个简单的 while 循环和额一个索引范围为0到len(seq)-1的索引变量。这和容易让人以为它是一个线性时间的算法，但这个结论被最后一行中的i -= 1语句给否定了。要想搞清楚该算法究竟运行了多长时间，我们必须搞懂他工作过程中的一些细节。

起初，我们会从左边开始扫描（持续递增 i），直到找到一个seq[i-1]大于seq[i]的位置 i,这时两个值顺序就错了，于是else部分开始生效。

else 分支会持续交换seq[i]与seq[i-1]的值并递减 i，直到其再次恢复到之前seq[i-1] <= seq[i]的顺序。换句话说，该算法会沿着目标序列交叉向上扫描来发现错了位的元素，并将其经过反复交换下移到合适的位置。那么其整体开销是多少呢？先忽略到平均情况，只关注最好和最坏的情况。

最好的情况当然是目标序列已经排好序，这时 gnomesort 只需要将整个序列扫描一遍即可便停止，其运行时间为 Ω(n)。

而最坏的情况就没有那么简单了，但也没有多复杂。需要注意的是，通常每当我们发现一个元素错位时，这之前的所有元素都应该是已经排好序了。所以，当我们将新元素移动到合适的位置的时候是不会发生冲突的。也就是说，每纠正一个错位元素，已排序元素的数量就会有所增加，并且下一个错位的元素会出现在更后面的位置上，所以可能的最坏的情况就是查找并移动这些错位的元素的开销与其位置形成了正比关系。因而最糟糕的运行时间就应该是1+2+3+...+(n-1)，也就是 O(n^2)

所以，Ω(n)和 O(n^2)就表示了侏儒算法的最好和最坏情况的上下严格边界。