Question

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

设计算法。用C++ 描述

Answer 1

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

#include<iostream>
#include<algorithm>
#include<cstdio>
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

两个相邻元素比较 如果前者比后者大 则换位 否则不动 然后最后一个元素就是最大的 之后用倒数第二个元素和最后一个元素相比较 看是否相同 不同说明最大值只有一个 倒数第二个元素就是此最大的

Answer 3

???