插入法相对较复杂，基本原理是抽出一个数据，在前面数据中寻找相应的位置插入，然后继续下一个数据，直到排序完成

以9、6、15、4、2为例来进行插入法排序

从表中可知，第一次排序将第一个元素放在首位，然后取出第二元素与其比较，如果小于第一个数则放在第一个数左边，反之则放在右边。以此类推，将元素逐个取出与前面的相比较，直到最后一个元素找到相应的位置放入

下面通过代码实现

#include<stdio.h>
int main()
{
	int arr[10];                      /*定义一个10个元素的数组*/ 
	int i,j,temp,pos;                 /*temp记录最小值，pos记录最小值位置*/
	for(i=0;i<=9;i++)                 /*输入各个数字*/
	{
		scanf("%d",&arr[i]);
	}
	for(i=1;i<10;i++)                  /*从数组的第二个元素开始循环*/
	{
		temp=arr[i];                  /*设置插入值*/ 
		pos=i-1;                      /*记录插入值前一个位置*/ 
		while(pos>=0&&temp<arr[pos])  /*与前面数逐个比较寻找插入值的位置*/ 
		{
			arr[pos+1]=arr[pos];      /*插入数值*/ 
			pos--;
		}
		arr[pos+1]=temp;
	}
	for(i=0;i<=9;i++)                  /*输出排序后的数组*/
	{
		printf("%d ",arr[i]);
	}
	return 0;
 } 

插入法排序共需要进行n-1次取出元素并寻找位置插入，因此当序列较为有序时，插入排序有较快的运算速度

（只是一个数组题目罢了）

直接插入排序，是指将无序序列中的各元素依次插入到已经有序的数组中。

假设数组中前i-1元素已经有序，现在要将线性表中第i个元素插入到前面的有序子表中，插入过程如下：

以长度为n=8的序列（13，6，1，31，9，27，5，11）的插入排序过程做示范： 第1趟：将数组第2个元素6向前插入后，则数组中元素为（6，13，1，31，9，27，5，11）； 第2趟：将数组第3个元素1向前插入后，则数组中元素为（1，6，13，31，9，27，5，11）； 第3趟：将数组第4个元素31向前插入后，则数组中元素为（1，6，13，31，9，27，5，11）； …… 第7趟：将数组第8个元素11向前插入后，则数组中元素为（1，5，6，9,11，13，27，31）； 总之，共执行7趟操作，可将有n=8个元素的数组排成有序序列。

插入排序从第二个数开始，拿出第二个数向前进行插入排序，一直到最后一个数向前做插入排序，要求输出每趟插入排序的结果。

测试输入：

10

47 47 21 69 2 8 76 50 9 47

预期输出：

47 47 21 69 2 8 76 50 9 47

21 47 47 69 2 8 76 50 9 47

21 47 47 69 2 8 76 50 9 47

2 21 47 47 69 8 76 50 9 47

2 8 21 47 47 69 76 50 9 47

2 8 21 47 47 69 76 50 9 47

2 8 21 47 47 50 69 76 9 47

2 8 9 21 47 47 50 69 76 47

2 8 9 21 47 47 47 50 69 76

提示： 如果有10个整数，要求输出每趟插入排序共9趟的结果。

这里我调用了自定义函数来实现程序，真正编写时可以不用函数。具体怎么做，就请读者自己思考啦。

编写程序：

#include<stdio.h>
#define N 100
int ONE (int a[],int n)
{
	int i,m;
	for (m=2;m<n+1;m++)
	{
		a[0]=a[m];
		for(i=m-1;i>=1;i--)
		{
			if (a[0]<a[i])
				a[i+1]=a[i];
			else break;
		}
		a[i+1]=a[0];
		for(i=1;i<=n;i++)
			printf("%d ",a[i]);
		printf("\n");
	}
	
}
int main()
{
	int a[N],n,i;
	scanf ("%d",&n);
	for (i=1;i<=n;i++)
		scanf ("%d",&a[i]);
	printf ("\n"); 
	ONE(a,n);
	return 0;
}

运行结果：

 运行成功！

C语言数组+冒泡排序

一、数组知识点

二、冒泡排序
从大到小基本思想： 每趟将相邻两个数字依次比较，将大的调到前面，最终每趟会将最小的沉到最后（这也是起名为冒泡的原因，大的向上冒泡，小的向下沉）。如果有n个数字，则要进行n-1趟比较，第一趟比较中要进行n-1次的两两比较，在第i趟要进行n-1-i次的两两比较。

示例代码：

//把一个整数插入从小到大排好序的数组中，要求新的数组仍然满足从小到大的顺序
int data[10]={66,33,126,128,888,10,67,54,20,16};
	int temp=0;
	for(int i=0;i<10-1;i++)
		for(int j=0;j<10-1-i;j++)
			if(data[j]<data[j+1])
			{
				temp=data[j];
				data[j]=data[j+1];
				data[j+1]=temp;
			}
    printf("数据从大到小排序如下:\n");
	for(i=0;i<10;i++)
		printf("%d ",data[i]);
	printf("\n");
	printf("请插入一个数字\n");
	int interNum;
	scanf("%d",&interNum);
	for(i=0;i<10;i++)
	{
		if(data[i]<=interNum)
		{
			for(int s=9;s>=i;s--)
				data[s+1]=data[s];
			break;
		}
	}
	data[i]=interNum;
	printf("插入数字后的排序如下:\n");
	for(i=0;i<11;i++)
		printf("%d ",data[i]);
	printf("\n");