十大排序 —— 希尔排序

我们今天来看另一个很有名的排序——希尔排序

什么是希尔排序

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，由Donald Shell于1959年提出。它通过比较相距一定间隔的元素来工作，间隔会逐步减小，直到最后变成1，此时算法实际上退化为普通的插入排序，但因为数组元素基本已经部分排序，所以插入排序在这个阶段会非常高效。

希尔排序的基本思想是将原始数据集分割成若干子序列，先使这些子序列基本有序，然后再对全体记录进行一次直接插入排序。这里的"基本有序"是指在子序列内，任意两个元素之间的距离都不超过某个预先设定的间隔（称为"增量"或"gap"）时，它们的顺序要么是正确的，要么仅需很少的比较和移动就可以变得正确。

希尔排序的具体步骤如下：

1. 选择一个增量序列：首先确定一个增量gap，常见的选择有希尔增量（如gap = gap / 2，直到gap = 1），或者使用更复杂的序列如Hibbard增量序列。
2. 分组排序：将整个数组分成多个子序列，每个子序列包含相距gap的元素，然后对每个子序列应用插入排序。
3. 减小增量：重复步骤1和2，但每次减小增量的大小，直到增量为1。
4. 最终排序：当增量减至1时，整个数组就是一个子序列，对这个子序列执行插入排序，这时数组应该是（或接近）完全有序。

希尔排序的优势在于它能够较早地将远处的元素移动到更接近其最终位置，从而减少了数据移动的总次数，提高了排序效率。特别是在数组规模较大时，相比简单的插入排序，希尔排序能显著提高排序速度。希尔排序的时间复杂度依赖于所选的增量序列，最好的情况可以达到O(n log n)，最坏情况则与所选增量序列有关，但通常优于O(n^2)。

再讲希尔排序之前，我们讲一下插入排序。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，适用于对小型数据集合或者基本有序的数据集合进行排序。它的核心思想是将一个记录（或数据元素）插入到已经排序好的有序表中，从而得到一个新的、记录数增加1的有序表。

插入排序的基本步骤如下：

1. 初始化：假设数组的第一个元素已经被排序。
2. 遍历数组：从第二个元素开始，每次取出一个元素（记为key），在已排序序列中从后向前扫描。
3. 比较与移动：如果该元素（key）小于它前面的元素，则将前面的元素向后移动一位，为key腾出位置；否则，停止扫描。
4. 插入元素：将key插入到已排序序列中的适当位置，即找到的正确位置或扫描停止的位置。
5. 重复步骤2-4：对数组中的每个元素都执行这样的插入操作，直到数组完全排序。

插入排序的时间复杂度分析：

• 最好情况：当输入数组已经是排序状态时，插入排序只需要进行n-1次比较，不需要移动数据，时间复杂度为O(n)。
• 最坏情况：当输入数组是反序时，每次插入都相当于在数组的最前面插入，每次插入操作需要移动所有的已排序元素，时间复杂度为O(n^2)。
• 平均情况：对于随机数据，插入排序的时间复杂度也是O(n^2)。

插入排序的空间复杂度为O(1)，因为它是一种原地排序算法，除了输入数组外，只需要常数级别的额外空间用于交换和临时存储。此外，插入排序是稳定的排序算法，即相等的元素的相对顺序不会改变。

画个图就是这样的：

// 选择插入排序函数实现
void select_sort(int *array, int size)
{
    // 遍历整个数组，除了最后一个元素（因为它自然有序）
    for (int i = 0; i < size - 1; i++)
    {
        // 选取当前位置i+1的元素作为待插入元素
        int temp = array[i + 1];

        // 初始化"已排序"部分的最后一个元素索引
        int end = i;

        // 当"已排序"部分的索引大于等于0时进入循环
        while (end >= 0)
        {
            // 如果"已排序"部分的当前元素大于待插入元素
            if (array[end] > temp)
            {
                // 将较大的元素向后移动一位，为待插入元素腾出空间
                std::swap(array[end + 1], array[end]);
                // 缩小"已排序"部分的范围，继续向前比较
                end--;
            }
            else
            {
                // 如果当前元素不大于待插入元素，说明找到了temp的正确位置
                // 或者已经检查到数组起始，此时无需再比较，直接跳出循环
                break;
            }
        }
        
    }
    // 循环结束，数组完成排序
}

int main()
{
	int array[] = { 1,34,56,1,233,56,0 };

	for (auto e : array)
	{
		std::cout << e << " ";
	}

	std::cout << std::endl;

	select_sort(array, sizeof(array) / sizeof(array[0]));

	for (auto e : array)
	{
		std::cout << e << " ";
	}
}

大家可以画个图，结合着图能比较清晰理解。

希尔排序

我们已经了解到了希尔排序的特殊形式直接插入排序，现在我们来了解一下更一般的形式=希尔排序。
我们之前用直接插入排序来让数据升序排列，我们来考虑一下它最糟糕的情况：数据是降序排序的。

这样的话，9之后的数据都要进行一次插入，插入到9之前，时间复杂度可以达到O(N2)，但我们会遇到这样一种情况：

10比9大故不用进行插入了，而我们可不可以让这种情况更普遍一些呢？所以我们可以在进行排序之前，先进行一次预排序，让数据整体是升序的，这就是希尔排序。

希尔排序的步骤：

1. 将数据分成gap组。
2. 以gap为间隔进行直接插入排序。

//希尔排序
void ShellSort(int* a, int n)
{
	assert(a);
	int gap = 3;
	for (int i = 0; i < n - gap ; i+=gap)
	{
		int end = i;
		int temp = a[end + gap];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				std::swap(array[end + gap], array[end]);
				end-=gap;
			}
			else
			{
				break;
			}
		}
	}
}

这段代码的结果是什么样的呢？我们来画图看看：

其实我们只完成了一组红色数据的预排序，其实我们的预排序可以不止一组：

那么如何完成这三组的排序呢？很简单，加一层for循环。

//希尔排序
void shell_sort(int* array, int size)
{
	int gap = 3;

	for (int j = 0; j < 3; j++)
	{
		for (int i = j; i < size - gap; i += gap)
		{
			//后面一个待排元素
			int temp = array[i + gap];
			int end = i;

			while (end >= 0)
			{
				if (array[end] > temp)
				{
					std::swap(array[end + gap], array[end]);
					end-=gap;
				}
				else
				{
					break;
				}
			}
		}
	}

}

我们看看程序结果怎么样：

我们发现数据的排序是有一些变化，但好像还是有点混乱，这是因为gap的原因，这时候我们把gap改为2看看：

我们发现gap越大，数据排序越混乱，但移动的越快，**gap越小，数据越有序，但移动的越慢**这直接和时间复杂度有关。

// 希尔排序函数实现
void shell_sort(int* array, int size)
{
    // 初始化间隔(gap)为数组的长度
    int gap = size;

    // 当间隔大于1时，持续执行以下步骤，逐步减小间隔以达到排序效果
    while (gap > 1)
    {
        // 计算新的间隔，这里使用的是一个简化的规则，将间隔除以3并加1，这是一种常用的递减策略
        gap = gap / 3 + 1;

        // 这个循环是为了处理不同子序列的起始位置，确保每个间隔下的元素都能被遍历到
        for (int j = 0; j < gap; j++)
        {
            // 遍历数组，从当前子序列的起始位置开始，步长为当前的间隔
            for (int i = j; i < size - gap; i += gap)
            {
                // 保存当前间隔位置的下一个元素，准备进行插入排序
                int temp = array[i + gap];
                int end = i;

                // 内部循环实现插入排序逻辑，将temp插入到已排序的子序列中正确的位置
                while (end >= 0)
                {
                    // 如果当前子序列中的元素大于temp，将该元素后移
                    if (array[end] > temp)
                    {
                        std::swap(array[end + gap], array[end]); // 交换元素
                        end -= gap; // 移动到前一个位置继续比较
                    }
                    else
                    {
                        // 如果找到了temp的正确位置或已经比较到子序列的起始位置，跳出循环
                        break;
                    }
                }
            }
        }
    }

    // 当所有间隔遍历完成后，数组已经基本排序完成，由于最后一次gap为1，实质上进行了最后一次的插入排序收尾
}

其实这段代码还有一个变形，也可以达到效果：多组并排

//希尔排序
void shell_sort(int* array, int size)
{
	int gap = size;

	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < size - gap; i ++)
		{
			//后面一个待排元素
			int temp = array[i + gap];
			int end = i;

			while (end >= 0)
			{
				if (array[end] > temp)
				{
					std::swap(array[end + gap], array[end]);
					end -= gap;
				}
				else
				{
					break;
				}
			}
		}
	}
}

递归版本

这里实现递归版本完全是为了锻炼思维，实际中不会这样写，仅供参考：

void select_sort(int* array, int size, int index)  
{  
	// 如果index小于0，递归结束  
	if (index < 0)  
		return;  
  
	// 递归调用，先对前面的部分进行排序  
	select_sort(array, size, index - 1);  
  
	// 如果index已经是最后一个元素（或者超过最后一个元素的索引），则不需要再进行排序  
	if (index >= size - 1)  
		return;  
  
	// 临时存储index+1位置的元素，这个元素可能是当前未排序部分的最小值  
	int temp = array[index + 1];  
	int end = index; // 从index位置开始向前比较  
  
	// 这是一个插入排序（Insertion Sort）的插入过程，但逻辑上不适合选择排序  
	while (end >= 0)  
	{  
		// 如果当前元素比temp大，则将当前元素后移  
		if (array[end] > temp)  
		{  
	 
			std::swap(array[end], array[end + 1]);  
			end--;  
		}  
		else  
		{  
			// 如果找到合适的位置，或者已经到达数组的开头，就跳出循环  
			break;  
		}  
	}  
  
}

希尔排序：

// 递归实现的插入排序，用于希尔排序中每轮的细分排序
void select_sort(int* array, int size, int index, int gap)
{
    // 递归基础情况：当索引小于0时，说明已处理完当前gap下的所有元素
    if (index < 0)
        return;

    // 递归调用，处理当前元素前一个gap位置的元素，逐步向前
    select_sort(array, size, index - gap, gap);

    // 防止数组越界，当索引达到size-gap时，说明当前gap下已无更多元素需要处理
    if (index >= size - gap)
        return;

    // 保存当前gap位置的元素值，准备进行插入排序
    int temp = array[index + gap];
    int end = index;

    // 插入排序逻辑，将temp插入到前方已排序的子序列中的正确位置
    while (end >= 0)
    {
        if (array[end] > temp)
        {
            // 交换元素，将较大的元素后移，为temp腾出位置
            std::swap(array[end + gap], array[end]);
            end -= gap; // 更新索引，继续向前比较
        }
        else
        {
            // temp已到达或超过其正确位置，停止循环
            break;
        }
    }
}

// 实现希尔排序的主体函数，使用递归的select_sort进行每一轮的细分排序
void shell_sort(int* array, int size, int index)
{
    int gap = size;

    // 循环直到gap减至1，每轮使用一个较小的gap进行插入排序
    while (gap > 1)
    {    
        // 计算下一轮的gap值，这里采用gap = gap / 3 + 1是一种常见但非唯一的策略
        gap = gap / 3 + 1;
        
        // 使用当前gap值调用select_sort进行插入排序
        select_sort(array, size, index, gap);
    }
}