常见排序算法及对应的时间复杂度和空间复杂度 (2)

•思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。 
•关键问题：在前面已经排好序的序列中找到合适的插入位置。 
•方法： 
–直接插入排序 
–二分插入排序 
–希尔排序

(1)直接插入排序（从后向前找到合适位置后插入）