一、算法原理
Shell排序算法是插入排序算法的一种改进算法，即分组插入排序算法，是不稳定排序算法。
其基本原理就是将初始数组按照某一规则分成多个子数组，在每个子数组内进行插入排序，经过多趟这样的分组排序后，即可得到排好序的数组。
为了方便实现分组，引入增量d，即将距离为d的元素组成一个新的子数组，这样也是将原数组分割成d个子数组，在组内进行直接插入排序。当完成一趟排序之后，修改d的值，重复上述操作，直到d取值是1的时候结束整个排序过程。
d的取值往往是相互之间无公因子。当d取值为奇数的时候，就会尽可能减少公因子的出现。
下面给出Shell排序算法的演示过程，其中d的初始值取为数组元素个数除以2，如果此时d是偶数，则d=d-1.
Demo:
第一趟排序：
取d = int( 11 / 2 ) = 5，对从下标为0的元素开始，取相距d的元素为一组，然后再进行组内的直接插入排序。相同颜色的元素为一组，即下标{0,5,10}的元素为一组，{1,6}为一组，{2,7}为一组，{3,8}为一组，{4,9}为一组，即将原数组分成5个子数组。
第二趟排序：
取d=3，即下标{0,3,6,9}的元素为一组，{1,4,7,10}为一组，{2,5,8}为一组，即将原数组分成3个子数组，组内进行直接插入排序。
第三趟排序：
取d=1，即对整个数组进行直接插入排序。此时由于经历过了前面的多趟排序，数组已经接近排序状态，因此对整个数组进行直接插入排序，效率就会提升很多。
至此排序结束。从上述排序过程看，Shell排序的原理很简单，实现也很容易。
二、Shell排序算法之C语言版
1. Shell排序算法
void ShellSort( int arr[], int len )
{
int d, i, j, k, t;
d = int( len / 2 );
if( d % 2 == 0 )
{
d--;
}
while( d >= 1 )
{
for( i = 0; i < d; i++ )
{
for( j = i; j < len; j += d )
{
for( k = j + d; k < len; k += d )
{
if( arr[j] > arr[k] )
{
t = arr[j];
arr[j] = arr[k];
arr[k] = t;
}
}
}
}
d -= 2;
}
}
2.完整的程序
#include"stdio.h"
void ShellSort( int arr[], int len );
int main()
{
int i;
int arr[] = { 9, 13, 8, 2, 5, 13, 7, 1, 15, 11 };
int len = 10;
printf( " Inital array : " );
for( i = 0; i < len; i++ )
{
printf( "%5d", arr[i] );
}
printf( "\n" );
ShellSort( arr, len );
return 0;
}
//Shell排序
void ShellSort( int arr[], int len )
{
int d, i, j, k, t, count;
d = int( len / 2 );
if( d % 2 == 0 )
{
d--;
}
count = 1;
//对不同的d进行分组排序
while( d >= 1 )
{
for( i = 0; i < d; i++ )
{
for( j = i; j < len; j += d )
{
for( k = j + d; k < len; k += d )
{
if( arr[j] > arr[k] )
{
t = arr[j];
arr[j] = arr[k];
arr[k] = t;
}
}
}
}
//向屏幕输出每一趟排序结果：
printf( " No. %d time sort( d = %d ): ", count, d );
for( i = 0; i < len; i++ )
{
printf( "%5d", arr[i] );
}
count++;
printf( "\n" );
d -= 2;
}
}
3.测试用例
测试用例一：
测试用例二：
测试用例三：
