这是我们的课程设计题目，我自己实现了三个，发出来看是不是对大家有用：
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#include"conio.h"
#define Maxsize 1000000 //线性表存储空间的初始分配量
#define Listcrement 1000000 //线性表分配空间的分配增量
#define ERROR 0
typedef struct
{
long int key;
char key2;
}Red;
typedef struct
{
Red *elem; //存储空间基址
long int length; //当前长度
long int listsize; //当前分配的存储容量
}Sqlist;
//以下是输出函数
void output(Sqlist &L)
{
FILE *fp;
long i;
char outfile[20];
printf("输入文件名(保存):\n");
scanf("%s",outfile);
if((fp=fopen(outfile,"w"))==NULL)
{
printf("Cannot open the file.\n");
exit(0);
}
for(i=2;i<=L.length;i++)
{
fprintf(fp,"%ld (%c)\n",L.elem[i].key,L.elem[i].key2);
}
fclose(fp);
}
//输出函数到此结束
//以下是希尔排序
void ShellInsert(Sqlist L,int dk)//一趟增量为dk的希尔插入排序
{
long i,j;
for(i=dk+1;i<=L.length;++i)
{
if(L.elem[i].key<L.elem[i-dk].key) //小于时，需将L.r[i]插入有序增量子表
{
L.elem[0].key=L.elem[i].key; //暂存在L.r[0]单元
L.elem[0].key2=L.elem[i].key2;
for(j=i-dk;j>0&&L.elem[0].key<L.elem[j].key;j-=dk)
{
L.elem[j+dk].key=L.elem[j].key; //记录后移，查找插入位置
L.elem[j+dk].key2=L.elem[j].key2
;
}
L.elem[j+dk].key=L.elem[0].key; //插入
L.elem[j+dk].key2=L.elem[0].key2;
}
}
}
void ShellSort(Sqlist L,int dlta[],int t)//按增量序列dlta[0..t-1]对顺序表L作希尔排序
{
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); //一趟增量为dlta[k]的希尔插入排序
}
}
//希尔排序到此结束
//以下是输入函数
Sqlist Input(Sqlist &a)
{
FILE *fp;
Red *newbase;
long i=1;
char filename[100];
printf("输入文件名及路径：");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("Can not open the file!\n");
exit(0);
}
a.elem=(Red*)malloc(Maxsize*sizeof(Sqlist));//构造一个空的线性表
if(!a.elem)
exit(0);//存储分配失败
a.length=0;//空表长度
a.listsize=Maxsize;//初始存储容量
while(!feof(fp))
{
if(a.length>=a.listsize)//当前存储空间已满，增加分配
{
newbase=(Red*)realloc(a.elem,(a.length+Listcrement)*sizeof(Sqlist));
if(!newbase)
exit(0); //存储分配失败
a.elem=newbase; //新基址
a.listsize+=Listcrement;//增加存储容量
}
fscanf(fp,"%ld (%c)",&a.elem[i].key,&a.elem[i].key2);
i++;
++a.length;
}
return a;
}
//输入函数到此结束
//以下是快速排序
long Partition(Sqlist &L,int low,int high)//交换顺序表L中子表
{
Red pivotkey;
L.elem[0].key=L.elem[low].key;
L.elem[0].key2=L.elem[low].key2;
pivotkey.key=L.elem[low].key;
pivotkey.key2=L.elem[low].key2;
while (low<high)
{
while (low<high && L.elem[high].key>=pivotkey.key)
{
--high;
}
L.elem[low].key=L.elem[high].key;
L.elem[low].key2=L.elem[high].key2;
while (low<high && L.elem[low].key<pivotkey.key)
{
++low;
}
L.elem[high].key=L.elem[low].key;
L.elem[high].key2=L.elem[low].key2;
}
L.elem[low].key=L.elem[0].key;
L.elem[low].key2=L.elem[0].key2;
return low;
}
void Qsort(Sqlist &L,long low,long high)
{
long pivotkey;
if(low<high)
{
pivotkey=Partition(L,low,high);
Qsort(L,low,pivotkey-1);
Qsort(L,pivotkey+1,high);
}
}
void Quicksort(Sqlist L)
{
Qsort(L,1,L.length);
}
//快速排序到此结束
//以下是堆排序
void HeapAdjust(Sqlist &H,int s,int m)
{
Red rc;
long int j;
rc.key=H.elem[s].key;
rc.key2=H.elem[s].key2;
for (j=2*s;j<=m;j*=2)
{
if(j<m&&H.elem[j].key<H.elem[j+1].key)
{++j;}
if(rc.key>=H.elem[j].key)
{break;}
H.elem[s].key=H.elem[j].key;
H.elem[s].key2=H.elem[j].key2;
s=j;
}
H.elem[s].key=rc.key;
H.elem[s].key2=rc.key2;
}
void Heapsort(Sqlist &H)
{
Red rc;
long int i;
for(i=H.length/2;i>0;--i)
{
HeapAdjust(H,i,H.length);
}
for(i=H.length;i>1;--i)
{
rc.key=H.elem[1].key;
rc.key2=H.elem[1].key2;
H.elem[1].key=H.elem[i].key;
H.elem[1].key2=H.elem[i].key2;
H.elem[i].key=rc.key;
H.elem[i].key2=rc.key2;
HeapAdjust(H,1,i-1);
}
}
//堆排序到此结束
void main()
{
int dlta[10]={60,52,41,30,24,15,9,7,5,1};
int t=10;
int ch1;
Sqlist array;
while(ch1!=4)
{
printf("*****************菜单***********************\n");
printf("请选择下列操作：\n");
printf("1------------------快速排序-----------------\n");
printf("2------------------希尔排序-----------------\n");
printf("3------------------堆排序-------------------\n");
printf("4------------------退出---------------------\n");
printf("请选择操作类别(1-4)：");
scanf("%d",&ch1);
if(ch1==1)
{
Input(array);
Quicksort(array);
output(array);
}
if(ch1==2)
{
Input(array);
ShellSort(array,dlta,t);
output(array);
}
if(ch1==3)
{
Input(array);
Heapsort(array);
output(array);
}
if(ch1==4)
{
break;
}
}
}
