黑马程序员技术交流社区
标题: 给有序的序列插入一个元素【附详细注释】 [打印本页]
作者: ToBeJeek1 时间: 2015-11-20 23:45
标题: 给有序的序列插入一个元素【附详细注释】
#include <stdio.h>
/**
* 用折半法尝试查找要插入的值,如果查找到,就返回该值的下一个元素的下标,如果没找到,可以返回low所在位置的下标
*
* @param arr 原来的数组
* @param len 数组的长度
* @param key 需要插入的数值
*
* @return 返回插入的地址
*/
int sortInsert(int arr[],int len,int key){
int low=0,high=len,mid;
int flag = 1;
while (flag) {
if (low <= high) {
mid = (low + high)/2;
if (key == arr[mid]) {
flag = 0;
//查找到后插入相同值的后面
return mid+1;
}else if (key > arr[mid]){
low = mid + 1;
}else{
high = mid -1;
}
}else{
flag = 0;
}
}
//没查找到时可以插入low的位置
return low;
}
int main(int argc, const char * argv[]) {
int a[11]={1,4,6,13,16,18,25,37,48,65};
int len = sizeof(a)/sizeof(int);
int key;
int loc;
printf("请输入要插入的数:");
scanf("%d",&key);
loc=sortInsert(a,len,key);
//将所有loc后面的元素往后移动一位
for (int i = len; i > loc; i--) {
a = a[i-1];
}
//将要插入的元素放入loc位置中
a[loc] = key;
//遍历所有元素输出
for (int i = 0; i < len; i++) {
printf("%d ",a);
}
//printf("%d\n",loc);
return 0;
}
作者: Mr.Yan 时间: 2015-11-21 00:14
老师没讲到,但是感觉还是有用的,恩,是这样,受教了.
作者: 打滚的橘子 时间: 2015-11-21 05:10
专门有个插入排序法的说。排序种类超多的,还要考虑复杂度稳定性什么的,昨天给我看晕了。
作者: wx_YXxWrUwd 时间: 2015-11-21 14:52
学习了,排序的方式那么多
作者: zhecipinle 时间: 2015-11-21 20:41
学习学习
作者: ToBeJeek1 时间: 2015-11-22 10:44
Mr.Yan 发表于 2015-11-21 00:14
老师没讲到,但是感觉还是有用的,恩,是这样,受教了.
技术需要分享,快把你的压箱代码放出来吧~
作者: ToBeJeek1 时间: 2015-11-22 10:44
Mr.Yan 发表于 2015-11-21 00:14
老师没讲到,但是感觉还是有用的,恩,是这样,受教了.
技术需要分享,快把你的压箱代码放出来吧~
作者: ToBeJeek1 时间: 2015-11-22 10:47
打滚的橘子 发表于 2015-11-21 05:10
专门有个插入排序法的说。排序种类超多的,还要考虑复杂度稳定性什么的,昨天给我看晕了。 ...
算法是程序的灵魂,而算法又需要数学的思想,因此,数学功底也很重要,如果你想走得更远
作者: ToBeJeek1 时间: 2015-11-22 10:50
wx_YXxWrUwd 发表于 2015-11-21 14:52
学习了,排序的方式那么多
他山之石,可以攻玉,算法不一定都得自己写,如果自己学得太辛苦的话,记得问问度娘
作者: ToBeJeek1 时间: 2015-11-22 10:51
zhecipinle 发表于 2015-11-21 20:41
学习学习
多方涉猎,多方借鉴,大神之路,你我同在!共勉
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |