[数据结构与算法]插入排序 ( 直接插入排序 && 希尔排序 )

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)，它是一种稳定的排序算法

??4?? 稳定性：稳定

? 动图演示：?

🧿 实现代码 ：

void InserSort(int* a, int n)
{
	//多趟控制
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		//单趟控制
		int end = i ;
		int temp = a[end + 1];
		while (end >= 0)
		{
			//目标数小于其它数时，其它数就往后挪；大于则插入
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	}
}

? 插入排序的时间复杂度 ?

??最坏的情况 - 逆序：O(N²)

??最好的情况 - 接近有序 ：O(N)

2、希尔排序

希尔排序 (缩小增量排序)

🔑 核心思想 🔑

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

??人话就是：

????1?? 预排序 (接近升序) - gap > 1

????2?? 直接插入排序 - gap == 1

? 希尔排序特性总结 ?

??1?? 希尔排序是对直接插入排序的优化

??2?? 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，其实就是直接插入排序，且数组已经接近有序的了。整体而言，可以达到优化的效果，我们实现后可以进行性能测试的对比

??3?? 希尔排序的时间复杂度并不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些数中给出的希尔排序的时间复杂度都不固定，官方给出的时间复杂度是 O(N^1.3)

??4?? 稳定性：不稳定

👁?🗨 知识扩展

🧿 实现代码 ：

代码的核心并不是一组一组的排，而是多组并排

以下只是预排序代码，还需要再调用 InsertSort 进行直接插入排序

void ShellSort(int* a, int n)
{
	int i = 0;
	int gap = 3;
	//多组并排
	for (i = 0; i < n - gap; i++)
	{
		int end = i;
		int temp = a[end + gap];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = temp;
	}
}

? 对于 gap 的值写成固定的并不好 ?

??这里只是建议

void ShellSortPro(int* a, int n)
{
	//gap > 1 预排序
	//gap == 1 直接插入排序
	int i = 0;
	//gap的初始值为n
	int gap = n;
	while (gap > 1)
	{
		//每次循环gap都在减少，直到gap变成1
		gap = gap / 3 + 1;
		//gap /= 2;
		
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (temp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}