题解 | #求最大最小数#

这道题考察的知识点就是排序。

排序的方法有很多，比如基数排序、冒泡排序、选择排序、归并排序、希尔排序、二分排序......

下面我用几种不同的排序方法来AC这道题。

第一种是简单的sort快速排序

#include<bits/stdc++.h>//sort快排 
using namespace std;
int a[1000001];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
          cin>>a[i];
        sort(a+1,a+1+n);
        cout<<a[n]<<" "<<a[1]<<endl;
    }
}

代码十分简短，但不建议初学者使用，还是要把基础打扎实了

第二种是冒泡排序

#include<bits/stdc++.h> //冒泡排序 
using namespace std;
int a[1000001];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
          cin>>a[i];
        for(int i=1;i<=n-1;i++)//进行n-1轮比较
        {
            for(int j=1;j<=n-i;j++)//每轮进行n-i次比较
            {
                if(a[j]>a[j+1]) 
                  swap(a[j],a[j+1]);
            }
        }
        cout<<a[n]<<" "<<a[1]<<endl;
    }
}

通过相邻两个元素的比较，如果前面的元素值比后面的大了，交换位置，此为升序

如果要实现降序，只需将if(a[j]>a[j+1])的>改成<，如果前面的元素值比后面的小了，交换位置，即可变为降序

第三种是选择排序

#include<bits/stdc++.h> //选择排序 
using namespace std;
int a[1000001];
int main()
{
    int n,k;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
          cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            k=i;
            for(int j=i+1;j<n;j++)
              if(a[j]<a[k]) k=j;
            if(k!=i)
              swap(a[i],a[k]);
        }
        cout<<a[n-1]<<" "<<a[0]<<endl;
    }
}

第四种是插入排序

#include<bits/stdc++.h> //插入排序 
using namespace std;
int a[1000001];
int main()
{
    int n,temp,i,j,k;
    while(cin>>n)
    {
        for(i=0;i<n;i++)
          cin>>a[i];
        for(i=0;i<n;i++)
        {
            for(j=i-1;j>=0;j--)
              if(a[j]<a[i]) break;
            if(j!=i-1)
            {
                temp=a[i];
                for(k=i-1;k>j;k--)
                  a[k+1]=a[k];
                 a[k+1]=temp;
            }
        }
        cout<<a[n-1]<<" "<<a[0]<<endl;
    }
}

第五种是希尔排序

#include<bits/stdc++.h> //希尔排序 (超时） 
using namespace std;
int a[1000001];
int main()
{
    int n,k,j;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
          cin>>a[i];
        int gap=n/2;
        while(gap>0)
        {
            for(int i=gap+1;i<=n;i++)
            {
                j=i;
                while(j=gap>0&&a[j]<a[j-gap])
                {
                    swap(a[j],a[j-gap]);
                    j=j-gap;
                }
            }
            gap=gap/2;
        }
        cout<<a[n]<<" "<<a[1]<<endl;
    }
}

PS:用希尔排序对于这道题而言会超时，因为嵌套的循环层数太多了，时间复杂度很大，一些大的数据过不去，但也提供一种不同的排序方法给大家
蟹蟹支持！