C-データ構造実験の並べ替え六:ヒル並べ替え
12838 ワード
Description
様々なソート方法を学び、異なる状況で異なるソートアルゴリズムを選択し、最適なソート効率を達成することを期待している.並べ替えられるデータにとって、データが基本的に秩序化され、記録が少ない場合、直接並べ替えを挿入する効率は非常に良く、ヒル並べ替えは、基本的に秩序化された少量のデータ記録のセットを並べ替える効率的なアルゴリズムである.増分dk=n/(2^k)(k=1,2,3,...)Input
複数組のデータが連続的に入力され、各組の入力データの最初の行には正の整数N(N<=10000)が与えられ、その後、N個の整数が連続的に並べ替えられるキーワードを表し、数字間はスペースで区切られる.
Output
dk=n/2とdk=1の場合の結果を出力します.Sample
Input
10 10 9 8 7 6 5 4 3 2 1 10 -5 9 7 -11 37 -22 99 288 33 66 Output
5 4 3 2 1 10 9 8 7 6 1 2 3 4 5 6 7 8 9 10 -22 9 7 -11 37 -5 99 288 33 66 -22 -11 -5 7 9 33 37 66 99 288
様々なソート方法を学び、異なる状況で異なるソートアルゴリズムを選択し、最適なソート効率を達成することを期待している.並べ替えられるデータにとって、データが基本的に秩序化され、記録が少ない場合、直接並べ替えを挿入する効率は非常に良く、ヒル並べ替えは、基本的に秩序化された少量のデータ記録のセットを並べ替える効率的なアルゴリズムである.増分dk=n/(2^k)(k=1,2,3,...)Input
複数組のデータが連続的に入力され、各組の入力データの最初の行には正の整数N(N<=10000)が与えられ、その後、N個の整数が連続的に並べ替えられるキーワードを表し、数字間はスペースで区切られる.
Output
dk=n/2とdk=1の場合の結果を出力します.Sample
Input
10 10 9 8 7 6 5 4 3 2 1 10 -5 9 7 -11 37 -22 99 288 33 66 Output
5 4 3 2 1 10 9 8 7 6 1 2 3 4 5 6 7 8 9 10 -22 9 7 -11 37 -5 99 288 33 66 -22 -11 -5 7 9 33 37 66 99 288
#include
#include
#include
using namespace std;
int a[100010],b[100010];
void shell(int a[],int n)
{
int d = n/2;
int t;
for(int i=d; i<n; i++)
{
for(int j=i-d; j>=0; j-=d)
{
if(a[j]>a[j+d])
{
t = a[j];
a[j] = a[j+d];
a[j+d] = t;
}
}
}
}
void shell2(int a[],int n)
{
int d = 1;
int t;
for(int i=d; i<n; i++)
{
for(int j=i-d; j>=0; j-=d)
{
if(a[j]>a[j+d])
{
t = a[j];
a[j] = a[j+d];
a[j+d] = t;
}
}
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
int i;
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
shell(a, n);
for(i=0; i<n; i++)
{
if(i<n-1)
printf("%d ", a[i]);
else
printf("%d
", a[i]);
}
shell2(b,n);
for(i=0; i<n; i++)
{
if(i<n-1)
printf("%d ", b[i]);
else
printf("%d
", b[i]);
}
}
return 0;
}