插入排序--直接插入排序（不要再寻找，看这篇就够了）

插入排序--直接插入排序（不要再寻找，看这篇就够了）

  成长是一笔交易，我们都是用朴素的童真与未经人事的洁白交换长大的勇气。

---

文章目录

• 一.前言
• 二.思想及 *** 作分析
• 三.代码设计
• 四.代码实现
• 四.总结

---

一.前言

  插入排序根据查找位置的方式不同，可以分为：顺序法查找插入位置的——直接插入排序；二分法也叫折半法查找插入位置的——折半插入排序；缩小增量多遍插入排序的——希尔排序。本文探讨有关直接插入排序的知识。

---

二.思想及 *** 作分析

思想：
  通过顺序法查找插入位置，即边比较边移动找出插入位置，并插入到正确的位置。
  我们都知道要在数组某一个位置插入一个数据，如果这个位置没有被占，那么直接插入到该位置。如果该位置被占，那么需要将该位置及其后面的元素均往后移动一个位置空出当前位置，才能进行插入。
  借助这个思想我们将数组元素分为两组，已经有序的一组和无序的一组。从无序的一组依次拿出数据插入到有序的一组并保持有序的一组依旧有序。来看一下这种思想的 *** 作分析。

*** 作分析：

  有如上的一个数组，现在我们需要将该数组中的元素从小到大进行排序。
  首先将数组分为两组，有序组（有颜色标记的），无序组（无颜色标记的），如下：

  对于第一个元素默认都是有序的（千万不要迷惑啊，只有一个元素当然是有序的）。现在我们要从无序组中选择第一个元素，即数组下标为1号位置的元素。对该位置的元素进行拷贝，也可以理解为拷贝后该位置没有数据（这里只是为了方便分析），将该位置编为有序组，如下：

  接着拿拷贝出来的元素和有序组中的元素依次比较。和0号位置比较有没有小于0号位置的元素，没有则放到0号位置的后面即1号位置，如下：

  再从无序组中拿出一个元素（这次是2号位置），拷贝数据，将该位置编为有序组中，如下：

  将拷贝出来的数据11和1号位置的元素进行比较，发现比1号位置的数据小，说明插入位置在1号位置数据的前面，那么将1号位置的元素往后面移动一个位置，即移动到2号位置，如下：

  再和0号位置进行比较，还是比它小，则将0号位置的元素往后移动，即移动到1号位置，如下：

  下一个位置是 -1 号位置,当然不能越界，则0号位置就是要插入的位置，将数据插入到0号位置，如下：

  如果我们发现插入元素比比较元素大则插入到比较元素的后面。重复上面的 *** 作直到整个数据有序，给出排好序的结果，如下：

  整个数据就由无序慢慢变为有序。

*** 作步骤：
 1.将数据分为有序和无序两组；
 2.从无序组中拿出数据并进行拷贝；
 3.到有序组中寻找插入的位置；
 4.将数据插入到有序组中正确的位置；
 5.重复2、3、4步骤直到整个数据变为有序。

---

三.代码设计

  需要一个指示无序组元素下标的变量 “i”，需要一个指示有序组元素下标的变量 “j”，还需要一个临时变量 “temp” 用于拷贝数据。依次从无序组中取出数据插入到有序组中，直到整个数据有序。

---

四.代码实现

typedef int ElementType;
void InsertSort(ElementType A[], int size)
{
	int i;//记录无序组中元素的数组下标
	int j;//记录有序组中元素的数组下标
	ElementType temp;//临时变量，用于拷贝数据
	for (i = 1; i < size; i++)//依次从无序组中取元素。第一个元素默认有序所以i=1。
	{
		temp = A[i];//拷贝待插入元素
		for (j = i - 1; j >= 0 && A[j] > temp; j--)//到有序组中寻找插入位置
		{
			A[j + 1] = A[j];//将数据往后移动一个位置
		}
		A[j + 1] = temp;//插入到当前位置的下一个位置
	}
}

  对于直接插入排序的代码还有改进的空间，比如加哨兵，即0号位置我们不存储数据，用来当哨兵位置，还有在拷贝数据之前我们就可以提前作一次判断，给出代码如下：

void InsertSort(ElementType A[], int size)
{
	int i;
	int j;
	for (i = 2; i < size; i++)//第一个位置本身有序，所以i=2，0号位置我们当作哨兵位；
	{
		if (A[i] > A[i - 1])continue;//判断当前位置有没有大于其前面一个位置，若大于不需要进行移动，直接结束本次循环的迭代
		A[0] = A[i];//把数组下标为O的位置当作哨兵位置
		for (j = i - 1;  A[j] > A[0]; j--)
		{
			A[j + 1] = A[j];
		}
		A[j + 1] = A[0];
	}
}

---

四.总结

   对于直接插入排序原始数据越接近有序，直接插入排序效率较高（即逆序个数越少越快）。时间复杂度为O(n^2)，空间复杂度O（1）。
如何提高插入排序的效率：
 减少元素的比较次数
 减少元素的移动次数

  下期我们讲解通过减少元素的比较次数来提高插入排序效率的——折半插入排序。

---

  我是老胡，感谢阅读！！❤️ ❤️