概念：顺序的把带排序的数据元素按其关键字值的大小插入到已经排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始，逐次增大，当子集合大小最终和集合大小相同时，排序完毕。
设待排序的n个数据元素存放在数组a中，初始时，子集合a[0]已经排好序，第一次循环准备把a[1]插入到已经排好序的子集合中。这时只需要比较a[0],a[1]即可。若a[0]<=a[1],
则说明序列有序，否则将a[1]插入到a[0]的前面去。此时子集合的大小增大为2，第二次循环准备把数据元素a[2]插入到已经排好的子集合中，这需要先比较a[2]和a[1]以确定是否把a[2]插入到a[1]之前，然后比较a[2]和a[0],以确定是否把a[2]插入到a[0]之前。该循环一直进行到a[n-1]插入完为止。以下为完整的代码：
void InsertSort(int a[],int n)
{
int temp;
for (int i = 0; i < n-1; i++)
{
temp = a[i+1];
int j = i;
while (j > -1 && temp < a[j])
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
}
int a[10] = {64,5,7,89,6,24};以该数组为例。
我们首先是比较a[0],a[1]。显然5是小于64的，所以需要插入。数组中的插入思路是先保存a[1]即，temp = a[1],然后在将a[1] = a[0]。最后将temp赋值回a[0]。
所以我们写temp = a[i+1],注意我们需要遍历整个数组，但是不要越界，所以i+1 所以我们构建如下循环循环： int temp; for (int i = 0; i < n-1; i++) { temp = a[i+1]; } 接下来我们需要比较a[i]和a[i+1],但是i是不能随意更改的，所以我们新建j来替代i的功能，且我们需要从后向前比较，所以j--(注意j>=0)，当后一个比前一个小时，就需要执行插入的操作 所以我们在循环中添加如下代码： int temp; for (int i = 0; i < n-1; i++) { temp = a[i+1]; int j = i; while (j > -1 && temp < a[j]) { a[j + 1] = a[j]; j--; } } } 最后当我们找到需要插入的位置时我们需要将temp反赋值回去，当我们的 temp < a[j]不满足的时候，其上一位就是我们需要插入的位置，即a[j++] = temp。或者我们可以这样思考，第一次插入的时候j=-1,此时我们要插入的位置为a[0]。 所以我们最后完成的代码为： void InsertSort(int a[],int n) { int temp; for (int i = 0; i < n-1; i++) { temp = a[i+1]; int j = i; while (j > -1 && temp < a[j]) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; for (int i = 0; i < 6; i++) { cout << a[i] << " "; } cout << "n"; } }
