#include <stdio.h>
#include<conio.h>
/*----------
*INSERT_SORT
*
* args
* A[] int[],the number of A arrary
* len int ,A length
*
------------*/
void insert_sort(int A[],int len){
int i,j,key
//printf("A length %d\n",len) //output arrary length
for(j=1j<lenj++){
key=A[j]
i=j-1
while (i>-1&&A[i]>key) { //i from 0 to 5,so i>-1
A[i+1]=A[i]
i=i-1
A[i+1]=key
}
}
//output A arrary
for(i=0i<leni++)
printf("%d ",A[i])
}
int main()
{
int A[10]
int i=0
char c
while(1){
scanf("%d",&A[i])//input unmbers
c=getchar()
if(c=='\n')
break
i++
}
//printf("%d %d %d %d %d %d %d %d\n",A[0],A[1],A[2],A[3],A[4],A[5],A[6],A[7])
//use insert_sort
insert_sort(A,i+1)//A length is i+1
return 0
}
/*---test------------
* input 5 2 4 6 1 3
*
* output 1 2 3 4 5 6
* ------------------*/
以上程序使用的是Qt Creator 工具，用C语言实现，经调试已经通过。
但依然有个问题：在main（）函数中调用insert_sort(int A[])时，若单传数组参数A[]，再在insert_sort(int A[])函数里面调用len=sizeof(A)/sizeof(int)计算数组实际输入长度，但是得不到实际输入的数组长度，所以只能采用实参的方式将具体数字通过len传到insert_sort(int A[],int len )；在insert_sort(int A[])接收到A数组后直接计算A[]实际输入长度，有什么办法可以实现？
插入排序(insertion sort)
如果需要对一个小型数组进行升序排列，那么可以选用插入排序，插入排序可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。
可以把左手中的牌比做已经摸起的牌，即已经被排列好的牌，左手可以容纳的牌数的空间可以假想为和要摸的牌的总数相同；而在桌子上的那部分没摸的牌则是未被排序的牌，这二者的关系可以抽象为数组中已经被排序好的部分和未被排序好的部分。
一开始摸起的第一张牌不需要排序，可以认定其为已排序的牌。
如果用外层循环for来表示摸起的牌的话，则可以抽象为：
// 对象数组
// 桌子上的牌
int A[] = {5,1,3,6,2,4}
// 从数组的第二个元素开始抽取
for(int i = 1i <sizeof A/sizeof A[0]++i)
{
int pick = A[i]// 被摸起的牌
int j = i - 1// j记录已排序部分的最后一张牌的位置
. . .
}
而后摸起的排要根据排列策略和先前摸起的牌的点数的大小来确定其插入的合适位置，这里示范的排列策略是升序排列，摸起了这张牌后，便自右向左地和手中的牌进行比较。
把pick称作摸起的牌，如果pick比手中的牌小，则手中较大的那张牌就向右挪一位，pick再和下一张牌做比较，如果下一张牌仍然比pick大，那么那张牌便也向右移动一个位置，依此类推。
如果手中下一张和pick比较的牌比pick小，那么pick就被插入在了手中前一张牌移动后空下的位置；
或者手中所有的牌都比pick大，那么所有的牌就都向右移动过一个位置，所以pick最终被插入在了手中最左边的位置。
这个过程可以抽象为：
// 对象数组
// 桌子上的牌
int A[] = {5,1,3,6,2,4}
// 从数组的第二个元素开始抽取
for(int i = 1i <sizeof A/sizeof A[0]++i)
{
int pick = A[i]// 被摸起的牌
int j = i - 1// j记录已排序部分的最后一张牌的位置
// 如果循环了j+1次，即j = -1时还未找到比pick小的牌
// 那么pick就是最小的牌被插入在位置A[0]处
// A[j]是当前手中和pick进行比较的牌
while(j >= 0 &&A[j] >pick)
{
// 未找到可插入位置，则A[j]向后挪一位
A[j+1] = A[j]
// j减1继续向左定位手中下一张供和pick比较的牌--j
}
// while结束后，j+1所表达的位置便是pick可以插入的位置
A[j+1] = pick
}
// 对于有N个元素的数组A，采用插入排序法排序时，当外层循环进行了N-1次后排序完毕
算法描述一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
范例程式码
void insertion_sort(int array[], int first, int last)
{
int i,j
int temp
for (i = first+1i<=lasti++)
{
temp = array[i]
j=i-1
while((j>=first) &&(array[j] >temp))
{
array[j+1] = array[j]
j--
}
array[j+1] = temp
}
}
