Shell（希尔）排序算法详解之C语言版

一、算法原理

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.测试用例
测试用例一：

测试用例二：

测试用例三：