数据结构之八大排序项目-----直接插入排序和希尔排序（从小到大）_希尔排序与直接插入排序哪个时间长

一、直接插入排序

思想

例如： 6 4 5 2 6 7
从第二个数据开始依次往后遍历。每遍历一个数据 i 下标对应的值tmp，就从后往前找 i 下标前面第一个大于 tmp 的数 j下标对应的值 ，依次遍历 i下标 前面的所有数 。找到后将 j 后移。直到tmp 大于 j 下标对应的值时，以及 j 到达边界时将 tmp 插入到空出来的 j+1 的位置上。

例：从4开始查找，从后往前找第一个比4大的6（ j 下标对应的值为6），将6后移。j–到达边界之后，直接将4插入到 j +1 的位置，即0下标的位置。
数据变成：
4 6 5 2 6 7
之后遍历到5，从后往前找第一个比5大的数，第一个6大于5，将6往后移，第二个4小于5，将5插入到4后面的位置。
数据变成：
4 5 6 2 6 7
之后遍历到2，从后往前找第一个比2大的数据，第一个6大于2，将6往后移，第二个5大于2将5往后移，第三个4大于2将4往后移，j到达边界，将2插入到j+1的位置，即0下标。
数据变成：
2 4 5 6 6 7
之后遍历到6，从后往前找第一个比6大的数据，没有比6大的，直接将6插入到j+1的位置即可。
数据变成：
2 4 5 6 6 7
之后遍历到7，从后往前找第一个比7大的数据，没有比7大的，直接将7插入到j+1的位置即可。
数据变成：
2 4 5 6 6 7
遍历完成，数据有序。
插入操作
在遍历过程中，先用一个tmp将数据 i 保存下来，和前面的数据 j 依次比较，未找到小于 i 的数据，j 就进行后移。找到之后停止后移，将 i 插入到j+1的位置上。

代码

void Insert(int* arr,int n)
{
	int j;
	//assert(arr != NULL);
	for (int i = 1;i < n;i++)     //将数据从第二个数据开始遍历
	{
		int tmp = arr[i];          //保存要插入的数据，防止移动时丢失
		for ( j = i - 1;j >= 0;j--)
		{
			if (tmp < arr[j])      //找i前面大于tmp的值，找到了将j对应的值后移,
				                    //直到j到达边界或者i前面没有大于他的值为止
				arr[j + 1] = arr[j];

			else
				break;
		}
		arr[j + 1] = tmp;                //找到后将i对应的值插入到j+1下标处
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度、空间复杂度和稳定性

时间复杂度为O（n^2）,空间复杂度为O（1),稳定。
空间复杂度：程序中没有随着问题规模n变化而变化的额外空间也没用到递归。所以空间复杂度为O（1)
判断稳不稳定只需要判断有没有发生跳跃式的交换数据，很显然数据直接插入排序数据移动的时候，是一个挨着一个移动的，没有跳跃式移动数据，所以稳定

特点

直接插入排序又叫做简单插入排序，有一个显著特点即越有序越快。因为当数据完全有序时，i下标前面将没有大于tmp的值，第二个循环时间复杂度为O（1），总体时间复杂度在完全有序情况下达到O（n）。

二、希尔排序

灵感来源

希尔排序是在直接插入排序基础上设计出来的一种排序方法。因为直接插入排序具有越有序越快的特点，所以希尔排序就让数据越来越有序，最后达到全部有序。

思想

将待排序数据分组，将分组后的数据进行直接插入排序。随着分组的减少到1组，达到将所有数据一起直接插入排序。

将数据先分五组，再分三组，最后分一组。分组时采用间隔式分组，从而使数据更有序。

例如数据开始为 7 6 8 2 7 4 6 3 5 9 4 5 3 7 9
其中红色线连接的三个数据为一组，黑色，绿色，黄色，紫色连接的三个数据为一组,我们需要将这几个组分别插入排序。

一、分五组
1.先将红色部分按插入排序成有序：

2.再将黑色部分按插入排序成有序：

3.将绿色、黄色、紫色同样按插入排序成有序：

二、分三组
将上图分五组得到的新的顺序的数，再分三组（如下）：

我们将上图得到的三组，分别按直接插入排序分别排序（同分五组的每组排序），将得到每组都有序的序列。

排序结束将得到 更趋向于有序的序列。 如下：

三、分一组
最后希尔排序会回归到最初的插入排序（见上直接插入排序）。只需进行插入排序即可。因为此时的数据已经趋向于有序，并且直接插入排序特点为越有序越快，这就是为什么需要不断缩小组数的原因。

在最后分一组的前提下，希尔排序完毕，数据完全有序。

代码

void  Shell(int* arr, int len,int group)//group是指分的组数
{
	int j;
	for (int i = group;i<len;i++)//和直接插入一样找从每组的第二个数据开始，和前面数据比较。i的起始下标为group。
	{
		int tmp = arr[i];          //保存要交换的数据
		for (j = i - group;j >= 0;j-=group)      //依次将需交换的数据和他前面的数据依次比较，如果前面数据大，进行后移。只是移动时，一次移动group（组数）个数据。所以j的值会跳转。
		{
			if (arr[j] > tmp)
				arr[j + group] = arr[j];  //移动数据
			else
				break;

		}
		arr[j + group] = tmp;//找到位置，将需交换的数据插入进去。

	}
}
void myShell(int* brr,int len)
{
	int arr[3] = { 5,3,1 };       //依次分五组，三组，一组进行插入排序。
	for (int i = 0;i < 3;i++)
	{
		Shell(brr, len, arr[i]);   //当分一组时，和直接插入排序完全相同
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

【注意】当数据量很少的情况，或者分组没有平均，程序依然可执行。

时间复杂度、空间复杂度和稳定性

希尔排序因为是逐渐更有序，比直接插入排序的时间复杂度低。希尔排序时间复杂度在O（1.3）~O（1.5）。
空间复杂度：O(1)
因为在交换数据过程中发生了跳跃式交换数据，所以希尔排序不稳定。