数据结构-插入排序+希尔排序+选择排序

1.插入排序

插入排序的时间复杂度：

2.希尔排序

希尔排序的时间复杂度：

3.选择排序

选择排序的时间复杂度：

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序在生活中的作用很大，例如：某宝中的价格排行榜、销量排行榜，国内外的财富排行榜、院校排行榜等等，都是使用排序完成的。

下面我们看看常见的排序都有哪些：

1.插入排序

基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中我们玩扑克牌时，就用了插入排序的思想：

插入排序的过程如下：

假设我们有如下一个数组：

具体实现代码如下：
while (end >= 0)
{
    //挪数据
	if (tmp < a[end])
	{
		a[end + 1] = a[end];
		end--;
	}
	else
	{
		break;
	}
}
//交换数据
a[end + 1] = tmp;
tmp中存放的是3，3小于10，10往后挪一位，3小于5,5往后挪一位......当end到2时，tmp小于2，退出循环，此时5 7 10都已经往后挪了一位，数组中的元素应该是：2 5 5 7 10，我们把tmp中存放的3和2后面的5交换即可。

以上只是一个数据的插入排序，要实现整个数组的排序，我们需要对数组的每个数据都往前插入排序一下：
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

插入排序的时间复杂度：

假设我们要排升序，当要排的数据刚好是降序时，时间复杂度最大，为O(N^2)，因为此时排序的次数是等差数列。

当要排的数据刚好是升序的时候，是最好的情况，时间复杂度最小，但是我们在排之前并不知道数据是升序，所以至少要排N次，时间复杂度为O(N)。

总结一下：

时间复杂度（最好）：O(N^2)

时间复杂度（最坏）：O(N)

而我们之前学过的冒泡排序，时间复杂度是O(N^2)，所以插入排序优于冒泡排序。

2.希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有数据分成n/gap个组，所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序，最后再进行一次gap=1的分组和排序。

希尔排序有两个过程：

1. 预排序 -- 使接近有序。

2. 插入排序

即先进行预排序是数据接近有序，然后使用一次插入排序，使数据有序。希尔排序实际就是对插入排序的优化。

预排序：

下面我们先来对红色组进行排序：
for (int i = 0; i < n - gap; i+=gap)
{
	int end = i;
	int tmp = a[end + gap];
	while (end >= 0)
	{
		if (tmp < a[end])
		{
			a[end + gap] = a[end];
			end = end - gap;
		}
		else
		{
			break;
		}
	}
	a[end + gap] = tmp;
}
注意下标 i 不能越界，所以 i < n - gap。

以上代码只能完成对红色组的排序，下面我们来将三个组都排好序：

只需在外面再加一层循环即可。
for (int j = 0; j < gap; j++)
{
	for (int i = j; i < n - gap; i += gap)
	{
		int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
						end = end - gap;
				}
				else
				{
					break;
				}
			}
		a[end + gap] = tmp;
	}
}
这样三组数据都排好序，完成了预排序，但是上述代码有似乎还可以简化：
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 = end - gap;
		}
		else
		{
			break;
		}
	}
	a[end + gap] = tmp;
}
只需将i+=gap，改为i++即可，当i+=gap时，我们是将三组分开排序的，先排完红色组，再排蓝色组，最后排绿色组，而当i++时，我们是多组并排的方式，这样明显效率更高。

插入排序：

以上就是预排序的过程，预排序完，数据变成了：1 02 3 3 4 6 5 7 9 8，还需要一次插入排序，现在我们先来思考一个问题，gap的值只能给3吗？

当然不是，gap可以任意给值，只不过，给的值不同，预排序出来的数据次序就不同。

我们可以令gap=n，gap=gap/3+1，这样每次使用的gap都在变化，而且能确保最后一次的gap一定是1，也就确保了最后一次一定进行的是插入排序。

最终代码如下：
void ShellSort(int* a, int n)
{
	//gap > 1  预排序
	//gap = 1  直接插入排序
	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 (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序的时间复杂度：

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

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

3.选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序过程如下图所示：

上图中是把待选数据遍历一遍，每次选出最小的数据放在前面，其实我们可以对其优化一下：把待选数据遍历一遍，每次同时选出最大和最小的数据，把最小的数据放在前面，最大的数据放在后面。

代码如下：
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	int mini = begin;
	int maxi = end;
	while (begin<end)
	{
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
问题来了，上述代码对吗？

运行一下就会发现：

诶？不对啊，那到底哪里出错了呢？

下面我们举个极端的例子：

经过遍历以后发现，最大数的下标maxi和begin重合了，那我们交换时就出现问题了，最小数0确实放在了前面，但是最大数的位置也变了，下面再想把最大数放在后面，此时的下标就不能再用了，所以我们在交换a[begin]和a[mini]的值后，要将最大数的下标更改:
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		//如果发生重叠，就更改下标
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}