排序算法之直接插入排序



	 

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

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

	 

	 

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

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

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

	 

	#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 张飞雪

补充：软件开发 , 其他 ,