練習7.1ソート(25点)+C言語
1884 ワード
入力規模は10の0次から10の5次まで変化するので、規模に応じて異なるソート方法を選択することが望ましい
N個(長整数範囲)の整数を与え,小さいものから大きいものへのソート後の結果を出力することが要求される.
本問題は,種々の異なるソートアルゴリズムの種々のデータの場合の表現をテストすることを目的とする.各グループのテストデータの特徴は以下の通りである.データ1:1要素のみ; データ2:11個の異なる整数で、基本的な正確性をテストします. データ3:103ランダム整数; データ4:104ランダム整数; データ5:105ランダム整数; データ6:105シーケンス整数; データ7:105逆シーケンス整数; データ8:105基本秩序の整数; データ9:105ランダム正の整数で、各数値は1000を超えません.
参照コード:
N個(長整数範囲)の整数を与え,小さいものから大きいものへのソート後の結果を出力することが要求される.
本問題は,種々の異なるソートアルゴリズムの種々のデータの場合の表現をテストすることを目的とする.各グループのテストデータの特徴は以下の通りである.
入力形式:
入力第1行は正の整数N(≦10 5)を与え、その後、1行はN個の(長い整数範囲内の)整数を与え、その間をスペースで区切る.出力フォーマット:
は、1行に小から大へ並べ替えた結果を出力し、数字間は1つのスペースで区切られ、行末に余分なスペースがあってはならない.サンプルを入力:
11
4 981 10 -17 0 -20 29 50 8 43 -5
出力サンプル:
-20 -17 -5 0 4 8 10 29 43 50 981参照コード:
#include
#include
void InsertationSort(int A[],int n);
void PrecDown(int A[],int p,int n);
void HeapSort(int A[],int n);
int main()
{
int N,*A;
scanf("%d",&N);
A=(int *)malloc(sizeof(int)*N);
for(int i=0;i0&&A[j-1]>temp;j--)
{
A[j]=A[j-1];
}
A[j]=temp;
}
}
//
void PrecDown(int A[],int p,int n)
{
int parent,child,X;
X=A[p];
for(parent=p;(2*parent+1)=A[child])
{
break;
}
else
{
A[parent]=A[child];
}
}
A[parent]=X;
}
void HeapSort(int A[],int n)
{
for(int i=n/2-1;i>=0;i--)//
{
PrecDown(A,i,n);
}
//
for(int i=n-1;i>0;i--)
{
int temp;
temp=A[0];
A[0]=A[i];
A[i]=temp;
PrecDown(A,0,i);
}
}