[数据结构]——排序——插入排序

1 .插入排序 1.基本思想：

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

2.直接插入排序：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

1.代码实现

排序过程如下：

1. 从数组的第二个元素开始，依次将其与前面的元素进行比较。
2. 如果当前元素比前面的元素小，则将前面的元素后移一位。
3. 继续比较前面的元素，直到遇到比当前元素小的元素，或者已经比较到数组的第一个元素。
4. 将当前元素插入到空出来的位置上。
5. 重复以上步骤，直到所有元素都被插入到合适的位置上。

实际上，这个排序算法的思想就是将数组分为已排序部分和未排序部分，每次从未排序部分选择一个元素并插入到已排序部分的合适位置上。

void InsertSort(int* a, int n)//直接插入排序
{
	for (int 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;
	}
}

2.直接插入排序的特性总结：

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

在实际应用中，如果待排序的数组已经基本有序，那么插入排序的效率会比较高。但是对于逆序数组或者随机排序的数组，插入排序的效率会比较低。因此，插入排序通常用于对小规模数据或者部分有序数据的排序。

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

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

1.预排序

预排序是指在希尔排序之前，先将序列进行一次插入排序，将相隔一个增量的元素进行排序。这样可以将序列的一些小的逆序对提前消除，使得希尔排序的效率更高。

具体的希尔排序预排序的过程如下：

1. 选择一个增量gap序列，通常取序列长度的一半作为初始增量。
2. 根据增量gap将序列分成若干个分组，每个分组包含相邻的元素。
3. 对每个分组进行插入排序，即将每个元素与其前面的元素进行比较并交换位置，直到该元素在该分组中的位置正确为止。
4. 缩小增量，重复步骤2和步骤3，直至增量为1，即对整个序列进行一次插入排序。

预排序是指在排序过程中，每次对分组进行插入排序之前，先对整个序列进行一次插入排序。这样做的目的是减少插入排序的比较和交换次数，从而提高排序效率。预排序的实现方法是在每次缩小增量时，将待排序序列进行一次插入排序。

2.预排序代码

for(int j=0; j<gap ;j++)
{
for (int i = j; 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;
	}
}

3.希尔排序代码

希尔排序的基本思想是将待排序序列分成若干个子序列，对每个子序列进行排序，然后逐步减小增量，最终整个序列就变成了有序序列。 具体的希尔排序过程如下：

1. 初始化增量 gap = n / 3 + 1。
2. 使用 gap 对序列进行分组，分为 gap 个子序列。
3. 对每个子序列进行插入排序，即将每个元素与其前面的元素进行比较并交换位置，直到该元素在该子序列中的位置正确为止。
4. 减小增量 gap，重复步骤2和步骤3，直至增量为1，即对整个序列进行一次插入排序。

希尔排序的特点是可以提前将较小的元素向前移动，从而减少后续插入排序的比较次数和交换次数，从而提高排序效率。

void ShellSort(int* a, int n)//希尔排序
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int 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;
		}
	}
}

4.希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。 2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定；