直接插入排序:改进算法---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