插入排序简单来说 假设数组第一个元素为一个有序序列 然后将后面的无序序列依次与第一个元素比较 更具大小决定待插入元素插入的位置。
、、、
// 插入排序 是吧无序序列中的元素依次插入到有序序列中，一般是从有序序列的尾部开始比较
void InsertSort(int buf[10], int bufsize)
{
int temp = 0; // 用于备份当前待插入元素的值
int current_prev = 0; // 备份待插入元素的下标(2)
// 可以假设把数组中的第一个元素座位有序序列的元素，剩下的元素作为无序序列
for (int i = 1; i < bufsize; ++i) //(1)
{temp = buf[i]; // 备份当前待插入元素的值// 把当前待插入元素和有序序列中的元素依次进行比较，从有序序列尾部开始for (int j = i - 1; i >= 0; j--){if (temp < buf[j]) // 当前插入元素的值 小于待插入元素的直接前驱元素的值{current_prev = j; // 备份当前待插入元素的直接前驱的下标(3)buf[j + i] = buf[i]; // 后移}else{current_prev = j + i;break;}}// 把待插入元素插入指定位置buf[current_prev] = temp;
}
}、、、
本题需要思考的两个问题
1.为何 （1）int i 从1 开始i++
答：已经假设了第一个下标为0 的元素为一个有序数列 没必要自己和自己再比较
2.为何 （2）（3）要对待插入元素的下标进行备份？
答：如图这种情况
会发现插入之前 i=1 j=0，当j进行j--时 j=-1 ，不满足第二个for循环，下标为负数没有意义 ，知道temp=3但是不知道它插入位置的下标。
此时在第二个for循环中备份 j=0当前下标的地址[current_prev] temp就有目标元素下标进行插入 ，j等于-1则不进入第2个for循环 。****
