直接插入排序&希尔排序纯C实现

直接插入排序

希尔排序

性能测试

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

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] < tmp
			{
				a[end + 1] = a[end]; //a[end]小于tmp把a[end]挪到后面的位置；
				--end;//在跟下个数比较
			}
			else//走到这里说明前面的数小于tmp
			{	//这个循环有两种结束条件
				//找到比tmp小的就停下，还有一种就是tmp最小，循环结束
				break;//所以这里的用break，更方便
			}
			a[end + 1] = tmp;//把tmp放到end+1的位置上
		}//直接插入排序比较简单，容易理解 时间复杂度O(n^2) 
	}
}

希尔排序在直接插入排序的思想上来进行操作
希尔是预排序，通过区间来进行，可以让大的数更快到后面，小的数更快到前面，gap>1都是预排序gap==1的时候就是直接插入排序，区间为几，就有几组区间

void ShellSort(int* a, int n)//通过代码可以看出来跟直接插入排序很相似
{
	int gap = n;//区间的大小跟数据个数有关系
	while (gap > 1)//gap为一就排完序了
	{
		gap /= 2;//gap每次除二，后面gap会==1，
		//gap=(gap/3) + 1；//这种也可以，加一为了防止gap==0
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];//以区间进行比较

			while (end >= 0)
			{
				if (a[end] > tmp)//大于tmp进行调整
				{
					a[end + gap] = a[end];//跟直接插入一样，只是这里是区间
					end -= gap;//找前面的数进行比较
				}
				else
				{    //这个循环有两种结束条件
				     //找到比tmp小的就停下，还有一种就是tmp最小，循环结束
					break;
				}
			}
			a[end + gap] = tmp;//放入数据
		}//希尔比较难理解，可以通过调试来理解，画图，希尔排序很快，一些书籍上给的时间复杂度：O(n^1.3);
	}
}

我这里的编译器是vs2022,Release测试模式，排序十万个随机数，时间是毫秒，通过这个可以看出来希尔排序的预排序有很大的用处