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

直接插入排序

•基本思想

•演示

•算法代码

•性能

直接插入排序是指每次从无序表中抽取一个元素插入到一个有序表中的合适位置，待所有元素都插入完后，得到一个新的有序表

具体操作是将一组数的第一个数据看成是一个代排的有序表，从第二个数据开始向有序表中插入数据，在有序表中从后向前依次比较寻求合适的插入位置，直到所有元素都插入完为止

以数据 8、5、2、4、3、1、7、6为例

首先将第一个数8看作一个代排的有序序列，从第二个元素5开始向前插入，5

2从有序表末尾开始依次向前比较，2

按照前面的方式42，则5的位置为插入点，则8和5依次向后移动一位，后续比较都依照此方式，直到所有元素插入完为止，得到新的有序表

32，4的位置为插入点，4、5、8后移一位

1

75，8的位置为插入点，8后移一位

65，7的位置为插入点，7、8后移一位

排序完

C++代码

Python代码

Java代码

直接从插入排序是稳定的排序算法，平均时间复杂度为O(N2),空间复杂度为O(1)