直接插入排序是一种最简单的排序方法，其基本操作是将需要排序的元素插入到已排好的有序表序列中，从而得到一个完整的有序序列。

①将待排序序列分为两部分，一部分有序一部分无序。 ②我们把第一个元素看作有序序列，从第二个元素到最后为无序序列。 ③将无序序列中每一个元素依次插入到有序序列的合适位置–从小到大（从大到小）。

我们有一个待排序序列为【3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

1、我们将第一个元素3看成已经排序好的序列，即有序序列。 2、从第二个元素44到最后一个元素48我们看作为无序的的序列，即待排序的序列。 3、我们将待排序序列中的第一个元素【44】，插入到有序序列中。 ①待排序元素【44】和有序序列中元素【3】进行比较，【44】比【3】大则直接插入到有序序列中。

②此时有序序列为【3,44】，待排序序列为【38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】 3、我们将待排序序列中的第一个元素【38】，插入到有序序列中。 ①待排序元素【38】和有序序列中元素【44】进行比较，【38】比【44】小，则将【44】向后移动，然后在将【38】和【3】进行比较，【38】大于【3】则将元素【38】插入到【3】位置后。 注意： 需要将待排序元素与有序序列中的每一个元素进行比较。

②此时有序序列为【3,38,44】，待排序序列为【 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】 4、然后按照以上操作，将待排序序列中的元素依次插入到有序列中。

小结： 待排序元素比有序元素元素大则直接插入到该有序元素后，若小于有序元素则将该有序元素向后移动。

O(n2)

O(1)

稳定的排序算法，其稳定性在于相同值的元素进行插入排序完成后相对位置不发生改变。