插入排序

直接插入排序

插入排序是对少量元素进行排序的有效算法,各个数字是原地排序,插入排序是稳定的。
算法思想:将一个元素通过和当前已经排序好的数组的最大元素进行比较,并在待插入数组较小的情况下通过设置哨兵,整体移动,插入正确位置,从此得到一个新的排序好的数组的过程。

算法导论中的伪代码:

△INSERT-SORT(A)
for j ← 2 to length[A]
do key ← A[j]
△Insert A[j] into the sorted sequence A[1..j-1].
i ← j-1
while i>0 and A[i]>key
do A[i+1] ← A[i]
i ← i-1
A[i+1] ← key

Continue reading