爱华网
插入算法:
以从小到大排序为例
假想,数组已经是有序的,要往数组中插入一个数.
故,只需查找到比要插入的数大的数组元素且在数组中最小的元素.然后插入在这个数组元素之前.
所以可以从数组的第二个元素开始查找(即下标为1的).依次递增
查找的数组元素满足条件(即比插入的数大的数组元素且下标大于0),交换数组元素的值到下个下标位置.
直到不满足条件,即找到了比要插入的数大的数组元素且在数组中最小的元素.就可以插入元素了
1.用一个循环控制数组中要插入的元素. for(i=1;i<n;i++)
2.用一个循环查找要插入的数在数组中的位置. 直到找到比要插入的数大的数组元素&&在数组中最小的元素&&下标大于0for(j=i;j>0 &&a[j-1]>key;j--)
3.插入元素 a[j] = key;
#include<stdio.h>
#define MAX 8
int main(void)
{
int a[MAX]={8,7,6,5,4,3,2,1};
int i;
void insert(int*a,int n);//函数声明
insert(a,MAX);
printf("after:n");
for(i=0;i<8;i++)
{
printf("%d ",a[i]);
}
printf("n");
return 0;
}
void insert(int *a,int n)
{
int i,j,key;
for(i=1;i<n;i++)//控制需要插入的元素
{
key=a[i]; //key为要插入的元素
for(j=i;j>0 &&a[j-1]>key;j--) //查找要插入的位置,循环结束,则找到插入位置
{
a[j] = a[j-1]; //移动元素的位置.供要插入元素使用
}
a[j] = key; //插入需要插入的元素
}
}
由于嵌套循环的每一个都花费 N次迭代,因此插入排序 为 O(N的2次方);
在另一方面.如果数据是已经排序好的.则运行时间只要O(N),因为内层的for检测总是判定不成立的
所以需要知道插入排序的平均运行时间. 即为 O(N的2次方);
转载请注明出处: http://blog.sina.com.cn/u/1835498344
http://weibo.com/1835498344
