问答题
使用VC6打开
下的源程序文件modi2.cpp。阅读下列函数说明和代码,实现函数sort(int A[],int n),用选择排序法把数组从大到小排序。
提示:选择排序法的思想是:
(1)反复从还未排好的那部分线性表中选择出关键字最小的节点;
(2)按照从线性表中选择出的顺序排列节点,重新组成线性表;
(3)直到未排序的那部分为空,则重新形成的线性表是一个有序的线性表。
补充函数sort(intA[],int n),实现选择排序。
注意:请勿改动主函数。
#include <iostream.h>
#define N 10
void sort(int A[N],int n)
{
}
int main ()
{
int A[N]={1, 2, 10, 5,7, 19, 34,78,-3,8};
sort(A, 10);
for (int i=0;i<sizeof(A)/sizeof(int); i++)
{
cout
<
<
A[i]
<
<
" ";
}
cout
<
<
endl;
return 0;
}
【正确答案】
【答案解析】int i,j;
for (i=0; i<n-1; i++)
{
for (j=0; j<n-1-i; j++)
{
if(A[j]>A[j+1])
//如果前面的数比后面的大则进行交换
{
int t=A[j];//做交换
A[j]=A[j+1];
A[j+1]=t;
}
}
}
答案考生文件夹
[解析] 选择法的思路是:将相邻两个数比较,将小的调到前头。这样下标从0到n-1的数与其后面相邻的数交换,可以把最大的数交换到数组的末端。进行n次下标从0到n-1的交换,则数组则会变成有序的,而且是由小到大的顺序。
(1)数组A[N]中有n个数,进行n-1趟比较,在每一趟比较中两两比较的次数逐渐减少,比如若有6个数9,8,5,4,2,0。第一次将8和9对调,第二次将第2和第3个数(9和5)对调,……,如此共进行5次,得到8-5-4-2-0-9的顺序,可以看到:最大的数9已“沉底”,成为最下面一个数,而小的数“上升”。最小的数0已向上“浮起”一个位置。经第一趟(共5次)后,已得到最大的数。然后进行第二趟比较,对余下的前面5个数按上法进行比较,经过4次比较,得到次大的数8。如此进行下去。可以推知,6个数要比较5趟。在第一趟中要进行两两比较5次,在第二趟中比4次,……第5趟比1次。因此设置两层循环,外层循环变量i从0变化大到n-1,内层循环变量i从0到n-i,在内层循环体内,比较相邻两数,如果前面比后面的大则交换。
(2)在内层循环体内,如果前面的元素比后面的元素大,则用一个临时变量记录前面的第j个元素,然后将第j+1个元素赋值给第j个元素,临时变量值赋给第j+1个元素,如此完成两个元素的交换。