只有一重循环的排序——侏儒排序(Gnome Sort)

侏儒排序:从头(i=0)开始遍历元素,如果当前元素比前一个元素大(array[i]>array[i-1]),就把它跟前一个元素互换(Swap(a[i],a[i-1]))并继续检查它(i--),否则检查下一个元素(i++)。当i=length时结束排序。

该排序的神奇之处是只有一重循环,而且代码简单。但是一重循环不代表时间复杂度更小,它的时间复杂度依然是O(n^2),原因就在于代码里的i--起到了和二次循环相同的效果。

优点:

1. 最好情况下时间复杂度低——O(n),一个循环跑下来始终i++,非常顺利。

2. 排序稳定,只交换相邻元素的排序都是稳定的。

3. 额外空间使用少,只需要i(记录进度)和t(交换缓存)。如果比较元素是数字,t都能省掉(不使用临时变量交换两个数字)。

缺点:

效率低。我们对比侏儒排序和直接插入排序。会发现这二者的排序思想一模一样,但是插入排序有2处优化是侏儒排序没做到的:

a. 插入排序遇到不匹配位置的新元素时,把前面的元素挨个后移,然后把新元素直接插入到合适位置(如果位置移动k位,则赋值k+1次)。而侏儒排序是把新元素逐个和前一个元素作交换,一路换位到合适位置,这是典型的冒泡做法(如果位置移动k位,则赋值3*k次)。

b. 当一个元素好不容易从第10位冒泡到第1位的时候,那么此时前10位一定是有序序列。插入排序会直接从第11位继续处理,而侏儒排序只能从第2位继续处理,因为它不知道上个元素是从哪个位置走到第1位的,只好多走冤枉路。

下面是C#代码:

void GnomeSort(List<int> a)
{
int i = 0;
while (i < a.Count)
{
if (i == 0 || a[i - 1] <= a[i])
{
i++;
}
else
{
int t = a[i];
a[i] = a[i - 1];
a[i - 1] = t;
i--;
}
}
}

当然,我们可以通过打补丁的方式来优化它,不过如果这么做了,我们干嘛不直接使用直接插入排序呢?作为直接插入排序的劣质版,它基本上没有实用价值,但是通过研究它,我们就能知道为什么直接插入排序能在这一众O(n^2)排序中脱颖而出了。

上一篇:13个Cat命令管理(显示,排序,建立)文件实例


下一篇:1全志 A20 camera移植