黑马程序员技术交流社区

标题: 给有序的序列插入一个元素【附详细注释】 [打印本页]

作者: 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