插入排序的C语言实现_c语言实现插入排序算法

一.简单插入排序

1.简单插入排序的基本概念

当我们将一个数组进行排序时，我们认为第一个数一个有序序列，然后插入下一个元素，经过对比，使这两个数成为新的有序序列，同理依次插入后续元素。

在我们生活中中也经常用到插入排序，不知道小伙伴们是否注意到当我们打扑克摸牌的时候也是类似插入排序，当我们抓上来第一张牌时，认为它是最小的牌，当我们抓下一张时与上一张比较，比较之后再插入。

2.简单插入排序的图示过程

(1).初始数据

(2).经过对比3<5, 挪动5，并且end指针往前移

(3).end < 0，end+1的位置替换成tmp

(1) (2) (3) 为3插入5有序序列的过程

(4)end和tmp分别指向下一位置

(5）经过对比 1 < 5 , 挪动5，并且end指针往前移

（6）经过对比1<3 ，挪动3，end指针往前移

（7）end<0，end+1的位置替换成tmp

(4)(5)(6)(7)为1插入3，5有序数组的过程,后续过程类似大家自行推到，如有疑惑可以私信up主

3.简单插入排序的代码实现

//简单插入排序
void InsertSort(int* a, int n)
{
	assert(a);        //断言a是否为空
 
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;	//记录最后位置
		int tmp = a[end + 1];	//记录要插入的数据
 
		while (end >= 0)	//依此对比，至到a[0]
		{
			if(tmp < a[end])	//如果要插入的数据比已经有序中的元素小
			{
				a[end + 1] = a[end];	//则移动数据
				--end;					//再比较前一个
			}
			else
			{
				break;					//如果要插入的数据不比有序数据小则不再比较
			}
		}
 
		a[end + 1] = tmp;
	}
}

4.简单插入排序的复杂度

简单插入排序的时间复杂度为O(n*n) 空间复杂度为O(1)

二.希尔排序

1.希尔排序的基本概念

希尔排序的名字由来是发明此算法的人名叫Shell，希尔算法是对简单插入排序的一个优化。简单选择排序当序列基本有序的时候算法的时间开销会很小，而希尔恰恰是利用这一点，在简单选择排序之前对数组进行预处理让数组基本有序。

2.希尔排序的图示过程

(1)首先对元素进行分组，设下标差为3的是一组则图中元素分为红黄蓝三组

（2）然后依次进行简单插入排序,排序完成如下图所示

(3)再缩短间距，每次都使间距 gap = gap /3 +1 进行分组,分成下图两组

(4)再对每组分别进行简单选择排序，排序结果如下图

（5）gap再次发生变化 变为gap = gap /3 +1 等于1，既对整个数组进行简单选择排序，而此时，数组已经基本有序，简单选择排序需要的时间会大大减少

3.希尔排序的代码实现

//希尔排序
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 tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
 
			a[end + gap] = tmp;
		}
	}
}

代码中有一个巧妙的点，就是每次都是++i,即每次都是交替分组排序

4.希尔排序的复杂度

时间复杂度为O(n^1.3)~O(n^n), 空间复杂度为O(1)

三.简单插入排序与希尔排序对比

排序一个10000个随机值数组所需要的时间，直接插入排序为122毫秒，而希尔排序为3毫秒。但是如果本来数组就基本有序时，简单插入排序更优