#include<iostream>
using namespace std;
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <stdio.h>
#include  <stdlib.h>
#define MAXL 50
typedef int KeyType;
typedef char InfoType[10];
typedef struct
{   
    KeyType key;               
    InfoType data;              
} RecType;


/* 希尔排序 */
void shell(RecType R[],int n,int &moves,int &comtimes)
{
    int i,j,gap;
    RecType tmp;
    gap=n/2;    /* 增量置初值 */
    while(gap>0)
    {
        for(i=gap;i<n;i++)    /* 对所有相隔gap位置的元素组采用直接插入排序 */
        {
            tmp=R[i];
            moves++;/* 移动次数加一 */
            j=i-gap;
            while(j>=0 && tmp.key<R[j].key)/* 对相隔gap位置的元素组进行排序 */
            {
                R[j+gap]=R[j];
                j=i-gap;        
            }
            moves++;/* 移动次数加一 */
            comtimes++;/* 比较次数加一 */
            R[j+gap]=tmp;
            moves++;/* 移动次数加一 */
   
        }
        gap=gap/2;/* 减小增量 */
    }
        cout<<"从小到大排序:";
    for(int k=0;k<n;k++)
    {   
        cout<<R[k].key<<"   ";
    }
    cout<<"\n";
    cout<<"运用希尔排序所需比较次数为："<<comtimes<<endl;
    cout<<"运用希尔排序所需移动次数为："<<moves<<endl;
}

int main()
{   
    srand((unsigned int) time(0));
    int n;
    int *a;
    int c[MAXL],e[MAXL];
    RecType b[MAXL];      
    cout<<"输入你所需要的随机数的个数n:";
    cin>>n;
    a=new int[n];  
    for (int i = 0; i < n; ++i)
    {
        
        for(int j=0;j<n;j++)
        {  a[i] = rand()%100+1;
           b[j].key=a[i];
        }
        printf("%d\n", a[i]);
    }
    return 0;
    int moves=0,comtimes=0;
    shell(b,5,moves,comtimes);
}