#include<iostream>
using namespace std;
#include <stdlib.h>
#include <iostream>
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;
}

void main()
{   
    int a[5]={52,13,38,56,1,2};
    RecType b[10];
    for(int i=0;i<5;i++)
    {
        b[i].key=a[i];
    }
    int moves=0,comtimes=0;
    shell(b,5,moves,comtimes);
}