直接插入排序

插入类排序的基本思想：在一个已排好序的子集的基础上，每一步将下一个待排序的记录有序的插入到已排好序的子集中。

讲的通俗一点，每次我们选取一个待排序记录r(或一个元素)，向前插入，因为我们假设前面是已排好序的，那么我们只需要找到r之前的所有记录中第一个小于r的记录，停下，在这个记录后插入r。(因为是排好序的，所以第一个小于r的记录前面的记录都小于r)，这样就完成了一次插入排序。我们先对前两个记录……