八大排序算法之直接插入排序算法

引言

插入排序简单的来说就是把一个数插入到一个有序的数列当中，从而使得新的数列仍然有序。再具体点讲，如果有一个数组，数组中有n个元素，如果用两个数组进行实现，其中一个是要排序的乱的数组，一个是空的数组，那么首先把第一个元素插入到空数组中，再取第二个元素插入，那么这个时候就需要判断是否比原先插入的元素大还是小，如果大则直接插入到原先元素后面，如果小则插入到原先元素的前面，然后取第三个元素，对原先插入的前两个元素进行比较后再插入到合适的位置，依此循环类推；如果用一个数组进行实现，那么可以把这个数组看成两个部分，一个是有序的部分，一个是无序的部分，然后只需要依次取无序的部分插入到有序的部分即可，其实思路和两个数组实现一样，两个数组实现比较好理解，然后首先可以把这个有n个元素的数组的第一个元素看成一个有序的部分，后面的n-1个数看成无序部分，接着取无序部分的第一个数，也就是整个数组的第二个数对前面有序部分的数进行依次比较，然后插入到相应的位置，依次类推，直到无序部分全部取完就结束了。

具体思路

首先考虑第一种方法，用两个数组进行实现，这样可能会好理解一点。
首先定义两个数组分别为a[8]，b[8]。a数组中的8个数为9，4，2，11，5，6，30，22；b数组假设是个空的数组（实际默认值为全0）。那么现在a数组就是一个无序的数组，b数组就是一个有序的数组（空数组），现在要做的就是把a数组中的数从0号位开始依次有序的放入到b数组。

i=0 a[0]=9 插入到b数组 b数组：9 (因为b数组是空的所以直接插入）

i=1 a[1]=4 插入到b数组 b数组：4，9（这里把4插入到b数组的时候需要遍历之前的元素判断插入的位置，以下步骤一样）

i=2 a[2]=2 插入到b数组 b数组：2，4，9

i=3 a[3]=11 插入到b数组 b数组：2，4，9，11

i=4 a[4]=5 插入到b数组 b数组：2，4，5，9，11

i=5 a[5]=6 插入到b数组 b数组：2，4，5，6，9，11

i=6 a[6]=30插入到b数组 b数组：2，4，5，6，9，11，30

i=7 a[7]=22插入到b数组 b数组：2，4，5，6，9，11，22，30

执行完毕

以上执行步骤中把a数组中的数插入到b数组中是关键，假设数组中的第k位置插入一个值只需要把k及k以后的部分往后移一位就可以了，然后在k位置插入a数组中的数，如果b数组用链表实现，那么插入就比较方便了。

再来考虑第二种思路，用一个数组进行实现
首先定义一个数组a[8]，a数组中的8个数为9，4，2，11，5，6，30，22。思路还是和上面的一样，把这个a数组看着两个部分，一个部分是有序的，另外一个部分是无序的，这里把a数组的第一个数看成是有序的部分，后面的n-1个数看成无序的部分，接下来就是要把第二个数开始的无序部分的数依次插入到前面的有序部分，从而使得整个数组有序。

i=0 a[0]=9 a数组：（有序部分）9；（无序部分）4，2，11，5，6，30，22

i=1 a[1]=4 a数组：（有序部分）4，9；（无序部分）2，11，5，6，30，22（把i=1位置的4插入到有序部分）

i=2 a[2]=2 a数组：（有序部分）2，4，9；（无序部分）11，5，6，30，22（把i=2位置的2插入到有序部分）

i=3 a[3]=11 a数组：（有序部分）2，4，9，11；（无序部分）5，6，30，22

i=4 a[4]=5 a数组：（有序部分）2，4，5，9，11；（无序部分）6，30，22

i=5 a[5]=6 a数组：（有序部分）2，4，5，6，9，11；（无序部分）30，22

i=6 a[6]=30 a数组：（有序部分）2，4，5，6，9，11，30；（无序部分）22

i=7 a[7]=22 a数组：（有序部分）2，4，5，6，9，11，22，30；（无序部分）

执行完毕

以上步骤思路也是和前面差不多，主要是一个数组实现把无序部分的数插入到有序部分是个难点，假设现在是第k个位置上的数（无序部分）插入到前面的有序部分，那么0到k-1的部分现在都是有序的，首先可以把a[k]存到一个临时变量中，然后从a数组的第k-1位开始遍历(从有序部分后面往前遍历)，如果第k-1位的数要大于a[k]，那么就把第k-1位的数往后移一位，原来的第k位的数现在是第k-1位的数覆盖了，并把第k-1位的index保存下来，继续往前判断，直到第x位如果小于a[k]了，那么就把a[k]插入到刚刚保存的index那个位置（也就是第x+1位），依次类推，后面的无序部分依次重复上面的操作即可。

那么这个插入排序的算法的时间复杂度是多少呢？最好的情况这个数组本来就是个有序的数组，那么只要遍历一遍即可，无序做向前插入操作，那么时间复杂度应该是O(n)，最差的情况这个数组是无序的，并且每个数都要向前插入，每次插入一个数都要往前遍历一次，那么时间复杂度则是O(n^2)。

代码实现

#include<iostream>
using namespace std;
const int N=8;
int insertSort(int *a,int n)
{
	int temp,k;
	for(int i=1;i<n;i++)
	{
		temp=a[i];//把无序部分中要插入到前面有序部分的数a[i]保存下 
		k=i;//并且把无序部分那个数的index保存下来 
		for(int j=i-1;j>=0;j--)//遍历有序部分，从后往前遍历，这样能减小复杂度 
		{
			if(temp<a[j])//判断无序部分数是否比前面一位（有序部分最后一个数）要小 
			{
				a[j+1]=a[j];//把有序部分那个数往后移一位（腾出空间留给a[i]一个位置） 
				k=j;//记录a[i]要插入的位置，并不断更新这个位置 
			}
			else
			{
				break;//如果a[i]要大于前面那个数了则停止遍历退出循环 
			}
		}
		a[k]=temp;//把a[i]的值插入到k这个位置 
	}
}
int main() 
{
	int a[N]={9,4,2,11,5,6,30,22};
	insertSort(a,N);
	for(int i=0;i<N;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

以上代码是用一个数组进行实现的情况，两个数组实现类似，只是便于理解，说了两个数组的实现的情况。