前言

?个人主页：@小沈熬夜秃头中୧⍤⃝❅
?小编介绍：欢迎来到我的乱七八糟小星球?
?专栏：算法
?本章内容：排序算法-插入排序之直接插入排序和希尔排序
送给各位?：落日弥漫的橘天边透亮的星 愿你永远向上.
记得 评论? +点赞? +收藏? +关注?哦~

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

?一、常见的排序算法：

?二、直接插入排序排序：

?2.1 基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想

?2.2 代码：

#include<stdio.h>
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("
");
}
void InsertSort(int* a,int n)
{
//[0, end]有序end+1位置的值插入[0, end]...让[0, end+1]有序
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end+1] = tmp;
	}
}
void TestInsertSoret()
{
	int a[] = { 3,5,2,7,1,4,9,8,0,6 };
	int sz = sizeof(a) / sizeof(a[0]);
	InsertSort(a, sz);
	PrintArray(a, sz);
}
int main()
{
	TestInsertSoret();
	return 0;
}

?2.3 时间复杂度：O(N^2)

逆序的情况下最坏(每个数字都需要移动)等差数列：1+2+3+… …+(n-1)
顺序有序的情况下最好：O(N)

?2.4 流程图详解：

?三、希尔排序(缩小增量排序)：

?3.1 基本思想：

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

?3.2 希尔排序思想图：

?3.3 希尔排序画图详解：

?3.4 代码：

#include<stdio.h>
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("
");
}
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		//gap = gap / 3 + 1;这种也可以保证最后一次gap=1进行直接插入排序
		
		//把间隔为gap的多组数据同时排

		//gap > 1时都是预排序接近有序
		//gap == 1时就是直接插入排序有序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
void TestInsertSoret()
{
	int a[] = { 3,5,2,7,1,4,9,8,0,6 };
	int sz = sizeof(a) / sizeof(a[0]);
	ShellSort(a, sz);
	PrintArray(a, sz);
}
int main()
{
	TestInsertSoret();
	return 0;
}

?3.5 希尔排序画图详解：

?3.6 希尔排序总结：

• 希尔排序是对直接插入排序的优化。
• 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
• 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度:O(N^1.3—N42)
• 稳定性:不稳定
• 多且间隔为gap的预排序，gap由大变小
• gap越大，大的数可以越快的到后面，小的数可以越快的到前面
• gap越大，预排完越不接近有序，: gap越小，越接近有序
• gap ==1时就是直接插入排序

?3.7 希尔排序时间复杂度:O(logN*N)

while(gap>1){gap /= 2… …}外边这个循环跑logN
里面的for循环：

• gap很大时，下面预排序时间复杂度O(N)
• gap很小时.数组已经很接近有序了…这时差不多也是O(N)

?四、希尔排序和直接插入排序性能的比较：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1,N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2,N);
	int end2 = clock();

	printf("InsertSort:%d
", end1 - begin1);
	printf("ShellSort:%d
", end2 - begin2);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}
int main()
{
	TestOP();
	return 0;
}

?总结：

本章内容是对排序算法中的部分排序做了一个解析总结。