插入排序
插入排序是一种简单直观的排序算法，它逐个将待排序的元素插入到已经排好序的序列中，直到所有元素都插入到正确的位置上。插入排序的基本思想是将待排序的元素插入到已排序的序列中，通过不断将待排序元素与已排序元素进行比较和交换，使得待排序元素有序。

插入排序的算法可以细分为直接插入排序和希尔排序。直接插入排序是最基本的插入排序形式，它假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中。具体操作是将第j个元素放到一个变量T中，然后从有序子表的最后一个元素开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上。

希尔排序是插入排序的一种改进版本，它将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法是将相隔某个增量H的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当H减到1时，进行一次插入排序，排序就完成。希尔排序的效率与增量序列有关。

插入排序的时间复杂度在最坏情况下为O(n^2)，即当输入序列是完全逆序的情况。而在最好情况下，即输入序列已经有序时，时间复杂度为O(n)。插入排序的空间复杂度为常数阶。