c语言插入法排序的算法步骤

任何一本数据结构的书，在排序一章有详细的介绍。

步骤
⒈从有序数列{a1}和无序数列{a2,a3，…，an}开始进行排序；
⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；
⒊重复第二步，共进行n-i次插入处理，数列全部有序。

算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
范例程式码
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;

while((j>=first) && (array[j] > temp))
{
array[j+1] = array[j];
　j--;
}
array[j+1] = temp;
}
}

插入排序法的基本操作就是将一个数据插入到已经排好序的有序数据中（初始时可以认为只有一个元素的序列是有序的序列，即从第二个数据起开始逐个插入），从而得到一个新的、个数加一的有序数据。
该算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的序列中适当位置上，直到全部插入完为止。
为避免反复比较是否越界，下面的插入排序使用了“哨兵”。即在插入的尽头，复制一个待插入数据的副本（a[0]），一身二用，既作为保存数据，又有效防止搜索时越界而反复检测是否越界。每一轮中，比待插入的数大的数，逐个后移一位，最后把a[0]正确放置到位。
1）a[1]~a[n]中存放数据,i=2
2）a[0]=a[i]，j=i;
3）若a[j-1]>a[0]，则a[j]=a[j-1]，然后j--;　　再转3）
4）a[j]=a[0];
5）i++; 若i<=n，则j=i，转3），否则结束。
排序结束后a[1]~a[n]即为升序的序列。