/* shell排序的算法源程序 */

#include<stdio.h>

#define MAXNUM 100
typedef int KeyType;
typedef int DataType;

typedef struct {
    KeyType key;       /* 排序碼字段 */
    /*DataType info;           記錄的其它字段 */
} RecordNode;

typedef struct {
    int n;               /* n為文件中的記錄個數，n<MAXNUM */
    RecordNode record[MAXNUM];
} SortObject;

void  shellSort(SortObject * pvector, int d) {	/* 按遞增序進行Shell排序 */
    int i, j, inc; 
    RecordNode temp, *data = pvector->record;
    
    for (inc = d; inc > 0; inc /= 2) {
        /* inc 為本趟shell排序增量 */
        for (i = inc; i < pvector->n; i++) { 
            temp = data[i];          	/* 保存待插入記錄Ri*/ 
            for (j = i-inc; j >= 0 && temp.key < data[j].key; j -= inc)
                data[j+inc] = data[j];	/* 查找插入位置，記錄后移 */
            data[j+inc] = temp;			/* 插入記錄Ri */
        }
    }
}


SortObject vector={8,49,38,65,97,76,13,27,49};

int main(){
    int i;
    shellSort(&vector,4);
    for(i=0;i<8;i++)
        printf("%d ",vector.record[i]);
    getchar();
    return 0;
}