开发者社区> 问答> 正文

计算机算法中的递归法与选择排序法是什么?请细讲

计算机算法中的递归法与选择排序法是什么?请细讲

展开
收起
知与谁同 2018-07-21 17:29:17 1963 0
3 条回答
写回答
取消 提交回答
  • 计算1+2+....+100的值
    #include <stdio.h>
    main()
    {
    printf("%d\n",fun(100));//调用函数fun()
    }
    递归函数
    fun(int n)
    {int t; <br/>if(n==0||n==1) t=1; //如果n为0或为1 输出1 <br/>//n大于0,则为第n项和第n-1项的和,继续调用fun() <br/>//以此类推... <br/>else t=n+fun(n-1); <br/>return t; <br/>}

    什么叫快速排序 qsort
    #include<string.h>
    #include<stdlib.h>
    #include<stdio.h>

    struct student{
    int xuehao;
    char name[20];
    int chengji;
    };

    typedef struct student stu;

    sortbyxuehao(const void *,const void *);
    sortbyname(const void *,const void *);
    sortbychengji(const void *,const void *);

    void main()
    {
    int i;
    stu a[3];
    int choice;
    int (*p)(const void * ,const void *);

    printf("please input record:\n");
    printf("xuehao name chengji:\n");
    for(i=0;i<3;i++)
    {
    scanf("%d",&a[i].xuehao);
    scanf("%s",a[i].name);
    scanf("%d",&a[i].chengji);
    }
    printf("choice_1: sorted xuehao:\n");
    printf("choice_2: sorted name\n");
    printf("choice_3: sorted chengji\n");

    scanf("%d",&choice);
    while(choice!=0)
    {
    if(choice==1)
    p=sortbyxuehao;
    if(choice==2)
    p=sortbyname;
    if(choice==3)
    p=sortbychengji;

    qsort(a,3,sizeof(stu),p);

    if(choice==1)
    for(i=0;i<3;i++)
    printf("\n%d\t%s\t%d",a[i].xuehao,a[i].name,a[i].chengji);
    if(choice==2)
    for(i=0;i<3;i++)
    printf("\n%s\t%d\t%d",a[i].name,a[i].xuehao,a[i].chengji);
    if(choice==3)
    for(i=0;i<3;i++)
    printf("\n%d\t%s\t%d",a[i].chengji,a[i].name,a[i].xuehao);
    printf("\n");
    scanf("%d",&choice);
    }

    }

    sortbyxuehao(const void *p,const void *q)
    {
    stu *x,*y;
    x=(stu*)p;
    y=(stu*)q;

    return (-((*x).xuehao-(*y).xuehao));
    }

    sortbyname(const void *p,const void *q)
    {
    stu *x,*y;
    x=(stu*)p;
    y=(stu*)q;

    return strcmp((*x).name,(*y).name);

    }

    sortbychengji(const void *p,const void *q)
    {
    stu *x,*y;
    x=(stu*)p;
    y=(stu*)q;

    return ((*x).chengji-(*y).chengji);

    }
    2019-07-17 22:55:17
    赞同 展开评论 打赏
  • 静静的看着你们
    选择法排序是一种简单的容易实现的对数据排序的算法。

    以整形数组元素为例,有数组A[10](以C语言为例描述),即A[0],A[1],…,A[8],A[9](假设其元素均互不相同)。要求对其元素排序使之递增有序。

    算法原理:首先以一个元素为基准,从一个方向开始扫描,比如从左至右扫描,以A[0]为基准。接下来从A[0],…,A[9]中找出最小的元素,将其与A[0]交换。然后将基准位置右移一位,重复上面的动作,比如,以A[1]为基准,找出A[1]~A[9]中最小的,将其与A[1]交换。一直进行到基准位置移到数组最后一个元素时排序结束(此时基准左边所有元素均递增有序,而基准为最后一个元素,故完成排序)。

    以下为一个用C描述的函数实现上述排序:

    void sort(int array[],int n) // n 为数组元素个数
    {
    int i,j,k,temp; // i 为基准位置,j 为当前被扫描元素位置,k 用于暂存出现的较小的元素的位置
    for(i=0;i<n-1;i++)
    {
    k=i; // k 初始化为基准位置
    for(j=i+1;j<n;j++)
    if (array[j]<array[k]) k=j ; // k 始终指示出现的较小的元素的位置
    temp=array[k];array[k]=array;array=temp; // 将此趟扫描得到的最小元素与基准互换位置
    }
    }

    此算法的实现相对简单,但效率比较低,时间复杂度为O(n2) (n 的平方),为就地排序。

    递归法比较好理解``
    计算1+2+....+100的值
    #include <stdio.h>
    main()
    {
    printf("%d\n",fun(100));//调用函数fun()
    }
    递归函数
    fun(int n)
    {int t; <br/>if(n==0||n==1) t=1; //如果n为0或为1 输出1 <br/>//n大于0,则为第n项和第n-1项的和,继续调用fun() <br/>//以此类推... <br/>else t=n+fun(n-1); <br/>return t; <br/>}

    #include <stdio.h>
    main()
    {printf("%d\n",fun(100));}
    fun(int n)
    {int t; <br/>if(n==0||n==1) t=1; <br/>else t=n+fun(n-1); <br/>return t; <br/>}
    2019-07-17 22:55:17
    赞同 展开评论 打赏
  • 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。
    能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。

    递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。
    在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。
    在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。
    由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。

    选择排序法 是对 定位比较交换法 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解,设有10个数分别存在数组元素a[0]~a[9]中。定位比较交换法是由大到小依次定位a[0]~a[9]中恰当的值(和武林大会中的比武差不多),a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数,a[0]与后面的元素一一比较,如果a[4]更大,则将a[0]、a[4]交换,a[0]已更新再与后面的a[5]~a[9]比较,如果a[8]还要大,则将a[0]、a[8]交换,a[0]又是新数,再与a[9]比较。一轮比完以后,a[0]就是最大的数了,本次比武的武状元诞生了,接下来从a[1]开始,因为状元要休息了,再来一轮a[1]就是次大的数,也就是榜眼,然后从a[2]开始,比出探花,真成比武大会了,当必到a[8]以后,排序就完成了。
    下面给大家一个例子:
    mai()
    {
    int a[10];
    int i,j,t;
    for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数,比武报名,报名费用10000¥ ^_^*/
    for ( i = 0; i < 9; i ++ )
    for ( j = i + 1; j < 10; j ++)
    if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不过就要让出头把交椅,不过a[ i ]比较爱面子,不好意思见 a[ j ],让t帮忙*/
    for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/
    }
    好啦,罗嗦了半天总算把定位比较排序法讲完了,这个方法不错,容易理解,就是有点麻烦,一把椅子换来换去,哎~
    所以就有了下面的选择排序法,开始的时候椅子谁也不给,放在一边让大家看着,找个人k记录比赛结果,然后发椅子。具体来讲呢就是,改进定位比较排序法,但是这个改进只是一部分,比较的次数没变,该怎么打还是怎么打,就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K,认为a[k]是最大元素其实i=k还是a[ i ]最大,a[k]与后面的元素一一比较,该交换的也是也不换,就是把K的值改变一下就完了,最后在把a[k]与a[ i ]交换,这样a就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较,比的次数没变,交换的次数减少了。
    下面也写个例子:
    main()
    {
    int a[10];
    int i,j,t,k;
    for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数,比武报名,报名费用10000¥ ^_^*/
    for ( i = 0; i < 9; i ++ )
    { k = i; /*裁判AND记者实时追踪报道比赛情况*/
    for ( j = i + 1; j < 10; j ++)
    if ( a[ k ] < a[ j ] ) k = j;
    t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; /* t 发放奖品*/
    }
    for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/
    }
    2019-07-17 22:55:17
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载