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

Answer 1

递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。
能采用递归描述的算法通常有这样的特征：为求解规模为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 ]); /*显示排序后的结果*/
}

Answer 2

选择法排序是一种简单的容易实现的对数据排序的算法。

以整形数组元素为例，有数组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/>}

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

}