一、算法原理

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.測試用例
測試用例一：

測試用例二：

測試用例三：