排序算法 —— 希尔排序

希尔排序是对直接插入排序的优化。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，我们一半去O(N^1.3)。希尔排序并没有开辟额外的空间，空间复杂度为O(1)。希尔排序是不稳定的

@阿超要努力

4020人浏览 · 2024-10-21 16:25:06

@阿超要努力 · 2024-10-21 16:25:06 发布

1.希尔排序的由来

希尔排序是对直接插入排序的优化。在直接插入排序算法中，如果数据是有序or接近有序的时候，直接插入排序算法的时间复杂度是O(N)，因为每次选取的待排序元素不需要经过太多次的比较，就能插入到有序序列中。

所以希尔排序的发明者就想，如果能把待排序序列快速的变得接近有序，那么直接插入排序不就能得到优化了吗？

2.希尔排序的思想

希尔排序的思想就是先对序列中的元素进行间距分组，先把分出来的这些组进行插入排序，然后缩小间距，再进行分组，在进行插入排序，当间距缩小为1的时候，此时就是直接插入排序。所以，希尔排序又叫缩小增量排序。

希尔排序分为两步：预排序和直接插入排序。在间距大于1的时候所进行的排序叫做预排序，当间距等于1的时候进行的排序就是直接插入排序。

预排序的意义：

大的数据越快的跳到后面去，小的数据越快的跳到前面去。

间距越大，数据跳的越快，数据越不接近有序。

间距越小，数据跳的越慢，数据越接近有序。

值得注意的是：当间距为几的时候，数据就被分成了几组。

3.希尔排序的实现

实现分析

想要实现希尔排序，我们先分析清楚如何实现一趟排序，就拿下面这个例子来说，我们先看红色的这一组。

红色的这一组之间的间距是3，我们类比直接插入排序，直接插入排序可以看做间距为1，所以我们只需要对直接插入排序稍微修改即可得出单趟排序的代码。

在上面右侧的代码中最外围的变量 i 控制的是一组中的元素下标，当这层循环走完之后，说明完成了一组数据的排序，但是我们需要完成的是分出的所有组的排序。在讨论希尔排序的思想的时候，我们发现，数据之间的间距是多少，数据就被分成了几组，所以，还需要在外面再加一层循环控制排序的数据是第几组的数据。

代码如下：

在前面我们也讨论过，希尔排序的间距是需要变化的，并且是变小的，而且，间距最后必须为1，所以，我们先将间距设置为待排序数据个数的一半，然后逐渐缩小一半。所以还需要再加一层循环控制间距。

代码如下：

实现代码

#include <stdio.h>

void ShellSort(int* nums, int n)
{
	int gap = n;

	while(gap > 1)
    {
        gap /= 2;
        for(int j = 0; j < gap; j++)
        {
            for(int i = j; i < n-gap; i += gap)
            {
                int end = i;
                int tmp = nums[end+gap];
                while(end >= 0)
                {
                    if(tmp < nums[end])
                    {
                        nums[end+gap] = nums[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                nums[end+gap] = tmp;
            }
        }
    }
}

int main()
{
	int nums[] = {5,1,2,4,6,3,8,9,7,0};
	ShellSort(nums,10);
	
	int i = 0;
	while(i < sizeof(nums)/sizeof(int))
	{
		printf("%d ",nums[i]);
		i++;
	}
	
	
	return 0;
}

代码优化

在上面的代码中，我们是将数据分成多组之后，然后一组排完之后再排另一组。其实，这多组数据是可以同时排的，也就是多组并排。

优化方案：1.去掉控制排第几组数据的循环。2.将枚举一组中待排序的数据修改为枚举所有组中待排序的数据。

代码示例如下：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		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;
		}
	}
}