黑马程序员技术交流社区

标题: 浅谈对C语言中三种排序算法的理解---插入排序法 [打印本页]

---

作者: 邹志鹏    时间: 2014-12-5 10:51
标题: 浅谈对C语言中三种排序算法的理解---插入排序法
       一、插入排序法
        算法分析：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在未找到插入点之前可以同时向后移动元素，为插入元素准备空间。
        算法特点：每趟从无序序列中取出第一个数插入到有序序列的合适位置，元素的最终位置在最后一趟插入后才能确定位置。也可是先用循环查找插入位置（可从前往后或从后往前），再将插入位置之后的元素（有序列中）逐个后移一个位置，最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前，则可将两个操作结合在一起完成，提高算法效率。仍可进行升序或降序排序。
        算法举例：
        for(i=1;i<10;i++) //外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入

  {

    t=a;     //将待插入数暂存于变量t中

    for( j=i-1 ; j>=0 && t>a[j] ; j-- ) //在有序序列（下标0 ~ i-1）中寻找插入位置

      a[j+1]=a[j]; //若未找到插入位置，则当前元素后移一个位置

    a[j+1]=t;        //找到插入位置，完成插入

  }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2