谁教我：数据结构的各种排序

Question

没好好听老师讲的

讲详细点，追加分
别复制C
我看不懂

Answer 1

1.快速排序

#include"stdio.h"
#define N 100
int a[N]={0};//存放要排序的数

int Qsort(int m,int n)//对数组中m到n的元素进行快速排序
{
int p,q;
int head,sign;
if(m!=n)//选定的数列不止一个元素
{
head=a[n];//选择数列的末尾元素作为比较元素
p=m;//p标记数列的首元素
q=n-1;//标记末尾元素的前一个元素
sign=n;//记录比较元素的位置，以其作为空位置
while(p<=q)//分别比较p、q所标记的元素与比较元素的大小，比其小的放在左边，比其大的放在右边
{
while(a[p]<head)//p所指元素比比较元素小，p右移
{
p++;
if(p>q)
{
break;
}
}
a[sign]=a[p];//将p所指元素移入空位置
sign=p;//记录空余位置
p++;
if(p>q)
{
break;
}
while(a[q]>head)//q所指元素比比较元素大，q左移
{
q--;
if(p>q)
{
break;
}
}
a[sign]=a[q];
sign=q;
q--;
}
a[sign]=head;//比较完成后，将比较元素移入空位置
if(sign-1>m)
{
Qsort(m,sign-1);//对m到sign-1的数列进行排序
}
if(sign+1<n)
{
Qsort(sign+1,n);//对sign+1到n的数列进行排序
}
}
return(1);
}

int Print(int m,int n)//对m到n的数组序列输出
{
int i;
for(i=m;i<=n;i++)
{
printf("%d\n",a[i]);
}
return(1);
}

int main()
{
int n,i;
scanf("%d",&n);//输入将要排序的数的个数
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);//输入要排序的数
}
Qsort(0,n-1);
Print(0,n-1);
}
二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；

三、调试分析与心得体会：
快速排序的思想时从数组序列中选定一个元素，将序列中其余元素与其进行比较，将比其小的放在左边，比其大的放在右边，然后以比较元素为中点，将序列分成两部分，再将它们分别进行快速排序，依次类推，直到序列中只有一个元素为止。

2.合并排序

#include"stdio.h"
#define N 10000
int a[N];//用a数组记录所给无序数列
int b[N]={0};//用b数组记录每次排序之后的a数组
int sign=0;
void Merge(int m,int mid,int n)//将两个有序数列合并成为一个有序数列
{
int i,j,k;
i=k=m;
j=mid+1;
while(i<=mid&&j<=n)//依次比较两个有序数列中的元素，从大到小将其放入b数组相应位置中
{
if(a[i]<a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
if(i<=mid)//将比较之后的剩余元素放入b数组相应位置
{
while(i<=mid)
{
b[k]=a[i];
k++;
i++;
}
}
else
{
while(j<=n)
{
b[k]=a[j];
k++;
j++;
}
}
for(i=m;i<=n;i++)//将合并后的数列重新放入a数组相应位置
{
a[i]=b[i];
}
}
int Msort(int m,int n)//对所给无序数列进行排序
{
int mid;
if(n!=m)
{
mid=(n+m)/2; //将数列一分为二直到其只有一个元素
Msort(m,mid);
Msort(mid+1,n);
Merge(m,mid,n);//将分割后的数列重新合并起来
}
return(1);
}
void Print(int num)//将序列依次输出
{
int i;
for(i=0;i<num;i++)
{
printf("%d\n",a[i]);
}
}
int main()
{
int sign;
int i;
int num;
scanf("%d",&num);//输入将要排序的数的个数
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);//依次输入要排序的数
}
sign=Msort(0,num-1);
Print(num);//输出完成排序后的有序数列
}
二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；
三、调试分析与心得体会：
合并排序是排序的一种常用方法，其主要思想为：将一个无序数列依次分割直到其每个序列只有一个元素为止，然后再将两个序列合并为一个有序数列，依此类推。

3.我的数据结构实验课题（关于排序）

//问题描述：排序器
//要 求：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，
//并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。
//1）、Shell排序； 2）、Quick排序
//3）、锦标赛排序； 4）、堆排序
//5）、归并排序； 6）、基数排序
//在实现排序算法1）~4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。

#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 10000000
#define N 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define LEN sizeof(SqList)
#define Maxr 10
#define MAXNUM 100000000

typedef struct node{
int key;
int num;
};
typedef struct {
struct node r[Maxsize+1];
long length;
}SqList,*qSqList;
typedef struct node2{
struct node r;
struct node2 *next;
}RecType;
long shifttimes;//统计移动次数
long comparetimes;//统计比较次数

qSqList creat(char filename[])//读入文件并且将数据保存
{
FILE *fp;
long i;
qSqList L;
L=(qSqList)malloc(LEN);
L->length=0;
if((fp=fopen(filename,"r"))==NULL)//文件不存在时终止程序
{
printf("cannot open file\n");
exit(0);
}
for(i=1;i<Maxsize+1;i++)
{
fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num));
if(L->r[i].key<0)
break;
L->length++;//记录读入的数据长度
}
fclose(fp);
return(L);
}

void Print2(qSqList L)//将序列输出到指定的文件中
{
long i;
FILE *fp;
char filename[N];
printf("\n\t请输入存储文件名：");
scanf("%s",filename);//输入将要储存的文件名
fp=fopen(filename,"w");
for(i=1;i<=L->length;i++)//将链表中数据逐一写入文件中
{
fprintf(fp,"%d (%d)\n",L->r[i].key,L->r[i].num);
}
fclose(fp);
}

void Print(qSqList L)//打印数据个数以及排序过程中的比较次数和移动次数
{
printf("\n\t数据个数:%ld",L->length);
printf("\n\t比较次数:%ld",comparetimes);
printf("\n\t移动次数:%ld",shifttimes);
}

struct node Min1(struct node a,struct node b)//比较两接点关键字的大小
{
struct node temp;
if(a.key>b.key)
temp=b;
else
temp=a;
comparetimes++;
return(temp);
}

qSqList shellinsert(qSqList L,int dk)//对顺序表以dk为增量作直接插入排序
{
int i,j;
for(i=dk+1;i<=L->length;i++)
{
if(LT(L->r[i].key,L->r[i-dk].key))//将L->r[i]插入到有序增量子表
{
L->r[0]=L->r[i];//将L->r[i]暂时存储在L->r[0]
shifttimes++;
for(j=i-dk;j>0&<(L->r[0].key,L->r[j].key);j-=dk)//记录后移，查找插入位置
{
L->r[j+dk]=L->r[j];
comparetimes++;
shifttimes++;
}
if(j>0)
comparetimes++;
L->r[j+dk]=L->r[0];//插入
shifttimes++;
}
comparetimes++;
}
// Print(L);
return(L);
}

qSqList shell(qSqList L)//希尔排序
{
int i,t=0;
int k;
for(t=0;LQ(pow(2,t),(L->length+1));t++);
t=t-1;
// printf("%d",t);
for(i=1;i<=t;++i)
{
k=(int)pow(2,t-i+1)-1;//计算排序增量
L=shellinsert(L,k);
}
Print(L);
Print2(L);
return(L);
}

long Quicksort(qSqList L,long low,long high)//交换顺序表L中子表L->r[low..high]的记录，使枢轴记录到位，并返回其所在位置
{
int pivotkey;
pivotkey=L->r[low].key;//用序列的第一个记录作枢轴记录
while(low<high)//从表的两端交替地向中间扫描
{
while(low<high&&L->r[high].key>=pivotkey)//将比枢轴记录小的记录交换到低端
{
comparetimes++;
high--;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
while(low<high&&L->r[low].key<=pivotkey)//将比枢轴记录大的记录交换到高端
{
comparetimes++;
low++;
}
comparetimes++;
L->r[0]=L->r[low];
shifttimes++;
L->r[low]=L->r[high];
shifttimes++;
L->r[high]=L->r[0];
shifttimes++;
}
return(low);//返回枢轴所在位置
}

qSqList Quick2(qSqList L,long low,long high)//对顺序表L中的子序列L.r[low..high]作快速排序
{
long pivot;
if(low<high)//序列长度大于1
{
pivot=Quicksort(L,low,high);//将序列一分为二
Quick2(L,low,pivot-1);//对低位子表递归排序
Quick2(L,pivot+1,high);//对高位子表递归排序
}
return(L);
}

qSqList Quick(qSqList L)//对顺序表作快速排序
{
long low,high;
low=1;//将第一个数据所在位置定义为低位
high=L->length;//将最后一个数据所在位置定义为高位
L=Quick2(L,low,high);//对顺序表作快速排序
Print(L);
Print2(L);
return(L);
}

void TourSort(SqList *L,long n)//锦标赛排序
{
qSqList Lp;
long i=0,t=1,k=1,w;
while(t<n)//t表示完全二叉树的结点个数
{
t=(long)pow(2,i);
i++;
}
t=2*t;
Lp=(qSqList)malloc((sizeof(SqList)));
Lp->length=t-1;
for(i=t-1;i>=t/2;i--)
{
if(k>n)
Lp->r[i].key=MAXNUM;
else
{
Lp->r[i]=L->r[k];

}
shifttimes++;
k++;
}
i=t-1;
while(i!=1)
{
Lp->r[i/2]=Min1(Lp->r[i],Lp->r[i-1]);
i-=2;
comparetimes++;
shifttimes++;
}
for(i=1;i<=n;i++)
{
L->r[i]=Lp->r[1];
shifttimes++;
w=1;
while(w<t/2)
{
if(Lp->r[2*w].key==Lp->r[w].key)
w*=2;
else
w=2*w+1;
}
Lp->r[w].key=MAXNUM;//将其赋为最大值
shifttimes++;
if(w%2)
Lp->r[w/2]=Lp->r[w-1];
else
Lp->r[w/2]=Lp->r[w+1];
shifttimes++;
while(w!=1)
{
if(w%2)
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w-1]);
else
Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w+1]);
comparetimes++;
shifttimes++;
w/=2;
}
}
Print(L);
Print2(L);
}

void Heapadjust(qSqList L,long s,long m)//调整L->[s]的关键字，使L->r[s..m]成为一个大顶堆
{
long j;
struct node rc;
rc=L->r[s];
for(j=2*s;j<=m;j*=2)//沿key较大的接点向下筛选
{
if(j<m&<(L->r[j].key,L->r[j+1].key))//j为key较大的记录的下标
{
j++;
comparetimes++;
}
if(!LT(rc.key,L->r[j].key))
{
comparetimes++;
break;
}
L->r[s]=L->r[j];//rc插入位置s
shifttimes++;
s=j;
}
L->r[s]=rc;//插入
shifttimes++;
}

qSqList Heap(qSqList L)//堆排序
{
long i;
for(i=L->length/2;i>0;--i)//把L建成大顶堆
Heapadjust(L,i,L->length);
for(i=L->length;i>1;--i)//将堆顶记录和当前未经排序子序列中最后一个记录交换
{
L->r[0]=L->r[1];
L->r[1]=L->r[i];
L->r[i]=L->r[0];
shifttimes=shifttimes+3;
Heapadjust(L,1,i-1);//将L重新调整为大顶堆
}
Print(L);
Print2(L);
return(L);
}

void Merge(qSqList L,int low,int m,int high)//将两个有序表R[low..m]he R[m+1..high]归并为一个有序表R[low,high]
{
int i=low,j=m+1,k=0;//k是temp的下标，i,j分别为第1，2段的下标
struct node *temp;
temp=(struct node*)malloc((high-low+1)*sizeof(struct node));//用于临时保存有序序列
while(i<=m&&j<=high)//在第1段和第2段均未扫描完时循环
{
if(LT(L->r[j].key,L->r[i].key))//将第1段中的记录放入temp中
{
temp[k]=L->r[j];
j++;
k++;
}
else//将第2段中的记录放入temp中
{
temp[k]=L->r[i];
k++;
i++;
}
}
while(i<=m)//将第1段余下的部分复制到temp
{
temp[k]=L->r[i];
k++;
i++;
}
while(j<=high)//将第2段余下的部分复制到temp
{
temp[k]=L->r[j];
k++;
j++;
}
for(k=0,i=low;i<=high;i++,k++)//将temp复制回L中
{
L->r[i]=temp[k];
}
}

void MSort(qSqList L,int low,int high)//二路归并排序
{
int m;
if (low<high)
{
m=(low+high)/2;
MSort(L,low,m);
MSort(L,m+1,high);
Merge(L,low,m,high);
}
}

void Merging(qSqList L)//归并排序
{
MSort(L,1,L->length);
Print2(L);
}

void Radixsort(qSqList L)//基数排序
{
int g,i,j,k,d=2;
struct node2 *p,*s,*t,*head[10],*tail[10];//定义各链队的首尾指针
for(i=1;i<=L->length;i++) //建立链表
{
s = (struct node2*)malloc(sizeof(struct node2));
s->r.key = L->r[i].key;
s->r.num= L->r[i].num;
if(i==1)
{
t = s;
p = s;
g++;}
else
{
t->next = s;
t = s;
g++;
}
t->next = NULL;
}
d=1;
for(i=1;i<6;i++)
{
for(j=0;j<10;j++)
{head[j] = tail[j] = NULL;} //初始化各链队首、尾指针
while(p!=NULL)//对于原链表中的每个结点循环
{
k = p->r.key/d;
k = k%10;
if(head[k]==NULL)//进行分配
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p = p->next;//取下一个待排序的元素
}
p=NULL;
for(j=0;j<10;j++)//对每一个链队循环
{
if(head[j]!=NULL)//进行搜集
{
if(p == NULL)
{
p = head[j];
t = tail[j];
}
else
{
t->next=head[j];
t = tail[j];
}
}
}
t->next=NULL;//最后一个结点的next置为空
d=d*10;
}
i=1;
while(p!=NULL)
{
L->r[i] = p->r;
i++;
p=p->next;}
Print2(L);
}

char chmenu()//对排序方法进行选择
{
char ch;
printf("\n\t请选择排序方法:"
"\n\t*************"
"\n\t1.Shell排序"
"\n\t2.Quick排序"
"\n\t3.锦标赛排序"
"\n\t4.堆排序"
"\n\t5.归并排序"
"\n\t6.基排序"
"\n\t7.结束"
"\n\t*************");
do{
printf("\n\tplease choose (1-7):");
getchar();
ch=getchar();
}while(!(ch>'0'&&ch<'8'));
return(ch);
}

void main()
{
int a=1;
FILE *fp;
char ch,filename[N];
qSqList L;
while(a)
{
printf("\n\t请输入读入文件名:");//输入要读入的文件名
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("cannot open the file\n");
exit(0);
}
L=creat(filename);
while(1)
{
if((ch=chmenu())=='7')
break;
switch(ch)
{
case'1':{shifttimes=comparetimes=0;shell(L);}break;
case'2':{shifttimes=comparetimes=0;Quick(L);}break;
case'3':{shifttimes=comparetimes=0;TourSort(L,L->length);}break;
case'4':{shifttimes=comparetimes=0;Heap(L);}break;
case'5':{shifttimes=comparetimes=0;Merging(L);}break;
case'6':{shifttimes=comparetimes=0;Radixsort(L);}break;
}
}
printf("\n\t***************"
"\n\t1.继续读入文件"
"\n\t0.结束"
"\n\t***************");
do{
printf("\n\tplease choose (0-1):");
getchar();
scanf("%d",&a);
}while(!(a==1||a==0));

}
}

Answer 2

数据结构算法-排序的各种方法
void shellsort(sqlist l,int d)
{
int i,j;
d=l.length/2;
while(d>0)
{
for(i=d 1;i<=l.length; i)
if(l.r[i].key<l.r[i-d].key)
{
l.r[0]=l.r[i];
for(j=i-d;j>0&&l.r[0].key<l.r[j].key;j-=d)
l.r[j d]=l.r[j];
l.r[j d]=l.r[0];}
d=d/2;}
}
;
;
;
void quicksort(sqlist l,int low,int high)
{int i,j;
if(low<high)
{i=low;j=high;l.r[0]=l.r[i];
do
{
while(i<j&&l.r[j].key>l.r[0].key)
--j;
if(i<j)
{l.r[i]=l.r[j]; i;}
while(i<j&&l.r[i].key<=l.r[0].key)
i;
if(i<j){
l.r[j]=l.r[i];--j;
}
}while(i!=j);
l.r[i]=l.r[0];
quicksort(l,low,i-1);
quicksort(l,i 1,high);
}
}
;
;
;
void heapadjust(sqlist l,int s,int m)
{
int rc,j;
rc=l.r[s].key;
for(j=2*s;j<=m;j*=2)
{
if(j<m&&l.r[j].key<l.r[j 1].key)
j ;
if(rc>l.r[j].key)
break;
l.r[s].key=l.r[j].key;
s=j;
}
l.r[s].key=rc;
}
;
;
;
void heapsort(sqlist l)
{
int i,t;
for(i=l.length/2;i>0;i--)
heapadjust(l,i,l.length);
for(i=l.length;i>1;i--)
{
t=l.r[1].key,l.r[1].key=l.r[i].key,l.r[i].key=t;
heapadjust(l,1,i-1);
}
}
;
;
;
void oesort(sqlist l,int n)
{
int t,i,change;
change=1;
while(change)
{
change=0;
for(i=1;i<n;i =2)
if(l.r[i].key>l.r[i 1].key)
{
t=l.r[i].key,l.r[i].key=l.r[i 1].key,l.r[i 1].key=t;
change=1;
}
for(i=2;i<n;i =2)
if(l.r[i].key>l.r[i 1].key)
{
t=l.r[i].key,l.r[i].key=l.r[i 1].key,l.r[i 1].key=t;
change=1;
}
}
}
;
;
;
main()
{
int i,j,low,high,a[maxsize 1];
char ch;
sqlist l;
clrscr();
l.r=(redtype *)malloc(maxsize*sizeof(int));
if(!l.r)
printf("overflow");
l.length=0;
printf("\n\nplease input five elements:\n\n");
for(i=1;i<maxsize 1;i )
{
scanf("%d",&a[i]);
l.length ;
}
getchar();
do
{
for(j=1,i=1;j<maxsize 1;i ,j )
l.r[i].key=a[j];
printf("\n\nWelcome to use PanWeiFeng's KeChenSheJi\n\n");
printf("s:shellsort\tq:quicksort\n\n");
printf("h:heapsort\te:oesort\n\n");
printf("o:quit\n\n");
printf("please input the way:");
ch=getchar();
clrscr();
printf("\n\nthe orignal array:");
for(i=1;i<maxsize 1;i )
printf("%d ",l.r[i].key);
printf("\n\n");
/*printf("please input the way:");
ch=getchar();*/
getchar();
switch(ch)
{
case 's':
shellsort(l,l.length);
printf("\n\nthe odered arry:");
for(i=1;i<maxsize 1;i )
printf("%d ",l.r[i].key);
printf("\n\n");
break;
case 'q':
low=1;high=l.length;
quicksort(l,low,high);
printf("\n\nthe odered arry:");
for(i=1;i<maxsize 1;i )
printf("%d ",l.r[i].key);
printf("\n\n");
break;
case 'h':
heapsort(l);
printf("\n\nthe odered arry:");
for(i=1;i<maxsize 1;i )
printf("%d ",l.r[i].key);
printf("\n\n");
break;
case 'e':
oesort(l,l.length);
printf("\n\nthe odered arry:");
for(i=1;i<maxsize 1;i )
printf("%d ",l.r[i].key);
printf("\n\n");
break;
case 'o':
exit(0);
default:
printf("\n\nerror!write again!\n");
}
}while(1);
}

数据结构里的各种排序方法及其效率分析
在visual c++6.0里面编译 你自己看
#include "stdafx.h"
#define MAXSIZE 50
#include <stdio.h>
typedef struct
{
int key;
}RECNODE;

int b,t;
int MakeList(RECNODE *r)
{
int j,k;
printf("\n请输入初始数据(每个数据以空格隔开，-1结束）： ");
k=0;
scanf("%d",&j);
while(j!=-1)
{
k++;
r[k].key=j;
scanf("%d",&j);
}
return k;
}

void UndealoutList(RECNODE *r,int n)
{
int i;
printf("\n未排序前的数据 ： ");
for(i=0;i<n;i++)
printf(" %d",r[i+1].key);
printf("\n\n");
}

void DealoutList(RECNODE*r,int n)
{
int i;

printf("排序后的数据 ： ");
for(i=0;i<n;i++)
printf(" %d",r[i+1].key);
printf("\n\n");
printf("交换或比较的次数： %d\n",b);
printf("排序的趟数： %d\n",t);
}

void InsertSort(RECNODE*r,int n)//直接插入排序//
{
int i,j;
b=0,t=0;

for(i=2;i<=n;i++)
{
r[0]=r[i];
j=i-1;
while(r[0].key<r[j].key)
{
r[j+1]=r[j];
j--;
b++;
}
r[j+1]=r[0];
b++;
t++;
}

}

void BubleSort(RECNODE *r,int n) //冒泡排序//
{
int i,j;
b=0,t=0;
RECNODE temp;
for(i=1;i<n;i++)
{
for(j=n-1;j>=i;j--)
if(r[j+1].key<r[j].key)
{
temp=r[j+1];
r[j+1]=r[j];
r[j]=temp;
b++;
}
else b++;
t++;
}

}

int Partition(RECNODE*r,int*low,int*high)//一躺快速排序//
{
int i,j;
static int w=0;
RECNODE temp;
i=*low;
j=*high;
temp=r[i];
do
{
while((r[j].key>=temp.key)&&(i<j))
{
j--;
w++;
}
if(i<j)
{
r[i]=r[j];
i++;
w++;
}
while((r[i].key<=temp.key)&&(i<j))
{
i++;
w++;
}
if(i<j)
{
r[j]=r[i];
j--;
w++;
}
}while(i!=j);
r[i]=temp;
b=w;
return i;
}

void QuickSort(RECNODE*r,int start,int end)//快速排序//
{
int i;
static int q=0;
if(start<end)
{
i= Partition(r,&start,&end);
q++;
QuickSort(r,start,i-1);
QuickSort(r,i+1,end);
}
t=q;
}

void SeleSort(RECNODE*r,int n)//直接选择排序//
{
int i,j,z;
b=0,t=0;
RECNODE temp;
for(i=1;i<n;i++)
{
z=i;
for(j=i+1;j<=n;j++)
if(r[j].key<r[z].key)
{
z=j;
b++;
}
else b++;
if(z!=i)
{
temp=r[i];
r[i]=r[z];
r[z]=temp;
}
t++;
}

}

void ShellSort(RECNODE *r,int n)//希尔排序//
{
int i,j,dk;
b=0,t=0;
dk=n/2;
while(dk>0)
{
for(i=dk+1;i<n;++i)
if(r[i].key<r[i-dk].key)
{
r[0]=r[i];
for(j=i-dk;j>0&&r[0].key<r[j].key;j-=dk)
{
r[j+dk]=r[j];
b++;
}
r[j+dk]=r[0];
}
dk=dk/2;
t++;
}

}

void Sift(RECNODE*r,int i,int m)
{
int j;
static int x=0;
RECNODE temp;
temp=r[i];
j=2*i;
while(j<=m)
{
if(j<m&&(r[j].key<r[j+1].key))
{
j++;
x++;
}
if(temp.key<r[j].key)
{
r[i]=r[j];
i=j;
j=2*i;
x++;
}
else x++; break;
}
r[i]=temp;
b=x;
}

void HeapSort(RECNODE*r,int n)//堆排序//
{
RECNODE temp;
int i;
t=0;
for(i=n/2;i>=1;i--)
Sift(r,i,n);
for(i=n;i>=2;i--)
{
temp=r[1];
r[1]=r[i];
r[i]=temp;
Sift(r,1,i-1);
t++;
}

}

void main()
{
RECNODE a[MAXSIZE];
int len,p;
do
{
printf("**********************\n");
printf("* 菜 单 *\n");
printf("**********************\n");
printf("* 1---直接插入排序 *\n");
printf("* 2---冒泡排序 *\n");
printf("* 3---快速排序 *\n");
printf("* 4---直接选择排序 *\n");
printf("* 5---堆排序 *\n");
printf("* 6---希尔排序 *\n");
printf("* 0---退出 *\n");
printf("**********************\n");
printf("\n请在上述序号中选择一个并输入： ");
scanf("%d",&p);
switch(p)
{
case 1:len=MakeList(a);
UndealoutList(a,len);
InsertSort(a,len);
DealoutList(a,len);
break;
case 2:len=MakeList(a);
UndealoutList(a,len);
BubleSort(a,len);
DealoutList(a,len);
break;
case 3:len=MakeList(a);
UndealoutList(a,len);
QuickSort(a,1,len);
DealoutList(a,len);
break;
case 4:len=MakeList(a);
UndealoutList(a,len);
SeleSort(a,len);
DealoutList(a,len);
break;
case 5:len=MakeList(a);
UndealoutList(a,len);
HeapSort(a,len);
DealoutList(a,len);
break;
case 6:len=MakeList(a);
UndealoutList(a,len);
ShellSort(a,len);
DealoutList(a,len);
break;
case 0:break;
default:printf("输入错误！请重新输入!\n");break;
}
}while(p!=0);

}

Answer 3

数据结构中的排序算法,各有用处,比如:
1,直接插入排序,在序列基本有序的情况下,移动的次数比较少,但是比较次数是一样的
复杂度O(n*n);
2,冒泡排序,这个不用说了吧,刚学C的人都懂了
3,希尔排序,只要是找出较好的增量,将数据排列成基本有序时,最后一次来一次直接插入排序,是对直接插入排序的改进.复杂度为O(n(3/2));
4,快速排序,算是所有排序中复杂度一般情况下比较好的算法,它设了一个枢轴,将它分为两部分,左边比它小,右边的比它大,复杂度为O(nlog n);
5,选择排序,和冒泡差不多的复杂度,
6,归并排序,这是一种稳定的排序方法,将数据分为各个有序的部分,再组合为一个整体,只要用递归的方法.
7,还有基数排序,树形排序,堆排序,等等,这里不多说了,你多多学习多多消化吧,慢慢学吧,多看看课本的算法,自己实现一次,学完了你的编程能力就能很好的提高了.

Answer 4

看《数据结构》，你一定会搞懂的本回答被提问者采纳

Answer 5

这个要讲得当面讲才有点效果。在网上想学好比较难。我希望你回去认真看点书。比在这儿浪费积分强得多。