排序算法之插入排序（探秘直接、希尔之间谁更快）_希尔排序为什么比直接排序速度快

他日卧龙终得雨

今朝放鹤且冲天

---

 

CSDN 请求进入专栏                                            是否进入《C++专栏》? 确定

 

---

排序的概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增 或 递减 的排列起来的操作。

排序稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序

数据元素全部放在内存中的排序。

外部排序

数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

---

目录

插入排序的概念

直接插入排序

算法思想

算法实现

排序原理

特性总结

希尔排序 

算法思想

排序原理

排序原理

算法实现

特性总结

插入排序的概念

插入排序分为两类：直接插入排序、希尔排序

直接插入排序

对于直接插入排序，我想大家都很熟悉，例如我们玩的扑克，洗牌时就运用了直接插入排序

算法思想

把 待排序 的记录按其关键码值的大小 逐个插入 到一个已经排好序的 有序序列 中，直到所有的记录插入完为止，得到一个新的有序序列 。

例如：对于一组将要排序的数据，我们应该从 前往后遍历 ，遍历到的数据我们就与前面排好序的数据进行比较。我们以 升序 为例，若当前数据比前面的数据小就要两者交换，如果再比前面的数据还小就继续进行交换直到数据有序为止，下面呈上动图以便老铁们理解。

当插入第 i (i>=1) 个元素时，前面的 array[0]，array[1] … array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1]，array[i-2] … array[0] 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移

算法实现

（以升序为例）

void InserSort(int* a, int n)          // a数组的首地址，n数组要排序的元素个数
{
	for (int i = 0; i < n - 1; i++)    // 从数组的第一个元素开始遍历无序数据
	{
		int end = i;                  
		int tmp = a[end + 1];          // 临时存储待排数据
		while (end >= 0)             
		{
			if (a[end] > tmp)          // 待排数据与前面的有序数据进行比较
			{
				a[end + 1] = a[end];   // 待排数据小于有序数据就在合适位置交换
				--end;
			}
			else
			{
				break;                    
			}
		}
		                              // 走到这里分两种情况，待排数据比有序数据都大或者都小 
		a[end + 1] = tmp;             // 直接插入就可以了
	}
}

排序原理

在 [0，end] 区间插入 tmp ，先比较 tmp 与 end 的大小关系，如果比 end 小，那么将 end 往后面挪一个，在用 tmp 和 end-1 比较，如果比 end-1 小，再将 end-1 往后挪，直到 tmp 比 [0,end] 区间中那个元素大，那么就停止，如果 tmp 比这个区间的所有数都要小，那么直接将tmp放在第一个位置。

代码测试

特性总结

<1>元素集合越接近有序	直接插入排序算法的时间效率越高
<2>时间复杂度	O(N^2)
<3>空间复杂度	O(1)
<4>稳定性	它是一种稳定的排序算法

希尔排序 

算法思想

希尔排序是对直接插入排序的 优化 ：

若面对这样一组数据 arr[ ] = {9,8,7,6,5,4,3,2,1} 按升序排序，如果使用直接插入排序的话时间复杂度为 O(N^2) ，为了提高代码效率，我们会对原数据 进行预排 ，这就是希尔排序。

排序原理

其实希尔排序就是将数据 分组 ，在每个组内进行 直接插入排序

那么如何分组呢？

设置一个增量序列，开始的增量通常是数组长度的一半，然后下一次增量减半，增量设为gap

假设有一组｛9, 1, 2, 5, 7, 4, 8, 6, 3, 5｝按　升序　排序

N即数组个数：１０

第一趟排序： 设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。

第二趟排序： 将上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为2组。按照直接插入排序的方法对每个组进行排序。

第三趟排序： 再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为1的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

注：需要注意一下的是，图中有两个相等数值的元素5和5。我们可以清楚的看到，在排序过程中，两个元素位置交换了。

---

下面呈上动图以便老铁们理解：

排序原理

希尔排序法又称 缩小增量法 ：

先选定一个整数 gap ，把待排序文件中所有记录分成几个组，所有距离为 gap 的记录分在同一组内，并对每组使用直接插入排序算法排序。然后取重复上述分组和排序的工作。

当 gap 减至 1 时，所有元素在统一组内排好序，算法便终止。

算法实现

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		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;
		}
	}
}

代码测试

特性总结

<1>当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

<2>希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定。

时间复杂度情况如下：（n指待排序序列长度）
(1)最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即 O(n)
(2)最坏情况：O(nlog2n)
(3) 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

因此希尔排序在效率上较直接插入排序有较大的改进

<3>希尔排序的空间复杂度 O(1) 。

<4>由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是 不稳定 的。