排序（1）——直接插入排序、希尔排序

一、直接插入排序

1.简介

2.思路与代码

3.复杂度与稳定性分析

（1）时间复杂度

（2）空间复杂度

（3）稳定性

二、希尔排序

1.简介

2.思路与代码

（1）分组排序

（2）多组并排

3.复杂度与稳定性分析

（1）时间复杂度

（2）空间复杂度

（3）稳定性

为了追求生产生活的便捷与秩序，我们常常需要对一系列的对象进行排序处理，排序在我们生活中无处不在。在C语言中面对众多的数据，众多优秀的程序员们发明了许多不同思想，不同方法的排序算法。我们今天所要接触到的就是其中之二：直接插入排序与希尔排序。

注：本文以升序为例

一、直接插入排序

1.简介

顾名思义，直接插入排序就是将数据直接插入到顺序之中。详细而言就是面对一个数组，假定某一位置之前的元素已经有序，需要将该元素也排入顺序之中，那么就需要这个元素与之前的顺序序列一一比较，找到其合适的位置插入进去。

2.思路与代码

在写排序算法的时候，最重要的是要明确单趟排序的思路，因为整体排序实际就是很多个单趟排序的不断重复。所以只要我们写出了单趟排序，把它丢进循环里，调整一下每一次排序的变量即可。

对于一个数组a，它具有n个元素。对于任一元素下标end，假设[0,end]已经有序，我们所要完成的就是将下标为end+1（即有序序列后一个）的元素插入到有序序列对应的位置，使得有序范围变为[0,end+1]。对此我们需要将所需要插入的元素与有序序列从后往前一一比较，如若小于所比较的元素则证明应该插入在它的左边部分，那么就继续迭代与下一个位置比较；否则直接插入右边位置即可。

    //单趟排序	

    //[0,end]已经有序，将end+1插入有序数组内
	int end
	int	tmp = a[end + 1];
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + 1] = a[end];
			end--;
		}
		else
		{
			break;
		}
	}
	a[end + 1] = tmp;

那么对于整体而言，我们只需要采用循环的方式，将end从0开始，排到end成为最后一个元素为止。初值end=0，[0,0]单个元素有序；排完end=end-2这次循环后，end自增为n-1，说明[0,n-1]有序，即所有元素已经有序，就可以停止了。

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//[0,end]已经有序，将end+1插入有序数组内
		int end = i;
		int	tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

3.复杂度与稳定性分析

（1）时间复杂度

插入排序是从一个到多个的顺序扩展，其时间复杂度的主要贡献者是插入过程中寻找位置的过程。

最差情况就是数组逆序的情况，此时每一次插入都需要完整地遍历之前的有序序列，所以此时的时间复杂度就是标准的等差数列求和，所以是 $O(n^2)$ 。

最佳情况下，就是数组顺序的情况下，此时无需任何交换，对每个元素只需比较一次就确定了位置，所以相当于遍历了一遍数组，时间复杂度是 $O(n)$ 。

（2）空间复杂度

插入排序并未用到多余额外的空间，所以空间复杂度是 $O(1)$ 。

（3）稳定性

插入排序是稳定的。

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

插入排序在排序过程中因为是依次取元素向前排的，只要保证在相等时end位置不向后挪动，即可确保相对位置不变，算法也就稳定了。

二、希尔排序

1.简介

希尔排序是由DL．Shell于1959年提出，因而被命名为希尔排序。希尔排序可以看作是插入排序的升级版，它对插入排序取长补短。因为插入排序处理有序序列效率很高，而处理逆序序列效率很低，所以希尔采取预排序的方法，将数组用较低的代价排列成为接近有序的状态，再使用插入排序完成最后的排序，这样的方法使得排序的效率相较于插入排序有了巨大的飞跃。

2.思路与代码

对于希尔排序，我们所需要重点解决的就是其预排序部分的实现，希尔排序在预排序中要求以gap为间隔进行预排序，即每隔gap个位置的元素称为一组，将这些组互不相干地分别进行插入排序。由于一次交换的发生在距离为gap的两个元素之间，因而使得较大元素更快被换到后方，而较小元素也更快换到前方。

对于一个无序数组啊a，假定本次预排序gap为3。

首先进行分组，将下标为0+n*3的元素视为一个组，另外两组下标为1+n*3和2+n*3，即每一组是下标加减gap的关系。我们这里说视为是因为并未为它们新开空间进行存放，只是我们人为将其主观划为三组，实际上其还是存在原数组中。这样理解比较方便，只是需要写代码的时候清楚注意到就好。

下一步将三组分别进行插入排序，保证三组分别有序。

最后放到原数组，这里说放回也是便于理解，同样地我们是在原数组中主观意识划分下的处理，分别排序这一步就是在原数组中进行调整，并不存在“放回”这一步。

（1）分组排序

这种方案比较符合我们的认知逻辑，因为gap是间隔的距离，所以我们可以知道需要排序的组数也就是gap组，每组对应的首元素也就是前gap个元素，所以我们可以循环gap次来对每一组分别进行插入排序。

直接插入排序的代码无需解释了，只是有一点改动。因为现在处理的是间隔为gap的一组数据，所以原先插入排序的调整（如end等）应该每次调整gap。

除此之外，还需要补充的一点是gap的选取。当gap选的过小时，与直接插入排序区别不大开销会变大；如果选的过大则难以很好的实现“重沉轻浮”的目标。所以动态的gap才是好gap，gap先很大，尽快区分出数据，然后逐渐变小，进行细化。gap = gap / 3 + 1是业界普遍认定的比较好的选择，具体原因等我学会再告诉你们（略略略）。无论gap如何选取，我们都应该知道gap最后一步应该是1，这样相当于最后一步的直接插入排序，完成后才能宣告结束，所以gap的递推关系要满足使得gap递减，并且可以到达1。

void ShellSort(int* a, int n)
{
	//预排序

	//int gap = 3;
	int gap = n;
	//gap>1时是预排序
	//gap==1时是直接插入排序
	while (gap > 1)
	{
		//gap在循环中应该递减为1
		//gap = gap / 2;  //gap/2最后都可以到达1
		gap = gap / 3 + 1; //对gap除以3，商可能是任意整数并且一定比被除数小，即gap是递减的
		//对于gap/3循环，gap是有可能不经过1而直接到达0的，所以需要加1确保gap一定可以到达1
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)//i作为坐标预处理数组元素下标
			{
				int end = i;//前end个元素已经有序
				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;
			}
		}
	}
}

（2）多组并排

多组并排和分组排序采取的思路一致，只是代码写法上有所不同。分组排序代码呈现与我们理解希尔排序的方式相同，而多组并排的代码呈现则是将其中两层循环合并起来了。因为原来代码每个组分别遍历自己的组员，每个组员的处理方式也都是一样的，这实际上就是遍历了整个原数组，所以多组并排就是遍历一遍原数组，遍历到不同的组员采取一样的处理方式。

void ShellSort2(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 cmp = a[i + gap];
			while (end >= 0)
			{
				if (cmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = cmp;
			}
		}
	}
}