数据结构实验9：排序子系统

实验9：排序子系统

1．实验目的

（1）掌握常用排序方法的基本思想。

（2）通过实验加深理解各种排序算法。

（3）通过实验掌握各种排序方法的时间复杂度分析。

（4）了解各种排序方法的优缺点及适用范围。

2．实验内容

（1）编写直接插入排序程序。

（2）编写希尔排序程序。

（3）编写冒泡排序程序。

（4）编写快速排序程序。

（5）编写选择排序程序。

（6）编写归并排序程序。

（7）编写堆排序程序。

（8）程序执行时，要求能显示每一趟的排序结果。

（9）设计一个选择式菜单，以菜单方式选择上述排序程序。

排 序 子 系 统

***************************************************

* 1------------更新排序数据 *

* 2------------直接插入排序 *

* 3------------希 尔 排 序 *

* 4------------冒 泡 排 序 *

* 5------------快 速 排 序 *

* 6------------选 择 排 序 *

* 7------------归 并 排 序 *

* 8------------堆 排 序 *

* 0------------返 回 *

***************************************************

请选择菜单号（0--8）：

3．实验程序

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#define L 8

#define FALSE 0

#define TURE 1

typedef struct

{

int key;

char otherinfo;

}RecType;

typedef RecType Seqlist[L+1];

int num;

Seqlist R;

void Insertsort();

void Bubblesort();

void QuickSort(int low,int high);

void Shellsort();

void Selectsort();

void Mergesort();

int Partition(int i,int j);

void Heap();

void main()

{

Seqlist S;

int i,k;

char ch1,ch2,q;

printf("\n\t请输入%d个待排序数据（按【Enter】键分隔）：\n\t",L); for(i=1;i<=L;i++)

{

scanf("%d",&S[i].key);

getchar();

printf("\t");

}

printf("\n\t排序数据已经输入完毕！");

ch1='y';

while(ch1=='y'||ch1=='Y')

{

printf("\n");

printf("\n\t\t 排 序 子 系 统 ");

printf("\n\t\t***************************************************");

printf("\n\t\t* 1------------更新排序数据 *");

printf("\n\t\t* 2------------直接插入排序 *");

printf("\n\t\t* 3------------希 尔 排 序 *");

printf("\n\t\t* 4------------冒 泡 排 序 *");

printf("\n\t\t* 5------------快 速 排 序 *");

printf("\n\t\t* 6------------选 择 排 序 *");

printf("\n\t\t* 7------------归 并 排 序 *");

printf("\n\t\t* 8------------堆 排 序 *");

printf("\n\t\t* 0------------返 回 *");

printf("\n\t\t***************************************************");

printf("\n\t\t请选择菜单号（0--8）：");

scanf("%c",&ch2);

getchar();

for(i=1;i<=L;i++)

R[i].key=S[i].key;

switch(ch2)

{

case '1':

printf("\n\t请输入%d个待排序数据（按【Enter】键分隔）：\n\t",L); for(i=1;i<=L;i++)

{

scanf("%d",&S[i].key);

getchar();

printf("\t");

}

printf("\n\t排序数据已经输入完毕！");

break;

case '2':Insertsort();break;

case '3':Shellsort();break;

case '4':Bubblesort();break;

case '5':printf("\n\t原始数据为（按【Enter】键开始排序）："); for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

num=0;

QuickSort(1,L);

printf("\n\t排序的最终结果是：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

printf("\n");break;

case '6':Selectsort();break;

case '7':Mergesort();break;

case '8':Heap();break;

case '0':ch1='n';break;

default:printf("\n\t输入出错！"); } if(ch2!='0') { if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')

printf("\n\t排序输出完毕！");

printf("\n\n\t按回车键返回。");

q=getchar();

if(q!='\xA')

{

getchar();

ch1='n';

}

}

}

}

void Insertsort()

{

int i,j,k,m=0;

printf("\n\t原始数据为（按【Enter】键开始排序）：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

for(i=2;i<=L;i++)

{

if(R[i].key<R[i-1].key)

{

R[0]=R[i];j=i-1;

while(R[0].key<R[j].key)

{

R[j+1]=R[j];

j--;

}

R[j+1]=R[0];

}

m++;

printf("\t第%d趟排序结果为（按【Enter】键继续）：",m);

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

}

printf("\n\t排序的最终结果是：");

for(i=1;i<=L;i++)

printf("%5d",R[i].key);

printf("\n");

}

void Shellsort()

{

int i,j,gap,x,m=0,k;

printf("\n\t原始数据为（按【Enter】键开始排序）：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

gap=L/2;

while(gap>0)

{

for(i=gap+1;i<=L;i++)

{

j=i-gap;

while(j>0)

{

if(R[j].key>R[j+gap].key)

{

x=R[j].key;R[j].key=R[j+gap].key;

R[j+gap].key=x;

j=j-gap;

}

else

j=0;

}

}

gap=gap/2;

m++;

printf("\t第%d趟排序结果为（按【Enter】键继续）：",m);

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

}

printf("\n\t排序的最终结果是：");

for(i=1;i<=L;i++)

printf("%5d",R[i].key);

printf("\n");

}

void Bubblesort()

{

int i,j,k;

int exchange;

printf("\n\t原始数据为（按【Enter】键开始排序）：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

for(i=1;i<=L;i++)

{

exchange=FALSE;

for(j=L;j>=i+1;j--)

if(R[j].key<R[j-1].key)

{

R[0].key=R[j].key;

R[j].key=R[j-1].key;

R[j-1].key=R[0].key;

exchange=TURE;

}

if(exchange)

{

printf("\t第%d趟排序结果为（按【Enter】键继续）：",i);

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

}

}

printf("\n\t排序的最终结果是：");

for(i=1;i<=L;i++)

printf("%5d",R[i].key);

printf("\n");

}

int Partition(int i,int j)

{

RecType pirot=R[i];

while(i<j)

{

while(i<j&&R[j].key>=pirot.key)

j--;

if(i<j)

R[i++]=R[j];

while(i<j&&R[j].key<=pirot.key)

i++;

if(i<j)

R[j--]=R[i];

}

R[i]=pirot;

return i;

}

void QuickSort(int low,int high)

{

int pirotpos,k;

if(low<high)

{

pirotpos=Partition(low,high);

num++;

printf("\t第%d趟排序结果为（按【Enter】键继续）：",num);

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

QuickSort(low,pirotpos-1);

QuickSort(pirotpos+1,high);

}

}

void Selectsort()

{

int i,j,k,h;

printf("\n\t原始数据为（按【Enter】键开始排序）：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

for(i=1;i<=L;i++)

{

h=i;

for(j=i+1;j<=L;j++)

if(R[j].key<R[h].key)

h=j;

if(h!=j)

{

R[0]=R[i];

R[i]=R[h];

R[h]=R[0];

}

printf("\t第%d趟排序结果为（按【Enter】键继续）：",i);

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

}

printf("\n\t排序的最终结果是：");

for(i=1;i<=L;i++)

printf("%5d",R[i].key);

printf("\n");

}

void Merge(int low,int mm,int high)

{

int i=low,j=mm+1,p=0;

RecType *R1;

R1=(RecType *)malloc((high-low+1)*sizeof(RecType));

if(!R1)

printf("\n\t内存容量不够！");

while(i<=mm&&j<=high)

R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];

while(i<=mm)

R1[p++]=R[i++];

while(i<=high)

R1[p++]=R[j++];

for(p=0,i=low;i<=high;p++,i++)

R[i]=R1[p];

}

void MergePass(int length)

{

int i;

for(i=1;i+2*length-1<=L;i=i+2*length)

Merge(i,i+length-1,i+2*length-1);

if(i+length-1<L)

Merge(i,i+length-1,L);

}

void Mergesort()

{

int length,k,m=0;

printf("\n\t原始数据为（按【Enter】键开始排序）：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

for(length=1;length<L;length*=2)

{

MergePass(length);

m++;

printf("\t第%d趟排序结果为（按【Enter】键继续）：",m);

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

getchar();

printf("\n");

}

printf("\n\t排序的最终结果是：");

for(k=1;k<=L;k++)

printf("%5d",R[k].key);

printf("\n");

}

void CreateHeap(int root,int index)

{

int j,temp,finish;

j=2*root;

temp=R[root].key;

finish=0;

while(j<=index&&finish==0)

{

if(j<index)

if(R[j].key<R[j+1].key)

j++;

if(temp>=R[j].key)

finish=1;

else

{

R[j/2].key=R[j].key;

j=j*2;

}

}

R[j/2].key=temp;

}

void HeapSort()

{

int i,j,temp,k;

for(i=(L/2);i>=1;i--)

CreateHeap(i,L);

for(i=L-1,k=1;i>=1;i--,k++)

{

temp=R[i+1].key;

R[i+1].key=R[1].key;

R[1].key=temp;

CreateHeap(1,i);

printf("\t第%d趟排序结果为（按【Enter】键继续）：",k);

for(j=1;j<=L;j++)

printf("%5d",R[j].key);

getchar();

printf("\n");

}

}

void Heap()

{

int i;

printf("\n\t原始数据为（按【Enter】键开始排序）：");

for(i=1;i<=L;i++)

printf("%5d",R[i].key);

printf("\n\t");

getchar();

HeapSort();

printf("\n\t排序的最终结果是：");

for(i=1;i<=L;i++)

printf("%5d",R[i].key);

printf("\n");

}