插入排序
描述
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到下一位置中
- 重复步骤2~5
实现
void InsertSort(int array[], int first, int last)
{
int i, j;
int temp;
//从第二个数开始向后遍历
for (i = first + 1; i <= last; i++)
{
temp = array[i];
//遍历前面的所有数，如果这个数字比temp大，就将数字后移
for (j = i - 1; j >= first; j--)
{
if (array[j] < temp)
break;
else
array[j + 1] = array[j];
}
//将这个数插入到第一个比它小的数字的后边
array[j + 1] = temp;
}
}