7-12ソート(25点)(ヒルソート)

5493 ワード

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

    入力形式:

    は、1行目に正の整数N(≦)を入力し、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
  •  1 #include
     2 #include
     3 
     4 #define MAXN 100005
     5 #define INFINITY 65535
     6 
     7 int a[MAXN];
     8 int n;
     9 void ShellSort();
    10 
    11 int main()
    12 {
    13     int i;
    14 
    15     scanf("%d",&n);
    16     for( i=0; i){
    17         scanf("%d",&a[i]);
    18     }
    19     ShellSort();
    20     for( i=0; i){
    21         printf("%d",a[i]);
    22         if( i!=(n-1)){
    23             printf(" ");
    24         }
    25     }
    26     return 0;
    27 }
    28 
    29 void ShellSort()
    30 {
    31     int i,j;
    32     int temp;
    33     int increment;
    34 
    35     for( increment=n/2; increment>0; increment/=2){
    36         for( i=increment; i){
    37             temp = a[i];
    38             for( j=i-increment; j>=0 && tempincrement){
    39                 a[ j+increment ] = a[j];
    40             }
    41             a[ j+increment ] = temp;
    42         }
    43     }
    44 }

     
    転載先:https://www.cnblogs.com/yuxiaoba/p/8358213.html