内部排序-直接插入排序

一、概念：

        排序是计算机程序设计中的一种重要运算，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

二、插入排序：

        1. 直接插入排序

        （1）基本思想

            每次将一个待排序的记录，插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

            例：由小到大排序 

        （2）操作：

        设数组为a[0…n-1]。

        直接插入排序即是在要排序的数组中，假设前n-1（n>=2）个数已经是排好序的，现在要把第n个数插入到前n个已经排好序的数组中，使得这n个数也变成有序的，如此反复循环，使得要排序的数组中的最后一个元素也排好序，

        我们可以先假设第一个数是排好序的，然后第二个数和第一个数进行比较，如果第二个数比第一个数大，那么说明前两个数排好序，无需做调整，如果第二个数比第一个数小，那么就把第一个数向后移，将第二个数放在第一个数的位置上，抽象出来就是用a[i]和a[i-1]进行比较，如果a[i]>a[i-1]，那么就说明前i个数是已经排好序的，如果a[i]<a[i-1], 就让j=i-1,temp=a[i],然后一边将数据a[j]向后移动，一边向前搜索，直到找到a[j]<a[i]时停止，并将temp放到a[j+1]处即可。

（3）具体实现：