概念
插入排序就是把数组分为两个区间,一个是有序区间,一个是未排序区间。初始的时候有序区间就只有一个元素,那就是数组的第一个元素,然后取未排序区间中的元素往有序区间中插进去,一直等到未排序区间中的所有元素为空。
int[] t = new int[10] { 54, 23, 43, 2, 3, 5, 1, 2, 6, 7 };
for (int i = 0; i < t.Length; i++)
{
int v = t[i];
int j = i - 1;
for (; j > 0; --j)
{
if (v > t[j])
{
t[j + 1] = t[j];
}
else
{
break;
}
}
}
for(int i = 0; i < t.Length; i++)
{
Console.WriteLine("{0}={1}", i, t[i]);
}
-
插入排序算法不需要额外的空间,所以它的空间复杂度为o(1),是原地排序算法。
-
插入的时候只是插到它所需要的位置,不会修改它后面位置的顺序,所以是稳定排序算法。
-
最好情况下,我们要排序的数据是有序的,所以我们只需要做o(n)的时间复杂度。最坏的情况下,我们要排序的数据是逆序的,所以我们要做o(nn)的时间复杂度。在数组中插入一个数据的时间平均时间复杂度是o(n),我们需要执行n次操作,所以平均时间复杂度是o(nn)。