插入排序:保护一个有序区,把元素一个个插入有序区的适当地位,直到所有元素都有序为止。
例子:无序数组:[5,8,6,3,9,2,1,7]
第一轮:让元素 8 和有序区 [5] 的元素顺次比拟。
8>5,所以元素 8 和元素 5 毋庸替换。
此时有序区的元素减少到两个:[5,8]
第二轮:让元素 6 和有序区 [5,8] 的元素顺次比拟。
6<8,所以把元素 6 和元素 8 进行替换。
6>5,所以元素 6 和元素 5 毋庸替换。
此时有序区的元素减少到 3 个:[5,6,8]
第三轮:让元素 3 和有序区的元素顺次比拟
3<8,所以把元素 3 和元素 8 进行替换
3<6,所以把元素 3 和元素 6 进行替换
3<5,所以把元素 3 和元素 5 进行替换
此时有序区的元素减少到了四个[3,5,6,8]
优化:
第三轮循环,把元素用 inserValue 存起来,把有序区的元素从前向后逐个复制。
第 1 步:暂存元素 3,inserValue
第 2 步:和前一个元素比拟,因为 3 <8,复制元素 8 到它下一个地位。
第 3 步:和前一个元素比拟,因为 3 <6,复制元素 6 到它下一个地位。
第 4 步:和前一个元素比拟,因为 3 <5,复制元素 5 到它下一个地位。
第 5 步:把暂存的元素 3 赋值到数组的首位。