排序是计算机科学中常见的一种问题，比较常见的排序算法有快速排序，归并排序，选择排序，冒泡排序和插入排序等。但也有很多不常见的排序算法，例如以下这几种不实用的排序算法。
1 臭皮匠排序
俗话说“三个臭皮匠，顶个诸葛亮”，臭皮匠排序(Stooge Sort)可能就是一个反例。臭皮匠排序的时间复杂度约为$O(n^{2.7})$，算法过程具体如下：
1.如果最后一个值小于第一个值，则交换这两个数
2.如果当前集合元素数量大于等于3：
- 使用臭皮匠排序前2/3的元素
- 使用臭皮匠排序后2/3的元素
- 再次使用臭皮匠排序前2/3的元素
def stooge_sort(l, start=None, end=None):
if start is None:
start = 0
if end is None:
end = len(l) - 1
if l[start] > l[end]:
l[start], l[end] = l[end], l[start]
k = (end - start + 1) / 3
if k:
stooge_sort(l, start, end - k)
stooge_sort(l, start + k, end)
stooge_sort(l, start, end - k)
2 慢速排序
慢速排序(Slow Sort)采取了Multiply and Surrender的思想。简单来讲，该算法递归地从列表的前后两部分中各自选出最大的元素然后将这两个元素中较大的移至末尾，并且再慢速排序剩下的部分。具体如下：
def slow_sort(l, start=None, end=None):
if start is None:
start = 0
if end is None:
end = len(l) - 1
if start >= end:
return
m = (start + end) / 2
slow_sort(l, start, m)
slow_sort(l, m + 1, end)
if l[m] > l[end]:
l[m], l[end] = l[end], l[m]
slow_sort(l, start, end - 1)
3 地精排序
地精排序(Gnome Sort)类似于插入排序，也被称为最简单的排序算法。因此你也可以叫它傻瓜排序(Stupid Sort)。这个排序算法中只有一层循环，通过一系列的交换把元素移到该去的位置。
def gnome_sort(l):
pos = 0
while pos < len(l):
if pos == 0 or l[pos] >= l[pos - 1]:
pos += 1
else:
l[pos], l[pos - 1] = l[pos - 1], l[pos]
pos -= 1
4 猴子排序
猴子排序(BoGo Sort)则可谓是排序算法中的“霸王”了，得名于爱捣乱的猴子，该算法的核心就是随机排列元素直至排序成功。猴子排序的平均时间复杂度为$O(n \cdot n!)$，并且在最坏情况下你可能一辈子都看不到结果🐒。
from random import shuffle
def BoGo_sort(l):
while any(l[i] > l[i + 1] for i in xrange(len(l) - 1)):
shuffle(l)
该算法还有进化版的蠢猴排序，以及以下这种惊为天人的算法：
from time import sleep
def god_sort(l):
while any(l[i] > l[i + 1] for i in xrange(len(l) - 1)):
sleep(10)
该算法利用内存中α粒子可能发生反转的原理期待奇迹的发生... 开个玩笑😂，不过对于猴子排序还真有详细的分析，无聊的朋友可以看看。
在手机上阅读或分享本文请扫描以下二维码：
Comments