一、算法原理

Shell排序算法是插入排序算法的一種改進(jìn)算法，即分組插入排序算法，是不穩(wěn)定排序算法。
其基本原理就是將初始數(shù)組按照某一規(guī)則分成多個(gè)子數(shù)組，在每個(gè)子數(shù)組內(nèi)進(jìn)行插入排序，經(jīng)過多趟這樣的分組排序后，即可得到排好序的數(shù)組。
為了方便實(shí)現(xiàn)分組，引入增量d，即將距離為d的元素組成一個(gè)新的子數(shù)組，這樣也是將原數(shù)組分割成d個(gè)子數(shù)組，在組內(nèi)進(jìn)行直接插入排序。當(dāng)完成一趟排序之后，修改d的值，重復(fù)上述操作，直到d取值是1的時(shí)候結(jié)束整個(gè)排序過程。
d的取值往往是相互之間無公因子。當(dāng)d取值為奇數(shù)的時(shí)候，就會(huì)盡可能減少公因子的出現(xiàn)。
下面給出Shell排序算法的演示過程，其中d的初始值取為數(shù)組元素個(gè)數(shù)除以2，如果此時(shí)d是偶數(shù)，則d=d-1.
Demo:

第一趟排序：
取d = int( 11 / 2 ) = 5，對(duì)從下標(biāo)為0的元素開始，取相距d的元素為一組，然后再進(jìn)行組內(nèi)的直接插入排序。相同顏色的元素為一組，即下標(biāo){0,5,10}的元素為一組，{1,6}為一組，{2,7}為一組，{3,8}為一組，{4,9}為一組，即將原數(shù)組分成5個(gè)子數(shù)組。

第二趟排序：
取d=3，即下標(biāo){0,3,6,9}的元素為一組，{1,4,7,10}為一組，{2,5,8}為一組，即將原數(shù)組分成3個(gè)子數(shù)組，組內(nèi)進(jìn)行直接插入排序。

第三趟排序：
取d=1，即對(duì)整個(gè)數(shù)組進(jìn)行直接插入排序。此時(shí)由于經(jīng)歷過了前面的多趟排序，數(shù)組已經(jīng)接近排序狀態(tài)，因此對(duì)整個(gè)數(shù)組進(jìn)行直接插入排序，效率就會(huì)提升很多。

至此排序結(jié)束。從上述排序過程看，Shell排序的原理很簡(jiǎn)單，實(shí)現(xiàn)也很容易。

二、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;
//對(duì)不同的d進(jìn)行分組排序
	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;
					}
				}	
			}
		}
		
//向屏幕輸出每一趟排序結(jié)果：		
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.測(cè)試用例
測(cè)試用例一：

測(cè)試用例二：

測(cè)試用例三：