排序算法(一)：插入排序(直接插入排序、希尔排序)

一、直接插入排序

1.算法思想

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