插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。
【排序过程】
此处同样对数字1~9 进行排序。首先，我们假设最左边的数字5 已经完成排序，所以此时只有5 是已归位的数字。

接下来，从待排数字（未排序区域）中取出最左边的数字3，将它与左边已归位的数字进行比较。若左边的数字更大，就交换这两个数字。重复该操作，直到左边已归位的数字比取出的数字更小，或者取出的数字已经被移到整个序列的最左边为止。

由于5 ＞ 3，所以交换这两个数字。

对数字3 的操作到此结束。此时3 和5 已归位，还剩下右边7 个数字尚未排序。

接下来是第3 轮。和前面一样，取出未排序区域中最左边的数字4，将它与左边的数字5 进行比较。

由于5 ＞ 4，所以交换这两个数字。交换后再把4 和左边的3 进行比较，发现3 ＜ 4，因为出现了比自己小的数字，所以操作结束。

于是4 也归位了。此时3、4、5 都已归位，已排序区域也得到了扩大。

遇到左边的数字都比自己小的情况时……

不需要任何操作即可完成排序。

重复上述操作，直到所有数字都归位。

对所有数字的操作都结束时，排序也就完成了。

在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。
在最糟糕的情况下，第2 轮需要操作1 次，第3 轮操作2 次……第n 轮操作n -1次，所以时间复杂度和冒泡排序的一样，都为 $O(n^2)$。