Question

插入排序过程详解

Answer 1

从有序数列和无序数列{a2,a3，…，an}开始进行排序；处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，ai-2，…，a1进行比较，找出合适的位置将ai插入；重复第二步，共进行n-i次插入处理，数列全部有序。

注意事项：

折半插入排序是对直接插入排序的一种改良方式，在直接插入排序中，每次向已排序序列中插入元素时，都要去寻找插入元素的合适位置，但是这个过程是从已排序序列的最后开始逐一去比较大小的，这其实很是浪费，因为每比较一次紧接着就是元素的移动。