数组插入排序

插入排序是一个相对复杂一点的排序算法,但是效率要比我们以前接触过的排序算法快一些,他的思想是将数组分为两组数据(第一次分的时候就是数组第一个元素为一组,后面的所有元素为一组),然后从后面一组数据中抽取第一个元素与前面一组数据依次做对比,按需求将大的或者小的值插入到前面的一组数据中,最终后面一组数据全部插入完毕后,前面一组数据就是有序状态了。

如果这样说比较枯燥,我们可以做一个小案例。有下面这样一组数据。

10 2 7 6 1 4 3

我们先将其分两组,一组是

10          2 7 6 1 4 3

然后抽取出 2 这个数据,记录到临时变量中,此时 2 这个数据的位置就空下来了,让临时数据与前面的数据依次对比(目前只有一个数据,如果超过1个数据就要依次对比)比 2 大的就向后移动一个位置,如果比 2 小,那么 2 就插入到移动后空闲出来的位置。上面这个分组经过第一次插入排序后,结果是这样的。

2 10       7 6 1 4 3

继续上面的操作

2 7 10      6 1 4 3

2 6 7 10      1 4 3

1 2 6 7 10      4 3

1 2 4 6 7 10     3

1 2 3 4 6 7 10

这种排序的图形表示法如下(摘自 传智播客 教师课件,图片下载下来放大看):

2015-06-07_232108

【代码实现】

void insert_sort(int* arr, int len)
{
	// 用来记录空位的下标
	int tmp = 0;
	// 用来记录抽取出去的值
	int value = 0;
	for (int i = 1; i < len; i++)
	{
		// 让 tmp 记录当前 i 的下标
		tmp = i;
		// 把下标为 i 位置的值存放到 value 中,此时下标为 i 的位置已经是空位
		value = arr[i];
		// 让 j 从 i - 1 的位置到 >=0 的位置递减遍历
		// 并且 arr[j] 的值要大于 value 的值才进入循环
		for (int j = i - 1; j >= 0 && arr[j] > value; j--)
		{
			// 如果以上条件符合,将当前下标为 j 的值移动到空位上
			arr[tmp] = arr[j];
			// 这样 j 的位置就空下来了,让 tmp 重新记录空位的位置
			tmp = j;
		}
		// 最后将最初记录 i 的值存放到多次移动的空位上
		arr[tmp] = value;
	}
}

 

评论