当前位置：首页 > article >正文

【数据结构】插入排序和希尔排序

article 2024/11/5 12:41:09

插入排序思路

把待排序的记录按其关键码值的⼤⼩逐个插
⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列。

直接插入排序思路

直接插入排序的步骤如下：
从第二个元素开始，将其视为待插入元素。
比较待插入元素与其前面已排序序列中的元素。
如果待插入元素小于比较的元素，则将比较的元素向后移动一位。
重复步骤3，直到找到合适的插入位置。
将待插入元素放入找到的位置。
重复步骤1-5，直到所有元素都被插入到正确的位置。序后移

动图解析

在这里插入图片描述

代码解析实现

代码实现：
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)//时间复杂度【n】
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)//时间复杂度【n】
		{
			if (arr[end] > tmp)
			{

				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
			arr[end+1] = tmp;
		}
	}
}

直接插⼊排序的特性总结
1.元素集合越接近有序，直接插⼊排序算法的时间效率越⾼
2.时间复杂度：O(N^2)
3.空间复杂度：O(1）

希尔排序思路

希尔排序法，又称缩小增量排序法，是直接插入排序算法的改进版。其基本思想是：

步骤：

选定一个整数（通常是 gap = n/3 + 1）。
将待排序记录分成若干组，每组内记录的距离相等。
对每组记录进行插入排序。
缩小增量：gap = gap/3 + 1。
重复步骤 2-4，直到 gap = 1，此时相当于直接插入排序。

这种方法通过分组和逐步缩小增量的方式，提高了排序效率。综合来看，希尔排序的效率明显高于直接插入排序算法。

在这里插入图片描述

代码：


```c
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;
		}

	}

}