经典排序算法-----直接插入排序（C语言实现）

算法表述：

直接插入排序的基本原理就如同打扑克牌一样，起初在摸牌的时候，第一张牌对于自身而言是有序的，假如摸到4，当第二次摸到6时，会将6放在4的后面，第三次摸到3时，会将3放在4的前面，这个过程就是直接插入排序。那么对于6和3而言，如何知道是大还是小呢？过程很简单，每摸到一张牌就和前面已有序数列作比较比较，然后交换顺序即可。

算法执行过程分析：

例如:8、45、18、33、15、99、3 说明：按照从小到大的顺序进行排序。

具体实现步骤如下：设置一个临时变量temp，其值为当前所摸牌的值，然后和它的前一张牌（即已有序列的最后一张牌）开始比较，如果temp小于前一张牌的值，就把前一张牌放在当前位置，结果比较有序序列的倒数第二位置，如果再小，重复上述步骤，如果大于，由于比较的是有序序列，故此是为有序状态，最后把temp的值放在和有序序列中最后一个比较的值的下一位置当有序之后，退出循环。具体可根据下述图进行自行分析。 备注：

其中i表示当前所摸的牌，j表示已有序数列的最后一张牌，从后往前比较。其中蓝色空格为temp的值,不代表方框中的值,彩色线条为两数之间的比较。以下每一步均为比较完变化后的结果。

(1)第一趟排序：

(2)第二趟排序：

以此类推... (3)第六趟排序：

此时待排序列已全部有序。 拓展：n个数排序需要n - 1躺。

代码实现：

void Insert_sort(int *arr,int len) { for(int i = 1;i < len;i++) //由于temp的初值为第二个数，故i为1 { int temp = arr[i]; int j = 0; for(j = i-1;j >=0;j--) { if(arr[j] > temp) { arr[j+1] = arr[j]; } else { break; } } arr[j+1] = temp; } }

总结：

由前面所介绍，直接插入排序是将一个数与一组已排号顺序的序列中的最后一个数进行比较。如果序列自身有序，则仅仅执行了外层循环，时间复杂度为O（n）；如果序列自身是无序的，那么其时间复杂度为O（n^2）（可根据上述图片进行具体分析）。因此可以得出直接插入排序的一个特点-----越有序越快。由于使用了辅助空间temp。故其空间复杂度为O（1）。直接插入排序是一种稳定的排序算法。