直接插入排序

1、简单方法首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。注意:若R[i]的关键字大于等于R[1..i-1]中所有记录的关键字，则R[i]就是插入原位置。2.改进的方法一种查找比较操作和记录移动操作交替地进行的方法。具体做法:将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较:① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置;②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。