什么是漂亮排序算法：一顿操作很装逼，一看性能二点七

向右看齐 2023-06-13 09:15 52阅读 0赞

在《算法导论》第二版第 7 章（快速排序）的思考题（第 95 页）中提及到一种 **低效的递归排序算法**：Stooge 排序， Howard、Fine 等教授将这个算法称为 **漂亮排序算法**，但经过证明，Stooge 排序的性能是慢于冒泡排序的。

![v2-566b53fb4e5c951965c0d7b2994870ed\_b.gif][v2-566b53fb4e5c951965c0d7b2994870ed_b.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;
        stoogeSortDo(A, low, high - split);
        stoogeSortDo(A, low + split, high);
        stoogeSortDo(A, low, high - split);
    }

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

![v2-b01372ee6c678f5f96fd6b69ca0b792f\_b.jpg][v2-b01372ee6c678f5f96fd6b69ca0b792f_b.jpg]

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

### 动画描述如下： ###

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

![v2-bd872db2f978f46a65dbeddc27a69843\_b.gif][v2-bd872db2f978f46a65dbeddc27a69843_b.gif]

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

![v2-0035dcadb9998814f95e37f791a6d3af\_b.jpg][v2-0035dcadb9998814f95e37f791a6d3af_b.jpg]

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

![v2-290ce59103e2f536866ec340f63683d2\_b.jpg][v2-290ce59103e2f536866ec340f63683d2_b.jpg]

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

![v2-011302d598e46656e0c6792d82ff4ee0\_b.jpg][v2-011302d598e46656e0c6792d82ff4ee0_b.jpg]

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

![v2-d95c3c7b46bc20d73e74e0f299e01b54\_b.jpg][v2-d95c3c7b46bc20d73e74e0f299e01b54_b.jpg]

排序完成！

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

所以，它除了好看，目前也没发现有啥用。

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

![v2-f676b3e171a217a04d338add8f366dd3\_b.jpg][v2-f676b3e171a217a04d338add8f366dd3_b.jpg]

[v2-566b53fb4e5c951965c0d7b2994870ed_b.gif]: https://img-blog.csdnimg.cn/img_convert/c1a2bf3b581b0483572bcc0c3c0f2550.png
[v2-b01372ee6c678f5f96fd6b69ca0b792f_b.jpg]: https://img-blog.csdnimg.cn/img_convert/97a5f4dfe65cb97758f2597949dd8475.png
[v2-bd872db2f978f46a65dbeddc27a69843_b.gif]: https://img-blog.csdnimg.cn/img_convert/530c3eae2c0139ffe1f48455d7290940.gif
[v2-0035dcadb9998814f95e37f791a6d3af_b.jpg]: https://img-blog.csdnimg.cn/img_convert/588a51c83742f1489c8a695b4d666112.png
[v2-290ce59103e2f536866ec340f63683d2_b.jpg]: https://img-blog.csdnimg.cn/img_convert/fe9a06896128097f133baa1cd26bb2d8.png
[v2-011302d598e46656e0c6792d82ff4ee0_b.jpg]: https://img-blog.csdnimg.cn/img_convert/366f8df522b6a609b0c6738426d2be37.png
[v2-d95c3c7b46bc20d73e74e0f299e01b54_b.jpg]: https://img-blog.csdnimg.cn/img_convert/5d9ff9efa1dc5fa9acf2a2800e5c402f.png
[v2-f676b3e171a217a04d338add8f366dd3_b.jpg]: https://img-blog.csdnimg.cn/img_convert/c7baf9b37060b886da4edb968b40f45f.png