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

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

      # 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