希尔排序(shellsort)又叫增量递减(diminishing increment)排序
是由D.L. Shell发明
这个算法是通过
个逐渐减小增量使个
逐渐趋近于有序从而达到排序目
假设有
个
data[16] = {...} 首先将这个增量设为16 / 2 = 8这样就将这个分成了8个子它们索引是0, 8 1, 9 2, 10等等 对这些子进行排序然后再使增量为8 / 2 = 4这样就将原分成了4个子它们索引分别是0, 4, 8, 12 1, 5, 9, 13等等再对这 4组数进行排序直到增量为1以上所描述
增量递减只是种思路方法这种思路方法并不是最有效率如f(n) = 3 * f(n - 1) + 1 f(1) = 1 (..., 121, 40 13, 4, 1)就比上面取增量思路方法好这种思路方法时间复杂度是O(n ^1.5)算法如下
#
<stdio.h>void output_
data
, n){
i;for(i = 0; i < n; i
)pr
f("%d ", data[i]);pr
f("\n");}
void swap(
*a, *b){
x;x = *a;
*a = *b;
*b = x;
}
void insertion_sort(
data, n, increment){
i, j;for(i = increment; i < n; i
increment)for(j = i; j >= increment && data[j] > data[j - increment]; j -= increment)
swap(&data[j], &data[j - increment]);
}
void shellsort(
data, n){
i, j;for(i = n / 2; i > 2; i /= 2)
for(j = 0; j < i; j
)insertion_sort(data + j, n - j, i);
insertion_sort(data, n, 1);
}
{
data = {5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6};output_
shellsort(data, 12);
output_
0;}
最新评论