7-22ソート

N個(長整数範囲)の整数を与え,小さいものから大きいものへのソート後の結果を出力することが要求される.本問題は,種々の異なるソートアルゴリズムの種々のデータの場合の表現をテストすることを目的とする.各グループのテストデータの特徴は以下の通りである:データ1:要素が1つしかない;データ2:11個の異なる整数で、基本的な正確性をテストします.データ3:103個のランダム整数;データ4:104ランダム整数;データ5:105ランダム整数;データ6:105シーケンス整数;データ7:105個の逆順序整数;データ8:105の基本秩序の整数.データ9:105ランダム正の整数で、各数値は1000を超えません.

入力形式:

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

#define MAXN 100005
#define INFINITY 65535

int a[MAXN];
int n;
void ShellSort();

int main()
{
    int i;

    scanf("%d",&n);
    for( i=0; i<n; i++){
        scanf("%d",&a[i]);
    }
    ShellSort();
    for( i=0; i<n; i++){
        printf("%d",a[i]);
        if( i!=(n-1)){
            printf(" ");
        }
    }
    return 0;
}

void ShellSort()
{
    int i,j;
    int temp;
    int increment;

    for( increment=n/2; increment>0; increment/=2){
        for( i=increment; i<n; i++){
            temp = a[i];
            for( j=i-increment; j>=0 && temp<a[j]; j-=increment){
                a[ j+increment ] = a[j];
            }
            a[ j+increment ] = temp;
        }
    }
}