【数据结构—数据—插入排序】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

---

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远！

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、插入排序

1.1基本思想：

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

实际中我们玩扑克牌时，就用了插入排序的思想

1.2直接插入排序：

当插入第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. 稳定性：稳定

1.3直接插入排序的代码实现

Sort.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

//打印数组
void PrintArray(int* a, int n);

//插入排序(最坏的情况下：逆序，才是等差数列)
void InsertSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"Stack.h"

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//插入排序
//时间复杂度：O(N^2)
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//[0,end],我们把end+1为下标的元素插入前面的有序的区间，后保持有序
		int end = i;
		int tmp = a[end + 1];
		//一趟插入排序
		while (end >= 0)
		{
			if (tmp > a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"

void TestInsertSort()
{
	int a[] = { 3,2,6,8,4,6,0,9,5,1,7 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestInsertSort();
	return 0;
}

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

2.1算法讲解

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

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

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

4. 稳定性：不稳定

2.2希尔排序的代码实现

Sort.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

//打印数组
void PrintArray(int* a, int n);


//希尔排序
void ShellSort(int* a, int n);

Sort.c

一组一组的预排序

//希尔排序
//步骤：1、预排序(接近有序)；2、直接插入排序
//预排序：分别对每个分组进行插入排序
void ShellSort(int* a, int n)
{
	//把间隔为gap的值看作一组
	int gap = 3;
	//gap组预排序
	for (int j = 0; j < gap; j++)
	{
		//一组预排序
		for (int i = 0; i < n - gap; i += gap)
		{
			//[0,end],我们把end+gap为下标的元素插入前面的有序的区间，后保持有序
			int end = i;
			int tmp = a[end + gap];
			//一趟插入排序
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

	}
}

多组一块预排序

//希尔排序(时间复杂度：平均是O(N^1.3))
//步骤：1、预排序(接近有序)；2、直接插入排序
//预排序：分别对每个分组进行插入排序(gap越大，大的值更快调到后面，小的值更快调到前面，但是越不接近有序)
//(gap越小，跳的越慢，但是越接近有序。如果gap == 1就是直接插入排序)，所以gap不能是固定值。
void ShellSort(int* a, int n)
{
	//把间隔为gap的值看作一组
	int gap = n;
	//gap > 1时是预排序，目的是让他接近有序
	//gap == 1是直接插入排序，目的是让它有序
	while (gap > 1)
	{
		//gap = gap / 2;//上下两个都行
		gap = gap / 3 + 1;//一定要保证gap最后一次是1
		//多组一块预排序
		for (int i = 0; i < n - gap; i++)
		{
			//[0,end],我们把end+gap为下标的元素插入前面的有序的区间，后保持有序
			int end = i;
			int tmp = a[end + gap];
			//一趟插入排序
			while (end >= 0) 
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"


void TestShellSort()
{
	int a[] = { 3,2,6,8,4,6,0,9,5,1,7 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestSelectSort();
	return 0;
}

---

总结

好了，本篇博客到这里就结束了，如果有更好的观点，请及时留言，我会认真观看并学习。
不积硅步，无以至千里；不积小流，无以成江海。