你知道什么是漂亮排序法吗？哦，知道，不就是臭皮匠排序法嘛！

深碍√TFBOYSˉ_ 2022-01-22 03:55 277阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

在《算法导论》第二版第 7 章（快速排序）的思考题（第 95 页）中提及到一种 **低效的递归排序算法**：Stooge 排序， Howard、Fine 等教授将这个算法称为 **漂亮排序算法（完美排序算法）。**

经过证明，Stooge 排序的性能是慢于冒泡排序的，因为这个，在《算法导论》中作者悄悄的 “diss” 了一下这几位终生教授，“怀疑”他们是否“名副其实”。

![640?wx\_fmt=gif][640_wx_fmt_gif]

顾名思义， **漂亮排序算法** 它的代码实现 看、上、去 **很整齐很好看**！

//@程序员小吴 在《算法导论》第 2 版第 95 页，里面使用的是 i 和 j，为了//更好理解，我在这里使用了 low 和 high 进行代替private static void stoogeSort(int[] A, int low, int high){    if(A[low] > A[high]) swap(A, low, high);    if(low + 1 >= high ) return;    int split = (high - low + 1) / 3;    stoogeSort(A, low, high - split);    stoogeSort(A, low + split, high);    stoogeSort(A, low, high - split);}
    //更好理解，我在这里使用了 low 和 high 进行代替
    private static void stoogeSort(int[] A, int low, int high){
        
        if(A[low] > A[high]) swap(A, low, high);
        if(low + 1 >= high ) return;
        int split = (high - low + 1) / 3;
        stoogeSort(A, low, high - split);
        stoogeSort(A, low + split, high);
        stoogeSort(A, low, high - split);
    }

通过图片你可能更能直观的看出它的好看。

![640?wx\_fmt=png][640_wx_fmt_png]

代码整体的思路就是基于递归来实现的，具体操作就是：对于传入的数组先将头部与尾部进行排序，然后递归调用排序**前三分之二**，再递归调用排序**后三分之二**，最后再递归调用排序**前三分之二**。

### 动画描述 ###

#### 1.第一步：对传入的数组的头尾元素进行比较 ####

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

#### 2.第二步：判断能否三等分，如果可以则将数组三等分 ####

![640?wx\_fmt=png][640_wx_fmt_png 1]

#### 3.第三步：同样的逻辑递归的排序数组的**前** 2 / 3 区域 ####

![640?wx\_fmt=png][640_wx_fmt_png 2]

#### 4.第四步：同样的逻辑递归的排序数组的**后** 2 / 3 区域 ####

![640?wx\_fmt=png][640_wx_fmt_png 3]

#### 5.第五步：同样的逻辑**再次**递归的排序数组的**前** 2 / 3 区域 ####

![640?wx\_fmt=png][640_wx_fmt_png 4]

排序完成！

这个算法的复杂度为 T(n) = 3 T( 2n / 3 ) + 1，已被其它大牛证明时间复杂度接近于 O(n2.71) ，对比于一般的排序算法，比如冒泡、选择等常见的 O(n2) 排序算法，排序过程上慢很多。

所以，它除了好看，目前也没发现有啥用：**一顿操作瞎装逼，一看性能二点七**！

再补充一个有趣的点，这个算法也被称之为 **臭皮匠算法**： 三个臭皮匠顶个诸葛亮（在代码实现中涉及到三等分这个概念）。

如果你对这种奇葩排序感兴趣的话，不妨点击下面两个链接看看，涉及到猴子排序、面条排序、鸡尾酒排序等各种奇葩排序的动画描述。

你还知道哪些奇葩算法？欢迎留言告诉小吴。

[动画：什么是鸡尾酒排序和地精排序？][Link 1]

[这些奇葩的排序算法，你没见过动画吧？][Link 2]

![640?wx\_fmt=png][640_wx_fmt_png 5]

[640_wx_fmt_jpeg]: /images/20220122/6721402a56334957a414f9893e71c5aa.png
[640_wx_fmt_gif]: /images/20220122/ba65fd64880943f2a242e2da0af18502.png
[640_wx_fmt_png]: /images/20220122/9efc9ded85134078a8d14140c1c1b4f0.png
[640_wx_fmt_gif 1]: /images/20220122/427938c4d5d04ee19f2d3ba7e7bde8c0.png
[640_wx_fmt_png 1]: /images/20220122/d713be8e8f1346b4968821b433312a18.png
[640_wx_fmt_png 2]: /images/20220122/ad376d25710e415e8e442ae712fc1d8a.png
[640_wx_fmt_png 3]: /images/20220122/56391e7bb794473fa15f794528440198.png
[640_wx_fmt_png 4]: /images/20220122/d3fb2653f50b4a82961a6ad9f0ed601b.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484486&idx=2&sn=95ea58e80a1a152eabc6fbcd5492c0a6&chksm=fa0e6bc7cd79e2d1acea00fbd68956fa99b10b112dc0999715db4bd8c4160c4c304dced7e4bb&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484102&idx=1&sn=6512a1ae8262d7a54007c938c6abcd16&chksm=fa0e6d47cd79e4519186fb173044c26cc8cdc89f6bc644603dfde9b171a207f2898cf1a69d3e&scene=21#wechat_redirect
[640_wx_fmt_png 5]: /images/20220122/4d980af85b1e49ad907ca8c557c67352.png