插入排序

对于插入排序,我理解的原理是这样的(假设是升序):
第一个元素不用排序,从第二个元素开始,与前面的元素比较,如果小于前面的元素就把前面的元素赋值给后面的元素.
前两个元素排好序以后,紧接着与第三个元素进行比较将这三个元素进行排序.
……..
如下图所示:

代码如下:

void InsertSort(int arr[],int size)
{
    if(size <= 1)
    {
        return;
    }
    int bound = 0;
    for(bound = 1;bound < size;++bound)
    {
        int value = arr[bound];
        int j = bound;
        for(;j > 0;--j)
        {
            if(arr[j - 1] > value)   //注意!!!!:这里要和需要插入的值进行比较
            {
                arr[j] = arr[j - 1];
            }
            else
            {
                break;
            }
        }
        arr[j] = value;
    }
}

时间复杂度

两层for循环排序,最坏的情况下时间复杂度为O(N^2).
所以时间复杂度为O(N^2).

空间复杂度

并没有额外的开辟空间,所以空间复杂度为O(1).