频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
排序算法之直接插入排序
2011-10-06 16:31:03      个评论      
收藏   我要投稿

 

基本思想:设置第一个为哨岗,后面一个比较,如果小,大的后移,如果大,插在后面,

然后再取下一个,再往序列里插,后往前比较

 

 

//直接插入排序算法的实现 

//本算法是在参照严蔚敏教材的基础上,为实际运行需要加以改进 

//为了学习需要,我们直接对整数数组进行排序操作,实际稍加修改可用于其它数据结构 

 

#include<stdio.h> 

#define Length 10 

 

//函数声明,函数实现在程序末部分 

void DirectInsertSort(int*,int); 

 

void main() 

    int L[Length]; 

    int i; 

 

    printf("请分别输入%d个整数:\n",Length); 

     

    for(i=0;i<Length;i++) 

    { 

        printf("\n请输入第%d个整数:",i+1); 

        scanf("%d",&L[i]); 

    } 

 

    printf("\n排序前:"); 

    for(i=0;i<Length;i++) 

    { 

        printf("%5d",L[i]); 

    } 

 

    DirectInsertSort(L,Length); 

     

    printf("\n排序后:"); 

    for(i=0;i<Length;i++) 

    { 

        printf("%5d",L[i]); 

    } 

    printf("\n"); 

 

 

//算法实现 

//直接插入排序的算法复杂度是O(n^2),空间复杂度为O(1),仅需要一个辅助空间,也就是本程序中的 

 

fence 

//正序的情况下,需要进行n次比较,逆序情况下,比较次数为O(n^2) 

//正序的情况下,需要进行0次移动,逆序情况下,移动次数为O(n^2) 

//直接插入排序是一种稳定的排序算法 

void DirectInsertSort(int* L,int length){ 

    int i,j; 

    int fence;//哨岗 

 

    for(i=1;i<length;i++) 

        if(L[i]<L[i-1]){ 

          //把小者作为哨岗,即后面位移的参照 

          fence=L[i]; 

          L[i]=L[i-1]; 

         

 

        //通过上面的操作,已经把i-1移到正确的i位置 

        //因而需要把i-1之前的凡是比哨岗大的,便往后挪 

        //最后空出来的位置便是正确的插入位置 

         

        //由于实际应用中,C语言通常是从0开始,所以比原书上多了一个条件 

        //因为如果当i=1,i-2就没有意义了,这时就相当把哨岗作为临时变量作了个交换而已 

        for(j=i-2;j>=0&&L[j]>fence;j--) L[j+1]=L[j]; 

        L[j+1]=fence; 

        } 

 

 }   

 

creat by 张飞雪

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:排序算法之快速排序
下一篇:用UltraEdit打造顺手perl ide
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站