#include <stdio.h>

//最小值 
//选择算法递归实现    
//原理:每次从a[i]~a[n]中选择一个最大值/最小值放到序列首部(得到最值的方法时比较)，
//这样当i=n-1时正好求得一个排序序列 
//时间复杂度分析：设原问题时间复杂度位T(n),共分成了1个子问题
//则T(n)=T(n-1)+n    T(n-1):是要选择n-1次，n:是要比较的次数    (因为1,2,3...都被舍去了)
//递推公式自己去算，数学就可以退出来，=O(n^2) 
void Select(int a[],int i,int n)
{
    if(i<n)
    {
        int small,j,temp;
        small=i;    //用每个递归序列的开头元素去比较 
        for(j=i+1;j<n;j++)
            if(a[j]<a[small])
                small=j;       //获得最小值的下标 
        //交换    使每一次递归 得到一个最小值，放在i-n的行首 
        temp=a[small];
        a[small]=a[i];
        a[i]=temp;  
        Select(a,i+1,n);   //进行下一次递归  
    }
}
//选择算法的非递归实现 1   算法原理:相邻元素两两比较 
void Select1(int a[],int n)
{
    int temp;
    for(int i=0;i<n-1;i++)   
        for(int j=i;j<n;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
 } 
//遍历算法 
void Print(int a[],int n)
{
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
}
int main()
{
    int a[10]={100,32,12,1000,43,56,43,89,0,1};
    int b[10]={100,32,12,1000,43,56,43,89,0,1};
    printf("递归遍历序列: ");
    Select(b,0,10);
    Print(b,10);
    printf("\n左右交换法的序列: ");
    Select1(a,10);
    Print(a,10);
    return 0;
}