题解 第三章排序与查找| #特殊排序#
特殊排序
http://www.nowcoder.com/practice/57f0f528bff149be9580af66f6292430
法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;
}
王道机试指南刷题 文章被收录于专栏
计划刷完这本书
查看14道真题和解析