插入排序算法是把要排序的数组分成前后两个部分：前面部分为排序好的元素，后面部分为数组的其他所有元素。从后部分第1个元素开始，逐个将元素插入前一部分合适的位置中去。插入时，前部分中比该元素大的元素后移。

第1遍，第0个元素作为前一部分，第1～n-1个元素为后一部分。取出第1个元素暂存于变量temp，并将temp与第0个元素比较，如果元素0较大，就将第0个元素后移到位置1，将temp放到移动后空出的位置0；否则，放到位置1。这时第0～1个元素完成排序。

第2遍，把已排序的第0、1个元素作为前一部分，第2个元素开始作为后一部分。将第2个元素取出暂存于变量temp，前一部分中所有比temp大的元素后移一位，直到元素比temp小为止，然后将temp放到移动后空出的位置。

第i遍，这时第0～i-1个元素作为前一部分已排序，第i个元素开始到最后作为后一部分。将第i个元素取出暂存于变量temp，同样将所有比temp大的元素后移一位，将temp放到移动后空出的位置。如此循环，直至排序完成。如图9-4所示。

图9-4 插入排序算法(www.daowen.com)

【例9-21】使用插入法对一无序数组进行排序。

程序思路：将n个元素的数组分成0～i-1和i～n-1两个部分，其中前面的0～i部分已经排序。取出第i个元素存放于temp，然后将前面第0～i-1部分的元素进行移位，腾出与取出的第i个元素的值相适合的位置，将取出的temp放入。程序使用两层循环，外循环控制后半部分未排序的内容，循环计数i从1到n-1；内循环控制第i个元素之前的已排序部分的比较过程，内循环计数j从i-1开始减1计数，将第j个元素a[j]与temp比较，当a[j]＞temp时a[j]后移一位，直到a[j]＜temp时停止内循环，在j+1的位置插入temp。

程序运行结果：（略，结果同例9-19）