排序算法之插入排序（C语言）

一、原理讲解

插入排序算法核心思想：将无序数组中的元素，根据其值的大小，插入有序子数组中。类似于我们打扑克牌的时候，一边摸牌，一遍摆牌。遇到小的直接插到牌首，遇到大的直接插入牌尾，遇到中间的则在中间空出一个位置，将其插入。

假定有一个无序数组 arr[10] = {10, 1, 0, 44, 5, 6, 77, 8, 10, 99};

第一步，直接将无序数组的第一个元素划分到有序子数组当中去，将原来的数组构造成有序子数组和无序子数组两个部分。

第二步，将无序子数组的第一个元素缓存下来，存到temp变量里面，并且使用temp和有序子数组最后一个元素（arr[0]）比较，若temp > arr[0]，则直接将temp存到arr[1]当中，若temp < arr[0] 则将arr[0]这个元素后移，存到arr[1]的位置，并且将temp存到arr[0]之中。因为arr[0]前面已经没有数据了。

第三步，有序子数组已有两个数据，无序子数组只剩8个数组，该轮比较我们将arr[2]存到temp当中，使用temp与arr[1]比较，此时我们发现，temp为0， arr[1] 为10，temp  < arr[1]，所以我们需要将arr[1]元素后移，保存到arr[2]的位置上，接着用temp和arr[0]比较，temp < arr[0]，因此我们继续将arr[0]后移且存到arr[1]的位置上，最后将temp存到arr[0]的位置上。

按照这个步骤我们对剩下的数据依次进行比较，并且无需子数组中的数据插入到有序子数组中相应的位置上，直至无序子数组元素为空位置，最终得到结果为：

二、具体代码

/*
函数名：int InsertSort(int data[], int n);
函数功能：使用插入排序的方法，将数组按从小到大排序
函数参数：
         data[]：数组首地址
         n：参与排序的数据个数
函数返回值：
           函数成功排序数组返回0，失败返回-1
*/

int InsertSort(int data[], int n)
{
	if (NULL == data)
	{
		printf("\n data is null \n");
		return -1;
	}
	
	int i = 0;
	int j = 0;
	int temp = 0;

	for (i = 1; i < n; i++)
	{
		if (data[i] < data[i - 1])        //程序优化，若无序子数组第一个元素大于有序子数组            
		{                                 //最后一个元素，直接插入，不进行下面的操作
			temp = data[i];           
			j = i - 1;
			
			while (j >= 0 && temp < data[j])
			{
				data[j + 1] = data[j];
				j--;
			}
			data[j + 1] = temp;      //因为数据比较之后会进行j--
		}
	}
	
	return 0;
}

仓促成文，不当之处，尚祈方家和读者批评指正。联系邮箱1772348223@qq.com