这就是插入排序，先给个思路，后给代码：
介绍：
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。
思路：
将n个元素的数列分为已有序和无序两个部分，如下所示： {，{a2，a3，a4，…,an}} {{a1(1)，a2(1)}，{a3(1)，a4(1) …,an(1)}} … {{a1(n-1)，a2(n-1) ，…}, {an(n-1)}} 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
步骤：
1.从有序数列和无序数列{a2,a3,…,an}开始进行排序； 2.处理第i个元素时(i=2,3,…,n) , 数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1，a i-2,…,a1进行比较,找出合适的位置将ai插入； 3.重复第二步，共进行n-1次插入处理，数列全部有序。
代码：
void InsertSort(char array[],unsigned int n)
{ int i,j; int temp; for(i=1;i<n;i++)
{ temp = array;//store the original sorted array in temp
for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
{ array[j]=array[j-1];//all larger elements are moved one pot to the right }
array[j]=temp;
}
}
“数姐”