臭皮匠排序（Stooge Sort）----(排序算法十二)

末蓝、 2022-09-17 14:17 181阅读 0赞

# 1.算法原理 #

# 2.代码实现 #

#include <stdio.h>
    
    //printArray打印出数组
    void printArray(int a[],int size){  
        printf("数组为：[%d] ",a[0]);  
        for (int i=1;i<size;i++)  
        {  
            printf(" %d ",a[i]);  
        }  
        printf("\n");  
    }
    
    
    
    void StoogeSort(int *a, int i, int j)  
    {  
        if(a[i]>a[j])  {
    		printf("%d<-->%d ",a[i],a[j]);
    		printArray(a,10);
    		a[0]=a[i];
    		a[i]=a[j];
    		a[j]=a[0];
    	}
    
        if((i+1)>=j)  
            return;  
        int k = (j-i+1)/3;  
        StoogeSort(a, i, j-k);  
        StoogeSort(a, i+k, j);  
        StoogeSort(a, i, j-k);  
    }  
    
    
    void main()
    {
    	//a[0]监视哨
    	int  a[10] ={0,9,8,7,6,5,4,3,2,1};  
    	int  len=10;
    	StoogeSort(a,1,len);
    	printArray(a,len);
    }

# 3.结果 #

9<-->3 数组为：[0]  9  8  7  6  5  4  3  2  1
    8<-->7 数组为：[9]  3  8  7  6  5  4  9  2  1
    7<-->6 数组为：[8]  3  7  8  6  5  4  9  2  1
    8<-->7 数组为：[7]  3  6  8  7  5  4  9  2  1
    6<-->5 数组为：[8]  3  6  7  8  5  4  9  2  1
    7<-->6 数组为：[6]  3  5  7  8  6  4  9  2  1
    8<-->7 数组为：[7]  3  5  6  8  7  4  9  2  1
    6<-->4 数组为：[8]  3  5  6  7  8  4  9  2  1
    7<-->6 数组为：[6]  3  5  4  7  8  6  9  2  1
    8<-->7 数组为：[7]  3  5  4  6  8  7  9  2  1
    5<-->4 数组为：[8]  3  5  4  6  7  8  9  2  1
    6<-->2 数组为：[5]  3  4  5  6  7  8  9  2  1
    7<-->6 数组为：[6]  3  4  5  2  7  8  9  6  1
    8<-->7 数组为：[7]  3  4  5  2  6  8  9  7  1
    9<-->8 数组为：[8]  3  4  5  2  6  7  9  8  1
    7<-->1 数组为：[9]  3  4  5  2  6  7  8  9  1
    8<-->7 数组为：[7]  3  4  5  2  6  1  8  9  7
    9<-->8 数组为：[8]  3  4  5  2  6  1  7  9  8
    2<-->1 数组为：[9]  3  4  5  2  6  1  7  8  9
    6<-->2 数组为：[2]  3  4  5  1  6  2  7  8  9
    3<-->2 数组为：[6]  3  4  5  1  2  6  7  8  9
    2<-->1 数组为：[3]  2  4  5  1  3  6  7  8  9
    4<-->2 数组为：[2]  1  4  5  2  3  6  7  8  9
    5<-->4 数组为：[4]  1  2  5  4  3  6  7  8  9
    4<-->3 数组为：[5]  1  2  4  5  3  6  7  8  9
    5<-->4 数组为：[4]  1  2  3  5  4  6  7  8  9
    数组为：[5]  1  2  3  4  5  6  7  8  9