shell排序：
这个排序的命名是来自发明者的名字，和排序的方法没有字面上的联系。所以不要因为名字而感觉很难。在K&R的C程序设计语言中书中只用了几行代码很简洁的实现了这个排序算法。那就来看看这个排序是如何实现的。
原理：
我们将所要排序的序列（大小为n）划分成组，组的数量一般是可以用这个序列的大小的一半来定义（也就是d = n/2），然后不断折半，而组的成员就是间隔为d的数分为一组。比如这边有个长度为8的数字序列要去排序，那我们就可以先将这个序列分成d=4组的，每个组有两个数，（这边的4就是8的一半）。这四组就是（R1，R5），（R2，R6），（R3，R7），（R4，R8）.然后就是组内比较，如果前者大，交换他们的位置。以次类推。编写程序时就是将我们所取的数和与他间隔为d大小的位置上的数比较。这边第一次组的数量是4，那么就是将第一个数和他间隔为4的数比较。当第一次排序后，我们将这个间隔缩小，就是拿上一次组数d折半。那么这次的组就只有2个了。每个组有4个数.同样是和上面一样，间隔为d=2的位置上的数比较（实际上操作是这样的，但是我们可以认为他们已经是在一个组里面了，就可以说成组内比较）。我们知道d最后会变成1的，那会儿就是相邻的两个数比较，所有的数字都会放在正确的位置上的。原理基本是这样的。
实现：
我们知道了原理，那就用自己熟悉的语言将其编写出来，我们这边是用的C语言，将其编写出来的。
我们按照我们上述的原理将其一步一步的实现下：
1 //函数的参数包含两个，一个是要排序的数组，一个是数组的大小 2 //函数不使用额外的空间，只用到数组本身。这就要求数组在输入时候保留出 3 //R[0],R[0]就相当是一个temp。用于互换两个数时的一个临时数。 4 void shellsort(int R[],intn) 5 { 6 inti,j,d; 7 d = n/2; 8 while(d >= 1) 9 { 10 //注意i的起始和最后的那个“=，我们的第一个数是R[1],所以i-d要从1开始 11 for(i = d + 1;i <= n;i++) 12 { 13 j = i -d; 14 //将R[i]暂存 15 R[0] =R[i]; 16 //这边的R[0]就是R[j+d]也就是R[i] 17 while(j>0 && R[j] > R[0]) 18 { 19 //将j位置的值给j+d位置 20 R[j+d] =R[j]; 21 j -=d; 22 } 23 //这边就是对应着上面的j-=d，如果上面的while执行了，j 24 //位置的值已经给了j+d位置了，那么j+d的值也要给j位置，互换 25 //这就要求下标必须是对应的。所以要将j-d才能满足这边是R[j] 26 //如果while没有执行，那么还将原来的R[i]的值放到原来位置上 27 R[j+d] = R[0]; 28 } 29 //d减半 30 d/=2; 31 } 32 }
上面就是按照所述的原理实现的，代码也不是很多，但是看上去有点乱，那么能不能改进点呢？下面就来了啊。
精简：
我们一般在保证程序的可读上，将程序变得很精巧。这也是K&R的一个思想把。我们知道while和for在一定的情况下是可以替代的。所以我们可以将上述的程序，变得更为紧凑些，我们用三个for循环就可以了。下面是精简后的实现：
1 #include<stdio.h> 2 3 #define N 100 4 void shellsort(int *,int); 5 6 int main(void) 7 { 8 intv[N]; 9 intn,i; 10 11 printf("输入你数组的大小:"); 12 scanf("%d",&n); 13 14 printf("输入%d个数，空格隔开： ",n); 15 for(i = 0;i < n; i++) 16 { 17 scanf("%d",&v[i]); 18 } 19 20 shellsort(v,n); 21 22 printf("shell排序后："); 23 for(i =0;i < n;i++) 24 { 25 printf("%3d",v[i]); 26 } 27 28 printf(""); 29 return 0; 30 } 31 32 void shellsort(int v[],intn) 33 { 34 inti,j,temp,gap; 35 36 for(gap = n/2;gap > 0;gap /=2) 37 for(i =gap ;i < n ;i++) 38 for(j = i - gap;j>=0 && v[j] >v[j+gap]; j-=gap) 39 { 40 temp =v[j]; 41 v[j] = v[j+gap]; 42 v[j+gap] =temp; 43 } 44 }
这边我给出了一个完整的程序，不过我们只看函数的实现。上面的函数中，第一个for循环控制的是被比较数之间的间隔，也可以说是分组的依据。中间的循环是控制元素移动位置的。最后一个循环就是组内的比较，如果顺序不对就交换位置。将第一个函数里面的while整合成了for，这样看起来程序很精简，我们在理解上可能会有些卡壳，如果熟悉while和for之间转换的话就会好很多。
补充：
for(表达式1；表达式2；表达式3)
语句；
等价于while的为：
表达式1；
while(表达式2)
{
语句；
表达式3；
}