c语言——直接插入排序实现(时间复杂度与空间复杂度分析)

c语言——直接插入排序实现(时间复杂度与空间复杂度分析)

c语言——直接插入排序
插入排序就是将一个记录插入到已排好序的序列中，从而得到一个新的有序序列。

哪里有一个排好序的序列
那问题是我们要排序的是一个数组，哪里来一个排好序的序列呢？这时，我们可以把数组下标为0的元素想像成一个有序的数组，这个数组内只有他一个元素，所以，它总是有序的。后面的元素和他比较。

以升序为例

代码
void insertSort(int n[], int size)
{
for (int i = 1; i < size; i++)
{
for (int j = i; j > 0; j–)
{
if (n[j] < n[j - 1])
{
swap(n[j], n[j - 1]);
}
else
{
break;
}
}
}
}

时间复杂度：乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，因此这段代码时间复杂度为O(n) * O(n) = O(n * n) = O(n*n)。

空间复杂度：直接插入排序中只使用了i,j这两个辅助元素，与问题规模无关，空间复杂度为O(1)。