八大排序(希尔排序)

2023-12-16 15:48:04

上篇文章我们来看了看插入排序是怎么实现的,本章内容就是在插入排序的基础上完成希尔排序,希尔排序是一个比较强大的排序,我们希尔排序的时间复杂度是比较难算的,这里直接给出的结论就是时间复杂度就是O(N^1.3),比较难算的原因就是我们每一次的次数都是会在变得,算起来不太方便。

?

这个就是希尔排序的动图,我们也是可以看到我们的希尔排序,但是图中的希尔排序gap是每次变化gap/2 还有一个也可以写成gap/3+1,我们gap == 1的时候就是插入排序了。我们可以来看看我们希尔排序的代码。

?

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int key = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > key)
					{
						a[end + gap] = a[end];
						end = end - gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = key;
			}
		}
		
	}

}

还可以写成下面的这个样子。

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		int j = 0;
		while (j < gap)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int key = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > key)
					{
						a[end + gap] = a[end];
						end = end - gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = key;
			}
			j++;
		}

	}

}

两种方式都可以。大家多看动图和调试然后看代码写吧,排序真的有点难讲。

文章来源:https://blog.csdn.net/2301_76895050/article/details/135032150
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。