直接插入排序:改进算法---2路插入排序

具体做法:另设一个和L.r同类型的数组d，首先将L.r[1]赋值给d[1],并将的d[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d[1]之前或之后的有序序列中。

  

   

    

     

    
    

     

      # include <stdio.h>
     
    
   

    

     

    
    

     

      # include <iostream.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 InserSort(SqList &L)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int d[MAXSIZE];
     
    
   

    

     

    
    

     

      	d[0] = L.r[1];//L中D的第一个记录为d中排好序的记录。 
     
    
   

    

     

    
    

     
	int first = 0, final = 0;//first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。 
     
    
   

    

     

    
    

     
	for (int i = 2; i <= L.length; ++i)//依次将L的第2个～最后一个记录插入d中。 
     
    
   

    

     

    
    

     

      	{ 
     
    
   

    

     

    
    

     
		if (L.r[i] < d[first])//待插入记录小于d中最小值，插入到d[first]之前（不需移动d数组的元素）。 
     
    
   

    

     

    
    

     

      		{ 
     
    
   

    

     

    
    

     

      			first = (first - 1 + L.length) % L.length;//first始终指向第一个排好序的记录 
     
    
   

    

     

    
    

     

      			d[first] = L.r[i]; 
     
    
   

    

     

    
    

     

      		} 
     
    
   

    

     

    
    

     
		else if (L.r[i] > d[final])//待插入记录大于d中最小值，插入到d[final]之后（不需移动d数组的元素）。 
     
    
   

    

     

    
    

     

      		{ 
     
    
   

    

     

    
    

     
			final = final + 1;   //final始终指向 最后一个排好序的记录 
     
    
   

    

     

    
    

     

      			d[final] = L.r[i]; 
     
    
   

    

     

    
    

     

      		} 
     
    
   

    

     

    
    

     
		else//待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素）。 
     
    
   

    

     

    
    

     

      		{ 
     
    
   

    

     

    
    

     
			int j = final ++;//移动d尾部元素以便按序插入记录。 
     
    
   

    

     

    
    

     
			while (L.r[i] < d[j]) 
     
    
   

    

     

    
    

     

      			{ 
     
    
   

    

     

    
    

     

       d[(j + 1) % L.length] = d[j]; 
     
    
   

    

     

    
    

     

       j = (j - 1 + L.length) % L.length; 
     
    
   

    

     

    
    

     

      			} 
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      		} 
     
    
   

    

     

    
    

     

      	} 
     
    
   

    

     

    
    

     
	for (i = 1; i <= L.length; i++)//循环把d赋给L。 
     
    
   

    

     

    
    

     

      	{ 
     
    
   

    

     

    
    

     

      		L.r[i] = d[(i + first - 1) % L.length];//线性关系。 
     
    
   

    

     

    
    

     

      	} 
     
    
   

    

     

    
    

     
	cout<<"最后的排序结果是:";//打印排序结果。 
     
    
   

    

     

    
    

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

    

     

    
    

     

      	{ 
     
    
   

    

     

    
    

     
		cout << L.r[i] <<" ";   
     
    
   

    

     

    
    

     

       }   
     
    
   

    

     

    
    

     
	cout << endl;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	SqList L;
     
    
   

    

     

    
    

     

      	CreateSqList(L);
     
    
   

    

     

    
    

     

      	InserSort(L);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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