【数据结构篇】~排序（1）之插入排序

前言

四大排序，今天解决插入排序

堆排序和冒泡排序已经写过了，可以看之前的博客！

插入排序

1.直接插入排序（时间复杂度：O(N^2)）

1.思想

插入排序​
基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。​
直接插入排序​
当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时
用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置
即将 array[i] 插入，原来位置上的元素顺序后移

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)

2.代码

每次插入前，都插入的是排好序的子数组的下一个元素，那么定义一个end用来记录最后一个有序元素的位置，那end+1就是插入的元素的下标。
先写内层循环，先假设end==0，那要插入的就是arr[1]（tmp）,进行比较，如果arr[end]>arr[end+1],然后把arr[end]往后挪，再end–，继续往前找，直到找到比tmp小的，然后break，把tmp赋给arr[end+1]（因为end下标的元素就是那个比tmp小的数，而原来的end+1位置的数因为往后挪了所以现在end+1下标位置是空的），或者直到找不到，break，把tmp赋给arr[end+1]

void insertsort(int*arr,int n)
{
	for (int i = 0; i < n-1 ; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

2.希尔排序(时间复杂度：O(N¹∙³))

1.思路

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是gap = n/3+1），把
待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。
希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。
2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序
的了，这样就会很快。这样整体而言，可以达到优化的效果。

简易证明希尔排序的复杂度

这里先假设，gap每次除3共有n个数，gap=n/3那么每组就有3个数，那就共有gap组数据
共3/n组
第一趟预排序（最坏的情况下这3个数都要交换一遍那么消耗就是）：（1+2）*3/n=n
共9/n组，每组9个数据
第二趟预排序（最坏的情况下这9个数都要交换一遍那么消耗就是）：
（1+2+…+8）*9/n=4n，
…
直到gap=1，进行最后一次直接插入排序，但是在第二次预排序时，数组已经不可能是最坏的情况了，因为已经经过第一次预排序了，所以第二次的消耗肯定是小于4n的，往后的每次消耗肯定是比算出来的消耗要小的，最后经过大量实验才得出时间复杂度是：O(N¹∙³)

2.代码

void shellsort(int* arr, int n)
{
	int gap = n;
	while(gap>1)
	{
	//这里进行预排序，直到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;
		}
	}
}