世界上的排序算法千千万，作为一名程序设计师 ，若仅对冒泡、插入、选择或者是归并、快排、堆排等主流排序方法背得滚瓜烂熟，未免让排序算法这一斑斓的领域褪色。事实上，排序算法种类多样到令人发指的程度。本文选出三种较有代表性的非主流排序方法略作介绍。
地精排序（Gnome Sort）
传说中最简单的排序算法。从前在一个美丽的大花园中，有一只地精在打零工，工作简单至极——将一排花盆排序。这只小家伙便从第一个花盆开始向后走，每遇到一个更小的花盆，就会将它“拖拽”到应处的位置。终于，地精走到了最后一个花盆处，成功地完成了它的工作。
代码只需要一重循环，但最坏时间复杂度为O(n^2)。不过在原先的花盆较为有序时，地精拖拽花盆的总距离会减少，时间复杂度可达到接近O(n)的程度。综合来看，其时间复杂度和插入排序基本相当。
void Gnome_Sort()
{
int i=1;
while(i<=n)
i>1&&a[i-1]>a[i]?swap(a[i-1],a[i]),i--:i++;
}
一个小优化：将地精走到的最远位置记下，当每一次拖拽完成后使其“瞬间转移”回到过的最远位置，可使其省去再次“检阅”曾经排序过的花盆的麻烦。
臭皮匠排序（Stooge Sort）
一个递归排序算法。它的提出者称其为“一种漂亮的排序算法”，但显然大家并不这样认为，反而在这种算法原理上产生了不好的联想——这个算法由此得名。
其实这种排序算法虽然又慢又不实用，但它的思想的确是“极好的”。
有三个臭皮匠，而整个序列被他们等分成了三份，每一次排序第二个臭皮匠都会先威胁第一个臭皮匠交出所有的大数，并将较小的数强塞到他的手中（递归排序区间内前2/3的数）。之后第三个臭皮匠又对第二个臭皮匠做了同样的事情（再递归排序后2/3的数）。那么整个序列中的大数都到了第三个臭皮匠的手中。而第二个臭皮匠岂能善罢甘休，又将第一个臭皮匠痛扁了一顿，得到了剩余的较大的数（重复第一次排序）。而第一个臭皮匠只能拿着一堆小数感慨自己生不逢时……
注：在整个过程中，三个臭皮匠手中的数的数目不变。
在实际代码实现上，排序的最开始阶段我们需要判断如果这段区间的第一个数大于最后一个数，先将其互换位置，再进行三段排序。
总时间复杂度O(n^2.7)。
inline void Stooge_Sort(int l,int r)
{
if(a[r]<a[l])
swap(a[l],a[r]);
if(r-l+1>=3)
{
int t=(r-l+1)/3;
Stooge_Sort(l,r-t);
Stooge_Sort(l+t,r);
Stooge_Sort(l,r-t);
}
}
猴子排序（Bogo Sort）
inline void Stooge_Sort(int l,int r)
{
if(a[r]<a[l])
swap(a[l],a[r]);
if(r-l+1>=3)
{
int t=(r-l+1)/3;
Stooge_Sort(l,r-t);
Stooge_Sort(l+t,r);
Stooge_Sort(l,r-t);
}
}
京公网安备 11010502036488号