数据结构——希尔排序

文章目录

• 什么是希尔排序呢？
• 代码实现
• 希尔排序的特点

什么是希尔排序呢？

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

其实希尔排序和插入排序非常相似，只不过，希尔排序的间隔是gap。就相当与将数组进行一次预排序，让数组接近有序，我们都知道越接近有序，利用插入排序就越快，可以达到o(n)。

代码实现

1.写出单趟排序，这里和直接插入排序非常相似

int gap = 3;//假设
int end;
int tmp = a[end+gap];
while(end >= 0)
{
	if(tmp<a[end])
	{
		a[end+gap] = a[end];
		end-=gap;
	}
	else
	{
		break;
	}
}
a[end+gap] = tmp;

2.第一组，也就是

int gap = 3;//假设
for(int i = 0; i<n-gap; i+=gap)
{
	int end=i;
	int tmp = a[end+gap];
	while(end >= 0)
	{
		if(tmp<a[end])
		{
			a[end+gap] = a[end];
			end-=gap;
		}
		else
		{
			break;
		}
	}
}

a[end+gap] = tmp;

3.gap组，gap是几就需要分成几组

int gap = 3;//假设
for(int j=0; j<gap; j++)
{
	for(int i = j; i<n-gap; i+=gap)
	{
		int end=i;
		int tmp = a[end+gap];
		while(end >= 0)
		{
			if(tmp<a[end])
			{
				a[end+gap] = a[end];
				end-=gap;
			}
			else
			{
				break;
			}
		}
	}
	a[end+gap] = tmp;
}

4.完成，但也可以不写三层循环

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

a[end+gap] = tmp;

这样写是可以的，自己拿笔在纸上画一下，可以发现gap组数据交替进行插入排序。
5.gap不是只能为3，gap越大越大的数就能更快的到最后，也越不有序，gap越小越接近有序。

void shellSort(int* a,int n)
{
	int gap = n;
	while(gap>1)
	{
		gap=gap/3+1;//为什么要+1呢，控制gap最后一次一定等于1
		for(int i = 0; i<n-gap; i+=gap)
		{
			int end=i;
			int tmp = a[end+gap];
			while(end >= 0)
			{
				if(tmp<a[end])
				{
					a[end+gap] = a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
		}
		a[end+gap] = tmp;
	}
}

希尔排序的特点

• 时间复杂度为o(n^1.3)
• 稳定性：不稳定
• 希尔排序是直接插入排序的优化
• gap>1时都是预排序，当gap==1时，是直接插入排序