1. 对一个整型数组A[n]设计一个排序算法。 2. 找出整型数组A[n]中元素的最大值和次最大值。

Question

用C++模板做

Answer 1

首先c++algorithm库里面提供了sort函数支持排序。快排实现的。
直接sort就可以了。对于最大和次大是可以通过一边扫描实现的。记录两个指针。max1，max2。保留目前位置的次大和最大。然后扫描的时候更新就行了。但是如果排完序的话，最大和次大就是A[N]和A[N-1]
（ps：如果是严格次大的话还是需要再扫描一下，还是如果数据不是太大的话可以采用计数排序就是记录C[I]表示I这个数字出现几次，然后从小到大扫描下C数组就行了。看下I这个数出现几次就输出几次）
代码：（sort实现）：

#include
#include
#include
using namespace std;
const int Maxn=1000000;
static int n,m;
static int A[Maxn];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&A[i]);
sort(A+1,A+n+1);
printf("%d %d\n",A[n],A[n-1]);
return 0;
}

Answer 2

1. 对一个整型数组A[n]设计一个排序算法。
void xuanzepaixu()
{
int a[10];
int i,j,t,max;

printf("input 10 numbers:\n");
for(i=0;i<10;i++)scanf("%d",&a[i]);
for(j=0;j<9;j++)
{max=0;
for(i=0;i<9-j;i++)
if(a[max]<a[i])max=i;
if(max!=i-1)
{t=a[max];
a[max]=a[i-1];
a[i-1]=t;}
}
for(i=0;i<10;i++)printf("%5d",a[i]);
printf("\n");
}

2. 找出整型数组A[n]中元素的最大值和次最大值。
#include<stdio.h>

int main()
{
int n,i,max1=0,max2=0,s[105]={0};
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",s+i);
if(s[i]>s[max1])
max1=i;
}
for(i=1;i<=n;i++)
//if(i!=max1&&s[i]>=s[max2])
if(s[i]!=s[max1]&&s[i]>=s[max2])
max2=i;
printf("%d %d\n",s[max1],s[max2]);
return 0;
}追问

用类模板做