排序1-插入排序与希尔排序

前言

一、插入排序

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

简单的来说：上图

当然，图上的方法难免有一些特例

上图：当进行到第四趟插入排序的时候
当然，开始写代码的时候，我们可以先写单趟，假设前n-1已经有序了，我们在来插入最后一个数，

然后再来写多趟，这样就可以简单写出插入排序了。当然，我这样写，是为了写下面介绍的希尔排序。

void InsertSort(int *arr, int n)//这里的n是·数组中元素的个数
{
	for (int i = 0; i<n-1; i++)//上图可知道，我们控制外层循环的时候，只要控制小于n-1
	{
		int end=i;
		int tmp=arr[end+1];
		while (end >= 0)
		{
			if (arr[end] > tmp)//比较大小
			{	
				arr[end + 1] = arr[end];//后移
				end--;//end--,前移
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;//防止上面说的情况，在循环外插入
	}
}

总结：

1. 元素越接近有序，插入排序的时间效率就越高
2. 时间复杂度为O(N)
3. 空间复杂度为O(1)
4. 稳定性：稳定

上面插入排序的代码特点是，前后指针相关联的，且从左到右

二、希尔排序

希尔排序：希尔排序又称缩小增量法，先选定一个整数，把待排序文件中所有记录分成个
组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

简单点说：

1. 先预排序—>接近有序
2. 直接插入排序

如图：

当数据较大时，我们应该如何控制gap呢？

1. 我们可以用数据来控制，先gap=n
2. 如何在循环中gap=(gap/3+1),我们以gap/3来慢慢缩小gap的值
3. 当gap越小的时候，就越接近有序

为什么是gap=（gap/3+1）而不是gap=（gap/3）呢？

1. 举个例子，当gap=6时，如果是gap=（gap/3），那么第一次循环，gap=2，当进行第二次循环的时候，gap=0了，那么进行下面的循环的时候就没法玩了。
2. 但是当gap=（gap/3）+1的时候，第一次循环，gap=3，第二次循环，gap=2，第三次循环gap=1，然后再结束，这时候，就进行了预排序后面要进行的插入排序了，排序完成。
3. gap=1的时候就相当于插入排序，所以控制gap的大小来控制整个程序是否结束，当然这时候进行插入排序的时候，数组已经接近有序了，所以这时候插入效率很高。

细心的朋友应该发现了，下面代码中的当gap=1时就是插入排序

//希尔排序

void ShellSort(int *arr,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 = arr[end + gap];
			while (end >= 0)
			{
    
				if (arr[end] > tmp)
				{
    
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}	
}

这个代码最外围的for循环，要好好看一下，
如图：这是gap=3的时候
总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3~N²）
4. 稳定性：不稳定

总结

通过上面的学习，我们知道希尔排序的关键并不是随机分组后的各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高。