实验七 排序及其应用

实验七 排序及其应用

一．实验目的

（1）掌握常用排序方法的基本思想； （2）通过实验加深理解各种排序算法；

（3）通过实验掌握各种排序方法的时间复杂度分析； （4）了解各种排序方法的优缺点及适用范围。 二．实验内容

（1）编写直接插入排序程序； （2）编写希尔排序程序； （3）编写冒泡排序程序； （4）编写快速排序程序； （5）编写选择排序程序； （6）编写归并排序程序； （7）编写堆排序程序；

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

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

排 序 子 系 统

*************************************************** * 1------------更新排序数据 * * 2------------直接插入排序 * * 3------------希 尔 排 序 * * 4------------冒 泡 排 序 * * 5------------快 速 排 序 * * 6------------选 择 排 序 * * 7------------归 并 排 序 * * 8------------堆 排 序 * * 0------------返 回 * *************************************************** 请选择菜单项：

三.基本原理

请叙述希尔排序、快速排序、选择排序和堆排序的基本思想。 四、程序模板

#include #include #include #define L 8

#define FALSE 0 #define TRUE 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(); void Partition(); void Heap();

void main() {

Seqlist S; int i,k;

char ch1,ch2,q;

printf(\请输入%d个待排序数据：（按回车隔开）\\n\\t\ for(i=1;i<=L;i++) {

scanf(\ }

printf(\排序数据已经输入完毕！\ ch1='y';

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

printf(\排 序 子 系 统\\n\

printf(\ printf(\更新排序数据----------*\\n\ printf(\直接插入排序 ---------*\\n\ printf(\希 尔 排 序 ---------*\\n\ printf(\冒 泡 排 序 ---------*\\n\ printf(\快 速 排 序----------*\\n\ printf(\选 择 排 序 ---------*\\n\ printf(\归 并 排 序 ---------*\\n\ printf(\堆 排 序----------*\\n\ printf(\返 回----------*\\n\ printf(\ printf(\请选择菜单号（0---8）:\ scanf(\ for(i=1;i<=L;i++)

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

switch(ch2) {

case '1':

printf(\请输入%d个待排序数据：（按回车隔开）\\n\\t\

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

scanf(\ }

printf(\排序数据已经输入完毕！\ break;

case '2':Insertsort();break; case '3':Shellsort();break; case '4':Bubblesort();break; case '5':

printf(\尚未排序的数据为（回车继续）：\ for(k=1;k<=L;k++)

printf(\ getchar();printf(\ num=0;QuickSort(1,L); break;

case '6':Selectsort();break; case '7':Mergesort();break; case '8':Heap();break; case '0':ch1='n';break;

default:printf(\输入错误！请重新输入！\\n\\t\\t\ }

if(ch2!='0') {

if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')

printf(\排序演示输出完毕！\\n\

printf(\请按回车键返回主菜单...\ q=getchar(); if (q!='\\xA') {

getchar();ch1='n'; } } } }

void Insertsort()//直接插入排序

{

int i,j,k,m=0;

printf(\尚未排序的数据为（回车继续）：\ for(k=1;k<=L;k++)

printf(\ getchar(); printf(\ for(i=2;i<=L;i++) {

if(R[i].key

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

while(R[0].key

//请完成该循环语句的循环体 }

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

printf(\第%d趟排序结果为（回车继续）：\ for(k=1;k<=L;k++)

printf(\ getchar();printf(\ }

printf(\

printf(\最终排序结果为：\ for(i=1;i<=L;i++)

printf(\ printf(\}

void Bubblesort()//冒泡排序 {

int i,j,k; int exchange;

printf(\尚未排序的数据为（回车继续）：\ for(k=1;k<=L;k++)

printf(\ getchar(); printf(\ for(i=1;i<=L;i++) {

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

if(R[j].key

{

R[0].key=R[j].key; R[j].key=R[j-1].key; R[j-1].key=R[0].key; exchange=TRUE; }

if(exchange) {

printf(\第%d趟排序结果为（回车继续）：\ for(k=1;k<=L;k++)

printf(\ getchar();printf(\ }

printf(\

printf(\最终排序结果为：\ for(i=1;i<=L;i++)

printf(\ printf(\ } }

int Partition(int i,int j) //快速排序 {

RecType pirot=R[i]; while(i

while(i=pirot.key) j--; if(i

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

while(i

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

R[i]=pirot; return i; }

void QuickSort(int low,int high) {

int pirotpos,k,i; if (low

本文来源：https://www.bwwdw.com/article/rsgf.html