数据结构实验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");

}