直接插入排序:改进算法---折半插入排序

这种改进是从比较次数入手的，并没用减少移动的次数

  

   

    

     

    
    

     

      # 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;
     
    
   

    

     

    
    

     
	int low,high,mid;
     
    
   

    

     

    
    

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

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      			low = 1;
     
    
   

    

     

    
    

     

      			high = i-1;
     
    
   

    

     

    
    

     
			while (low <= high)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       mid = (low+high)/2;
     
    
   

    

     

    
    

     
 if (L.r[0] < L.r[mid])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       high = mid-1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       low = mid+1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
			
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			
     
    
   

    

     

    
    

     
			for (j=i-1; j>=high+1; --j)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      			L.r[high+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/6827526