题解 第三章排序与查找| #特殊排序#

法1:采用自带函数

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a,const void *b)
{
    return *(int*)a>*(int*)b;
}

int main()
{
    int Num=0;
    scanf("%d",&Num);
    int Arr[Num];
    for(int i=0;i<Num;i++)
        scanf("%d",&Arr[i]);
    //以上即将所有的数据录入
    
    qsort(Arr,Num,sizeof(int),cmp);
    printf("%d\n",Arr[Num-1]);
    if(Num!=1)
        for(int i=0;i<Num-1;i++)
            printf("%d ",Arr[i]);
    else printf("-1");
    printf("\n");
    return 0;
}

法2:采用堆排序

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

void Sift(int Arr[], int i, int Num)
{
    int j = 2 * i + 1, temp = Arr[i];
    while (j < Num)
    {
        if (j < Num - 1 && Arr[j] < Arr[j + 1])
            j++;
        if (temp < Arr[j])
        {
            Arr[i] = Arr[j];
            i = j;
            j = 2 * i + 1;
        }
        else
            break;
    }
    Arr[i] = temp;
}

void HeapConstruct(int Arr[], int Num)
{ //作大顶堆,让大的在上面
    for (int i = (Num - 1) / 2; i >= 0; i--)
        Sift(Arr, i, Num);
}

void HeapSort(int Arr[], int Num)
{
    int temp;
    for (int i = Num - 1; i > 0; i--)
    {
        temp = Arr[0];
        Arr[0] = Arr[i];
        Arr[i] = temp;
        Sift(Arr, 0, i);
    }
}

int main()
{
    int Num;
    cin >> Num;
    int Arr[Num];
    for (int i = 0; i < Num; i++)
        cin >> Arr[i];
    //以上即将所有的数据录入

    HeapConstruct(Arr, Num);
    cout << Arr[0] << endl;
    if (Num == 1)
        cout << -1;
    else
    {
        HeapSort(Arr, Num);
        for (int i = 0; i < Num - 1; i++)
            cout << Arr[i] << ' ';
    }
    cout << endl;
    return 0;
}