直接插入排序

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

直接插入排序是一种最简单的排序方法，其思想是：先将序列中的第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