希尔排序.cpp

希尔排序。通过C语言实现。能正常运行。但需要帐户才能下载。请见谅。

#include<stdio.h>
#include<stdlib.h> 
#include<malloc.h>
#define MAXSIZE 100

typedef struct{
	int *elem;
	int length;
}SqList;

void ShellPass(SqList &L,int d,int n)      //希尔排序一趟排序
{
	int i,j;
	for(i=d+1;i<=n;i++)
		if(L.elem[i]<L.elem[i-d])
		{
			L.elem[0]=L.elem[i];               //暂存在L.elem[0]
			j=i-d;
			do{                                 //记录后移
				L.elem[j+d]=L.elem[j];
				j=j-d;
			}while(j>0&&L.elem[0]<L.elem[j]);   
			L.elem[j+d]=L.elem[0];              //插入
		}
}


void ShellSort(SqList &L)                 //希尔排序
{
	int increment=L.length;
	do{
		increment=increment/7+1;
		ShellPass(L,increment,L.length);
	}while(increment>1);
}

void main()
{
  SqList L;
  int n,i;
  L.elem=(int*)malloc(MAXSIZE*sizeof(int));
  if(!L.elem)
  {
	  printf("分配空间失败\n");
      return;
  }
  printf("请输入随机生成数的个数(不大于100个):");
  scanf("%d",&n);
  L.length=n;
  printf("随机生成%d个的数为:\n",n);
  for(i=1;i<=n;i++)
  { 
      L.elem[i]=rand()%1000;
	  printf("%5d",L.elem[i]);
  }
  ShellSort(L);
  printf("\n经过希尔排序后由小到大的顺序为:\n");
  for(i=1;i<=L.length;i++)
	 printf("%5d",L.elem[i]);
  printf("\n");
  return;
}