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
#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; }