插入排序的基本思想是将后面的元素逐个插入到有序数列中

插入排序的C实现:

void insertion(int *n, int len)
{
    int i, j;
    for (i=1; i<len; i++) {
        for (j=i; j>0 && *(n+j) < *(n+j-1); j--) {
            swap(n+j, n+j-1);
        }
    }
}

插入排序最差情况的计算次数为\(1 + \cdots + (n-2) + (n-1) = n (n -1) / 2\) , 由此可知插入排序的时间复杂度为\(O(n^2)\) (与冒泡排序相同), 插入排序需要的额外空间为\(O(1)\) , 插入最优情况下时间复杂度接近\(O(n)\) , 插入排序是稳定的.

comments powered by Disqus