希尔排序详解编程语言

（1）概念：
希尔排序（Shell Sort）的实质是分组插入排序，也称为递减增量排序算法，是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的:
1）插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
2）插入排序是低效的， 因为插入排序每次只能将数据移动一位。

（2）性能分析：
平均时间复杂度：O(nlogn)
稳定性：不稳定

（3）基本思想：
先将这个待排元素序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对整体记录进行一次直接插入排序。

（4）执行步骤为：
1）先取一个小于len的整数h1作为第一个增量，把文件的全部记录分成n1个组。所有距离为h1的倍数的记录放在同一个组中，在各组内进行直接插人排序。
2）取第二个增量h2<h1重复上述的分组和排序，直至所取的增量hn=1(hn<hn-l<…<h2<h1)，即所有记录放在同一组中进行直接插入排序为止。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长串行都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

算法示意图：

（5）特点：
子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。

（6）实现代码：

void ShellSort(int arr[], int len) 
{ 
	int h = len/3;//排序增量 
	while (h > 0) 
	{ 
		//直接插入排序 
		for (int j = h; j < len; j+=h) 
		{ 
			int key = arr[j]; 
			int i = j - h; 
			while (i >= 0 && key < arr[i]) 
			{ 
				arr[i + h] = arr[i]; 
				i-=h; 
			} 
			arr[i + h] = key; 
		} 
		h--; 
	} 
} 

（7）程序：

#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h> 
#include<stdlib.h> 
 
void ShellSort(int arr[], int len) 
{ 
	int h = len/3;//排序增量 
	while (h > 0) 
	{ 
		//直接插入排序 
		for (int j = h; j < len; j+=h) 
		{ 
			int key = arr[j]; 
			int i = j - h; 
			while (i >= 0 && key < arr[i]) 
			{ 
				arr[i + h] = arr[i]; 
				i-=h; 
			} 
			arr[i + h] = key; 
		} 
		h--; 
	} 
} 
 
void test2() 
{ 
	int arr[] = { 40, 30, 60, 80, 70, 10, 20, 40, 50, 05 }; 
	int len = sizeof(arr) / sizeof(arr[0]); 
	ShellSort(arr, len); 
	for (int i = 0; i < len; i++) 
	{ 
		printf("% d", arr[i]); 
	} 
	printf("/n"); 
} 
 
int main() 
{ 
	test2(); 
	system("pause"); 
	return 0; 
} 

运行结果为：

（8）总结
总结一下：如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。