插入排序详解(C语言实现) c语言堆排序代码详解



插入排序详解(C语言实现) c语言堆排序代码详解



插入算法:
以从小到大排序为例

假想,数组已经是有序的,要往数组中插入一个数.
故,只需查找到比要插入的数大的数组元素且在数组中最小的元素.然后插入在这个数组元素之前.

所以可以从数组的第二个元素开始查找(即下标为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

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/356475.html

更多阅读

Adobe Premiere Pro CS4 序列号 premiere pro cs4破解

Adobe Premiere Pro CS4 序列号 ?单单是输入序列号是没什么效果的下次打开 还是会提示你 输入序列号 ??在输入序列号之前添加一段代码就完美了操作如下图选择试用安装安装完成打开 运行一次 然后关闭打开C盘文件 添加代码

用flash8制作MV方法举例:小城故事

用flash8制作MV方法举例:小城故事制作技巧要点1.插入音乐,缩小文件体积2.插入按钮,简单交互语言3.插入文字,歌词歌声同步4.插入图片,多种转场方法效果图:

声明:《插入排序详解(C语言实现) c语言堆排序代码详解》为网友一步毁分享!如侵犯到您的合法权益请联系我们删除