/*
功能:Shell排序算法
思路:对整型数组进行排序的Shell排序算法。 Shell排序算法是D. L. Shell
于1959年发明的,其基本思想是:先比较距离远的元素,而不是像简单交
换排序算法那样先比较相邻的元素。这样可以快速减少大量的无序情况
,从而减轻后续的工作。被比较的元素之间的距离逐步减少,直到减少
为1, 这时排序变成了相邻元素的互换。
该函数中包含一个三重嵌套的for循环语句。最外层的for语句控制两个被
比较元素之间的距离,从len/2开始,逐步进行对折,直到距离为0。巾问层
的for循环语句用于在元素间移动位置。最内层的for语句用于比较各对相
距gap个位置的元素,当这两个元素逆序时把它们互换过来。 山于gap的值
最终要递减到1 ,因此所有元素最终都会位于正确的排序位置上。 注意,
即使最外层for循环的控制变址不是算术级数,for语句的书写形式仍然没
有变,这就说明for语句具有很强的通用性。
{9, 8, 7, 6, 5, 4, 3, 2, 1};未排序状态
{1, 4, 3, 2, 5, 8, 7, 6, 9};len/2 1次,i从len/2到len-1,j从0到len/2 隔4两两1组 gap=len/2
{1, 2, 3, 4, 5, 6, 7, 8, 9};len/2 2次,i从len/4到len-1,j从0到len/4 隔2两两1组 gap=len/4
{1, 2, 3, 4, 5, 6, 7, 8, 9};len/2 3次,i从len/8到len-1,j从0到len/8 隔1两两1组 gap=len/8
作者:Ck018
时间:2015.1.27
修改:
*/
# include<stdio.h>
# include<stdlib.h>
void shell_sort(int src[], int len);
int main(int agrc, char* agrv[])
{
int i;
int src[] = {9, 7, 8, 6, 1, 4, 3, 2, 5};
shell_sort(src, 9);
for (i=0; i<9; i++)
printf("%d", src[i]);
system("pause");
return 0;
}
void shell_sort(int src[], int len)
{
int gap, i, j, temp;
for (gap=len/2; gap>=1; gap/=2)
for (i=gap; i<len; i++)
for (j=i-gap; j>=0 && src[j]>src[j+gap]; j-=gap)
{
temp = src[j];
src[j] = src[j+gap];
src[j+gap] = temp;
}
}