排序算法之臭皮匠排序

系统管理员 2023-03-06 05:18 7阅读 0赞

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

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

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

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);
    }

golang版本

package main
    
    import (
    	"fmt"
    )
    
    func inner_stoogeSort( arr[]int,  low int,  high int)[]int{
        
    	if(arr[low] > arr[high]){
        
    		arr[low], arr[high] = arr[high], arr[low]
    	}
    
    	if(low + 1 >= high){
        
    		return arr
    	}
    
    	part := (high - low + 1)/ 3;
    	inner_stoogeSort(arr, low, high - part) //
    	inner_stoogeSort(arr, low + part, high)
    	inner_stoogeSort(arr, low, high - part)
    	return arr;
    }
    
    func StoogeSort( arr[]int)[]int{
        
    	length := len(arr)
    	if length  <= 1{
        
    		return arr
    	}else{
        
    		return inner_stoogeSort(arr, 0, length - 1);
    	}
    }
    
    func main() {
        
    	arr:=[]int {
        9, 1, 3, 6, 5, 4, 2, 7, 8}
    	fmt.Println(StoogeSort(arr))
    	fmt.Println(arr)
    }

*  如果最后一个值小于第一个值，则交换这两个数
 *  如果当前集合元素数量大于等于3：
    
     *  使用臭皮匠排序前2/3的元素
     *  使用臭皮匠排序后2/3的元素
     *  再次使用臭皮匠排序前2/3的元素  
        ![在这里插入图片描述][20200805154011572.gif]  
        代码整体的思路就是基于递归来实现的，具体操作就是：对于传入的数组先将头部与尾部进行排序，然后递归调用排序前三分之二，再递归调用排序后三分之二，最后再递归调用排序前三分之二

1、对传入的数组的头尾元素进行比较 【low = 0， high = 8】  
![在这里插入图片描述][20200805154846681.gif]  
将数组三等分： split = \[8 - 0 + 1\] / 3 = 3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
2、同样的逻辑递归的排序数组的前 2 / 3 区域 【0， 8 - 3 】= \[0, 5\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]  
splid = (5 - 0 + 1) / 3 = 6 / 3 = 2  
![在这里插入图片描述][20200805161522307.png]

*  同样的逻辑递归的排序数组的前 2 / 3 区域 \[0, 5 - 2\] = \[0, 3\]  
    ![在这里插入图片描述][20200805162043322.png]  
    此时4、6无需交换  
    数据3分：splid = (3 - 0 + 1)/3 = 1  
    ![在这里插入图片描述][20200805163214934.png]
 *  同样的逻辑递归的排序数组的前 2 / 3 区域\[0, 3 - 1\] = \[0, 2\]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]  
    splid = (2 - 0 + 1) / 3 = 1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]

3、同样的逻辑递归的排序数组的后 2 / 3 区域\[0 + 1, 2\] = \[1, 2\]， splid = 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]  
3、同样的逻辑递归的排序数组的前 2 / 3 区域\[0 , 2 - 1\] = \[0, 1\]，

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]

可以看出前3个以及有序了

4、 回到第2个递归, 逻辑递归的排序数组的后 2 / 3 区域\[0+2, 5\] = \[2, 5\]， sp = 2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]  
第3局循环已经完成， 可以看到 4，5，6 局部有序，出栈。

5、回到第3个递归：递归前 2/3 .。。。。

排序完成！

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

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

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

[20200805154011572.gif]: /images/20230208/2c00b98a100c4829bd9d57f3353fd779.png
[20200805154846681.gif]: /images/20230208/89625e418f734c9499f521526c716208.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230208/e288ae04eb9c44a29fad36c37468a0fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20230208/1977f74faa3e422080d11a7e1f8255aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: /images/20230208/413ea97b75bb4594b35b5e437e96257c.png
[20200805161522307.png]: /images/20230208/937c8aa3f03843b48106269add3a9a4c.png
[20200805162043322.png]: /images/20230208/4493c40a558546179204fff29d0604d0.png
[20200805163214934.png]: /images/20230208/d2f4dc938a594f2c93641b64a50d3a5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: /images/20230208/5dc55ee2e17144fb946ac79ea9a4c125.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: /images/20230208/fa3995d9d9174c6b8f150279c8116fd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: /images/20230208/697236cd52a94af99d3ee111d7b286d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]: /images/20230208/da293c0c29a14581bb9b310b77d58d6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]: /images/20230208/eac34fa5780547d7a47b3090cf5d4a4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]: /images/20230208/b9a4522c85e747b88e0c5dfe36f86d21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]: /images/20230208/25605f6950db4673822d4e0db1d0a2b2.png