排序算法——直接插入排序

直接插入排序与希尔排序是插入排序的两个分支，直接插入排序是较为简单的一种排序算法，同时也是众多算法实现或优化的基石。

前提：

插入排序：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。

简单来说，就是打斗地主时，你已经摸了几张牌并将牌从小到大排列成有序的概况，这时再摸一张牌，将其也插入到合适的位置，使所有牌继续有序。

算法思想分析：

直接插入排序自然秉承了这一思想，直接插入排序算法的思想是：当插入第i个元素时，arr[0]到arr[i-1]个元素已经排好序，这时用array[i]按与array[i-1],array[i-2],…的顺序依次进行比较，如果找到合适的位置就将arr[i]插入，没找到就继续比较，原来位置的元素顺序后移。

有图有真相：

举个例子：

arr[i]=27,在arr[i]前面的数字已经有序，这时就将arr[i]与arr[i-1]ye也就是27与47比较。

27小，47向后移。

arr[i]再与arr[i-2]也就是44比

，27小，44向后移.......

与arr[i-4](即36)比较，36小,36向后移。

直到遇到arr[i-5]也就是26，27比26大。27插入到原arr[i-4]的位置，单趟排序结束。

代码如下：

这里我们定义一个变量end，假设从a[0]到a[end]范围有序，定义tmp保存下标为第end+1的数。

while循环，如果tmp比它前一个数小，前一个数后移，tmp继续比较。直到遇到比tmp小的或者tmp最小(end=-1,tmp应落到arr[0]位置)，循环结束。将tmp赋给end+1的位置，保持有序。