目录
一 基本思想二 例子三 时间复杂度
一 基本思想
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。
二 例子
private int[] array
= new int[10] {4,5,6,3,2,1,7,8,9,0};
private void InsertSort()
{
for (int i
= 1; i
< array
.Length
; i
++)
{
if (array
[i
] < array
[i
- 1])
{
int temp
= array
[i
];
int j
= 0;
for (j
= i
- 1; j
>= 0 && array
[j
] > temp
; j
--)
{
array
[j
+ 1] = array
[j
];
}
array
[j
+ 1] = temp
;
}
}
}
三 时间复杂度
最好的情况是， 表是有序的， 需要比较 n-1 次，比较操作的时间复杂度是O(n), 移动操作的时间复杂度是0， 总的时间复杂度是O(n)。最坏的情况是，表是反序的， i = 1 时， 需要比较 2 次，移动 1 次 ， i = 2 时 需要比较 3 次，移动 2 次····· i = n - 1 时， 需要比较 n 次， 移动 n-1 次。 因此，总比较次数为 n(n+2)/2，总移动次数为 n²/2 ， 总的比较操作的时间复杂度是 O(n²)， 移动操作的时间复杂度是O(n²)。 总的时间复杂度为比较加移动的时间复杂度， 也就是O(n²)。如果排序记录是随机的， 平均比较次数和移动次数约等于(n²/4)。 同样的时间复杂度 O(n²)， 直接插入排序比冒泡排序和简单选择排序的性能好要一点。
