插入排序—-希尔排序

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个gap组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

实现

希尔排序是对直接插入排序的一个优化，希尔排序分为预排和正式排序两个阶段，预排是把n个数分成gap组，每个组执行一遍直接插入排序，但是每次end不再是end–或者end+1,而是end-=gap和a[end+gap]=tmp。

gap我们初始给它赋值为n，也就是分成n组，每组一个数，这样的话也服务器托管网就相当于直接插入排序，因为直接插入排序我们是每次挪一个位置和Tmp比较。

for (int i = 0; i = 0)
	{
		if (a[end] > tmp)
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	a[end + gap] = tmp;
}

上述操作也就是把直接插入排序的1换成了gap而已，而这也就相当于gap等于1时候的预排，如果这样操作的话就和直接插入排序没有任何区别，所以我们把gap=n后，第一次预排之前要 gap=gap/3+1；这个操作就是把n个数据分成3组，+1是为了保证让gap不为0,如果gap=2,2/3=0,那分成0组是什么意思？，我把n个数据分成3组进行一次预排，第一次预排之后，每一组肯定都是有序的，这时，gap再进行一次 gap=gap/3+1;也就是再把他划分为更少的组，而我们使gap=gap/3+1，这个加1还有最重要的目的就是一定会使gap=1，所有我们当gap=1时不再往下划分Gap,这个时候就是正式排序

void ShellSort(int* a, int n)//希尔排序
{
	int gap = n;
	while (gap > 1)
	{
		.......
	}				
}

gap越小，分的组越少，预排的结果越接近有序的。当gap>1时，进行的是预排序，当gap==1,进行的是正式排序。这就是希尔排序。

测试

#include
int main()
{
	
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	int n = sizeof(a) / sizeof(a[0]);
	ShelltSort(a, n);
	for (int i = 0; i 

时间复杂度

希尔排序的时间复杂度非常难计算，我们只需要记住它大概在O(N^1.3)左右就可以了。

性能测试

我们使用c语言随机生成的随机数，对这两个排序进行性能测试，我们测试的是1000000个随机数，（由于C语言生成的随机数只能有30000多个，所以我们在每个随机数后面再加上第几次循环的i可以大大减少重复的数据）

#include
#include
#include
srand(time(0));
const int N = 1000000;
int* a1 = (int*)malloc(sizeof(int)*N);
int* a2 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i 

结果如上，由此可以看出，希尔排序无非就是比直接插入排序多了多次预排，直接的差异竟然如此之大。

源代码

void ShellSort(int* a, int n)//希尔排序
{
	int gap = n;
	while (gap &g服务器托管网t; 1)
	{
		gap = gap/3+1;//+1保证最后一次gap为1，也就是进行直接插入排序；gap越小，预排的结果越接近有序
		for (int i = 0; i = 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}				
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 《UNIX网络编程 卷2：进程间通信（第2版）》PDF

内容简介 《UNIX网络编程.卷2：进程间通信(第2版)》是一部UNIX网络编程的经典之作！进程间通信(IPC)几乎是所有Unix程序性能的关键，理解IPC也是理解如何开发不同主机间网络应用程序的必要条件。 《UNIX网络编程.卷2：进程间通信(第2版)》从对…