|
#include <stdio.h>
#include <string.h>
#define less(m, n) (m < n)
int a[] =
{
10, 1, 2, 10, 3,
6, 7, 8, 3, 1,
0, 5, 3, 9, 11,
12, 20, 9, 8, 10
};
void sort_print(void)
{
int i;
int len = sizeof(a) / 4;
printf("[ ");
for(i = 0;i <len; i++) printf("%d ", a[i]);
printf("]\n");
}
void sort_shell(int n)
{
int i, j, h;
n -= 1;
printf("----------------------------------------------------------------------\n");
printf(" h-list: [ ");
for (h = 1; h <= n/9; h = 3*h+1) printf("%d ", h);
printf("%d ]\n", h);
printf("----------------------------------------------------------------------\n");
printf(" origin data: ", h);
sort_print();
printf("----------------------------------------------------------------------\n");
for ( ; h > 0; h /= 3)
{
printf("* h-sort when h = %d\n", h);
printf("----------------------------------------------------------------------\n");
for (i = h; i <= n; i++)
{
int j = i;
int v = a[i];
printf("** i = %d", i);
printf(" exch: %d",j);
while (j >= h && less(v, a[j-h]))
{
a[j] = a[j-h];
j -= h;
printf("->%d", j);
}
printf("\n");
a[j] = v;
printf("*** ");
sort_print();
printf("----------------------------------------------------------------------\n");
}
}
printf(" final data: ", h);
sort_print();
printf("----------------------------------------------------------------------\n");
}
int main()
{
int n = sizeof(a) / 4;
sort_shell(n);
return 0;
}
|
