经典算法（三）----插入排序----图解法让你快速入门

引言

     只要设计到数据，就会涉及到数据的排序问题，比如给你随机给你五个整数  3，1，5，2，4 。让你从小到大进行排序，那我们该怎样才是实现对这些整数的排序呢 ？

    答案是多种多样的，比如用插入排序、选择排序、堆排序、归并排序、快速排序等等，这些排序方法都可以实现对整数排序，而这篇文章要讲的就是插入排序

本文将从以下几个问题对插入排序进行分析和讲解：

1. 什么是插入排序？
2. 插入排序的大概过程是什么？
3. 怎样用代码实现插入排序？
4. 插入排序的代码详解。

什么是插入排序？

下面看百度百科对插入排序的定义：

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动   。

简单来说：就是在想有序的数组中插入一个值，并且插入之后的数组仍然是有效的，进行一次次的插入，知道最后排好序。

下面看一个动图：
 

 

插入排序的大概过程是什么？

下面拿一个例子说明选择排序的大概过程。

插入排序的基本思想就是：往有序的序列中一次次插入值，直到排序完成

下面来说用插入排序对3，1，5，2，4进行排序（从小到大排序）

1. 首先选定第一个数3为有序序列，拿着第二个数1往前面那个有序序列中插入值，插入的方法是用要插入的1依次和有序序列的值比较（从有序序列的后面依次往前比较），知道发现一个数比这个要插入的1小或者要插入的数走到了有序序列的头部为止。
2. 经比较发现发现1<3，那就把有序序列的3后移一个位置（注意不是1和3这俩数）。这时候走到了头，那就把数字1放到头部。这时候数组元素为1，3，5，2，4
3. 继续拿着5去有序序列中比较，发现5>3,那就不用继续比较了，因为3前面的数肯定比3小。                                         这时候数组元素为1，3，5，2，4
4. 继续拿着2去和有序序列比较，首先发现2<5，那就把5后移一个位置（注意是后移）。再用2和3比较，发现2<3，那就把3后移一个位置，继续用2和1比较，发现1<2。那就找到了放2的位置，把2在1后面就可以了。                                只是后数组元素为1，2，3，5，4
5. 按照上面的方法，用4去一一比较即可，最后得到的结果就是1，2，3，4，5

总结：假设有n个数需要排序，我们可以默认第一数是有序的，那就只需n-1轮就可以排序完成。每轮就是拿着元素去有序序列从后往前比较，这可以写一个while循环实现，循环结束的条件就是比较到头了或者找了比这个数要小的数，

扩展：这个扩展对后面理解希尔排序特别有用， 如果暂时不理解这个扩展的也没事。

1. 就上我们上面第3步结束后，数组元素为1，3，5，2，4，前三个元素为有序序列，后两个还未比较，这时候我们需要拿着2去比较，等比较结束，发现3和5都后移了一个位置，所以一共后移了两个位置。
2. 再看我们上面的的第4步结束后，数组 元素为1，2，3，5，4。这时候还剩一个元素4没有排序，排序后，发现5后移了一个位置，所以一共后移了一次。
3. 一个是后移了两次，一个是后移了一次，那么时间复杂度肯定是不同的，后移一次的肯定更省时一些，而且后移的次数时候数组元素的 “ 相对有序 ” 有关。
4. 相对有序的意思就是相对来说小元素在前面，大元素在后面，只要有这个意识就可以了，其他的就不再多赘述了。至于怎样利用这个相对有序来减少排序的时间，就是后面希尔排序的事情了。

 怎样用代码实现插入排序？

通过上面对3，1，5，2，4的排序过程讲解，我们需要明确已知的三个条件

1. 我们要排序的数组有哪些数？数组长度为多少？
2. 我们要进行几轮插入操作？
3. 每轮插入，哪些元素需要后移？

搞清楚了上面三个条件，我们下面我们动图数据排序的实现代码：

#include<iostream>
using namespace std;
//插入排序函数    稳定 
void InsertionSort(int arr[],int len)
{
	int temp;
	for(int i=1;i<len;i++)
	{
		int index=i-1;//前i-1个数已经排序好了
		int current=arr[i];
		while(index>=0&&arr[index]>current)
		{
			arr[index+1]=arr[index]; 
			index--; 
		}
		arr[index+1]=current;
	}
}
//输出数组的值
void printf(int arr[],int len)
{
	for(int i=0;i<len;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}
int main()
{
	//要排序的数组 
	int arr[]={3, 44,38, 5,47,15,36,26,27,2 ,46,4 ,19,50,48};
	int len=15;//要排序的数组长度 
	
	//排序 
	InsertionSort(arr,len);
	
	//输出 
	printf(arr,len);
	return 0;
}

运行结果： 

插入排序的代码详解

 

1. 上面代码写了两个函数，一个是printf函数，这个是输出排序后的数组。
2. 另一个函数就InsertionSort函数，在这个函数里面有一个二重循环，外层循环的的次数就是要查找的次数，内层循环的次数的就是要比较的次数，刚好对应上面说的（这里数组下标是从0开始的）。如果对上面代码有疑问，自己可以按照前面的过程，模拟一边对3，1，4，5，2的排序过程，就知道代码是怎样执行的了 。

本文参考以及引用：

百度百科

图片动画