【十大排序算法】----C语言版插入排序（详细图解）

一：插入排序——原理

二：插入排序——分析

三：插入排序——实现

四：插入排序——效率

一：插入排序——原理

插入排序的原理和基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

动图如下：

二：插入排序——分析

选择排序的核心就是：多趟选择插入

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

通俗来讲就是：以升序（从小到大）下列动图排序为例，假若有N个数。

第一次插入：因为第0个位置可以看作已经排好序了，将array[1]（i ==1）看作是被插入的数据，即让被插入的数据与 [ 0 , i ) 区间的元素数据相比，若遇到数据比被插入的数据要大，遇到的数据后移一位，若遇到数据比被插入的数据要小，就将被插入的数据插入到该数据的后面。这样排好之后，前两个数据就变得有序了。
第二次插入：i == 2，此时前两个数据是有序的，即是将 array[2]看作是被插入的数据，在往前进行观察选择插入。
......
最后一次插入：i==N -1，此时前N-1个数据是有序的，将array[N-1]看作是被插入的数据，在往前进行观察选择插入。这一趟选择插入之后，这整个数组序列就变得有序了。

三：插入排序——实现

#include<stdio.h>
// 插入排序
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)          // 决定所插入数据的位置 和 决定插入遍历的次数     
	{
		int tem = a[i];                  // 被插入的数据
		int end = i - 1;                 // 决定 与被插入的数据相比较 的区间

		while (end >= 0)                 // 结束条件：全部数据比较完成，该循环目的是：找到比被插入数据要小的值的位置
		{
			if (a[end] > tem)            // 已排好的数组中end的位置上的数 比 所要插入的数 大就交换
			{
				a[end + 1] = a[end];     // 大数往后移一位
				end--;                   // end 往前走一步
			}
			else                         // 有数据比 被插入的数据要小，跳出循环
			{
				break;
			}
		}
		a[end + 1] = tem;                // 将要插入的数插入到 end 位置的后一位。
	}
}

int main()
{
	int a[] = { 29,10,14,37,12,6,32 };
	int sz = sizeof(a) / sizeof(a[0]);     // 获取数组的大小

	printf("插入排序：\n");

    for (int i = 0; i < n; i++)            // 打印排序前的序列
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	InsertSort(a, sz);                     // 执行 插入排序 函数

    for (int i = 0; i < n; i++)            // 打印排序后的序列
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}