希尔排序:
伪代码:
input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2)
C语言实现:
#include <stdio.h>
#include <stdlib.h>
#define LEN 10 int main()
{
int i, j, temp;
int gap = 0;
int a[] = {10,9,8,7,6,5,4,3,2,1};
while (gap<=LEN)
{
gap = gap * 3 + 1;
}
while (gap > 0)
{
for ( i = gap; i < LEN; i++ )
{
j = i - gap;
temp = a[i];
while (( j >= 0 ) && ( a[j] > temp ))
{
a[j + gap] = a[j];
j = j - gap;
}
a[j+gap] = temp;
}
gap = ( gap - 1 ) / 3;
}
for(i=0;i<LEN;i++)
{
printf("%d\n",a[i]);
}
}