数据结构初阶之插入排序与希尔排序详解

个人主页：点我进入主页

专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶    Linux

欢迎大家点赞，评论，收藏。

一起努力,共赴大厂。

目录

一.前言

二.插入排序

2.1插入排序的思想

2.2代码实现

三.希尔排序 

3.1希尔排序的思想

3.2代码实现

四.总结

一.前言

        时隔一个多月，我终于回来了。这段时间里，由于一些不可避免的原因，我没有能够抽出时间来撰写文章。但是今天，我非常激动地给大家带来了一些全新的内容，其中包含了插入排序和希尔排序的相关主题。在这一个月的沉淀中，我对排序算法进行了深入的学习和实践，通过对插入排序和希尔排序的研究，我深刻领悟到它们在算法设计中的重要性。这两种排序算法不仅在理论上有着独特之处，而且在实际应用中也展现出强大的性能。对于插入排序而言，它的简单直观的思想使得它成为初学者入门的良好选择。通过逐步地将元素插入已排序的序列中，我们可以在每一步保持部分有序性，从而最终得到完全有序的结果。这种排序算法的易懂性使得它在教学和基础应用中广受欢迎。而希尔排序则是一种更为高级的排序算法，它通过引入间隔序列的概念，能够在一开始就以较大的步长对数据进行排序，然后逐步减小步长，最终实现全局有序。这种分阶段的排序思想使得希尔排序在大规模数据上表现出色，相对于简单的插入排序，它更具有高效性。

二.插入排序

2.1插入排序的思想

’        我们先针对插入排序的某一次循环，我们让前end个元素有序，我们针对第end+1的元素进行插入排序，如果前面的元素大于这个元素我们就让它往后移动，直到出现小于它的元素，这样第一层循环就好了，我们接下来写所有的排序，我们直到前end个元素有序，所以我们针对前end个元素进行，让end先为0，然后让end加加，直到end小于n-1，但是我们不能直接把end方在循环条件，我们可以看下面的图片，来感受一线插入排序。

在这张图片中我们可以深刻感受到插入排序的过程，更详细的感受到插入排序的方法。

2.2代码实现

void InsertSort(int* a, int n)
{
	for(int i=0;i= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

我们任意选择一趟排序，例如针对这一趟排序，我们的tmp存储了3，end指向9，

首先我们先让9和3进行比较，9大于3，我们让9向后进行移动，然后end--；

 我们继续进行比较最后我们可以得到

三.希尔排序 

3.1希尔排序的思想

        希尔排序的关键在于确定初始的 gap 值，然后在每一轮迭代中逐步减小 gap。一般来说，初始的 gap 可以选择数组长度的一半，然后每轮迭代将 gap 除以 3+1，直到 gap 缩小为 1。 希尔排序的性能相对于简单的插入排序有较大的提升，尤其是对于中等大小的数组。这是因为希尔排序在每一轮迭代中都会对距离较远的元素进行比较和交换，从而减少了插入排序中需要移动的元素的数量。 然而，希尔排序并不是稳定的排序算法，即相同元素的相对位置在排序前后可能会发生变。这是因为希尔排序的排序过程是基于比较和交换的，而不是简单的元素移动。我们可以展示一下gap为5的动图。

3.2代码实现

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

我们针对gap=4时进行讲解，我们进行分组， 

 进行循环，end为0，tmp为4，进入第一次交换，可以得到

 我们的思想和插入排序一样，希尔排序就是插入排序的进阶。对于希尔排序的时间复杂度为nlogn;

四.总结

        希尔排序的主要思想是通过比较和交换不相邻的元素，从而使得数据项能够更快地移动到正确的位置。这种分段的插入排序策略可以有效地减小序列的无序程度，提高整体的排序效率。希尔排序的性能与所选取的间隔序列有关。一些常见的间隔序列包括希尔增量和序列9、5、3、2、1等。不同的间隔序列可能导致不同的性能表现，因此在实际应用中，选择适合特定情况的间隔序列是重要的。希尔排序的优点包括：相对于简单的插入排序，希尔排序对于中等大小的数据集表现更好。相对于一些其他复杂的排序算法，希尔排序的实现相对简单。然而，需要注意的是，希尔排序并不稳定，即相等元素的相对顺序在排序后可能发生改变。总体而言，希尔排序是一种在实际应用中被广泛使用的排序算法，尤其在需要对中等大小数据集进行排序时，它的性能表现相对较好，最后希望大家可以一件三连。