直接插入排序

从今天起，开始写排序程序，所有思想均来自 严蔚敏老师的数据结构第三版

直接插入排序是一种最简单的排序方法，其思想是：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入(从待插入的记录起向左查找插入的位置)，直至整个序列变成按关键字非递减有序序列为止。

有了这个我们就好编程实现了

  

   

    

     

    
    

     

      # include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      # define MAXSIZE 20
     
    
   

    

     

    
    

     

      typedef int KeyType;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	KeyType r[MAXSIZE+1];
     
    
   

    

     

    
    

     
	int length;
     
    
   

    

     

    
    

     

      }SqList;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void CreateSqList(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,n;
     
    
   

    

     

    
    

     
	printf("请输入待排序数据的长度:");
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

     
	printf("请输入待排序的数据:");
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

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

    

     

    
    

     

      	{
     
    
   

    

     

    
    

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

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	L.length = n;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Display(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

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

    

     

    
    

     

      	{
     
    
   

    

     

    
    

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

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void InserSort(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i,j;
     
    
   

    

     

    
    

     
	for (i=2; i<=L.length; ++i) //第2个记录开始插入有序序列
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (L.r[i] < L.r [i-1])//如果待插入的数据比前一个小，则需要将其插入有序序列
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			L.r[0] = L.r[i];//待插入的数据复制为哨兵
     
    
   

    

     

    
    

     

      			L.r[i] = L.r[i-1];//为什么不将这步省掉，而直接将j的初值定为i-1?
     
    
   

    

     

    
    

     
			for (j=i-2; L.r [0]<L.r [j];--j)
     
    
   

    

     

    
    

     

      			{//待插入的数据继续与前面的数据比较，如果小，则前面的数据需往后移。
     
    
   

    

     

    
    

     

      			L.r [j+1] = L.r [j];
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		L.r [j+1] = L.r [0];//插入到正确的位置
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("第%d趟排序结果为: ", i-1);
     
    
   

    

     

    
    

     

      		Display(L);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	SqList L;
     
    
   

    

     

    
    

     

      	CreateSqList(L);
     
    
   

    

     

    
    

     

      	InserSort(L);
     
    
   

    

     

    
    

     
	printf("最后的排序结果是:");
     
    
   

    

     

    
    

     

      	Display(L);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/6824386