实验八 排序技术的编程实现

实验八 排序技术的编程实现

【实验目的】

排序技术的编程实现 要求：

排序技术的编程实现（2学时，综合型），掌握排序技术的编程实现，可以实现一种，也可以实现多种。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

综合性实验，其综合性体现在本实验的内容具有的实际应用价值，多种数据结构的综合应用，各种具有代表性的算法设计和程序实现。（学时数：2H）

【实验内容】

1. 2. 3. 4.

使用冒泡排序法设计一个排序程序。 使用快速排序法设计一个排序程序。 使用堆排序法设计一个排序程序。

鼓励同时开发多种排序的程序，并且用菜单管理。

【注意事项】

1. 建议把数据先存在文件中，避免调试程序时反复输入，同时增加程序的通用性。 2. 建议把排序的中间过程显示出来体现排序的原理和过程。

【思考问题】

1. 排序算法通常使用什么数据结构和存储结构？为什么？ 2. 各种排序算法的效率分析和比较？ 3. 快速排序主要使用什么思路？ 4. 举出排序的应用范例？

【参考代码】（以下内容，学生任意选择一个完成即可）

（一） 提高篇

//利用冒泡排序，快速排序和堆排序完成一批数据的排序。 #include #define MAX 1000

void bubbleSort(int *list, int index)

{ //利用冒泡排序算法，完成对数组list中的index个数进行排序。

}

//快速排序程序构思： //1.读入欲排序的数值。 //2.使用快速排序法 // (1)设置左右端指针（i-左指针，j-右指针） // (2)设分割指针pivot

// (3)i往右找比pivot大时停止，j往左找比pivot小时停止 // (4)若i=j，list[left]和list[j]内容值对调 /

// (5)pivot找到其位置，并打输出对调后的排序结果 // (6)排序pivot左边的元素 QuickSort（左边） // (7)排序pivot右边的元素 QuickSort（右边） //3.打印最终排序结果

void QuickSort(int *list,int left,int right,int index)

{ //利用快速排序算法，完成对数组list中的index个数进行排序。 }

void produce_data(int data[],int num) //随机产生一批数 { int i;

srand((unsigned)time(NULL)); for(i=0;i

void produce1_data(int data[],int num) //随机产生一批数

{ //专门用于堆排序，数据从data[1]开始存放 int i;

srand((unsigned)time(NULL)); for(i=1;i<=num;i++) data[i]=rand()0; }

void print_data(int data[],int num) //输出数据 { int i; int count; for(i=0;i

void print1_data(int data[],int num) //输出数据

{ //专门用于堆排序，数据从data[1]开始输出 int i; int count; for(i=1;i<=num;i++) { printf(\ count++; if(count==0) printf(\ } }

void createHeap (int *heap, int root, int index) { int i,j;

int temp; //于数值交换时的暂存变量 int finish; //判断堆是否建立完成

j=2*root; //子结点的index temp=heap[root]; //暂存heap的root值 finish=0; //默认堆建立尚未完成

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

//找最大的子结点 if (j

if (heap[j]=heap[j])

finish=1; //堆建立完成 else {

heap[j/2]=heap[j]; //父结点=目前结点 j=2*j; } }

heap[j/2]=temp; //父结点=root值 }

//堆排序程序构思： //1.读取数值存入二叉树数组list中 //2.将二叉树转成最大堆 //3.堆的最大值和数组最后一个数值交换 //4.其余数值进行堆重建，并打印目前排序结果 //5.重复3、4，直到所有值均已排序完成 //6.打印最终排序结果 void HeapSort(int *heap,int index)

{ //堆排序 int i,j,temp;

for(i=(index/2);i>=1;i--) //将二叉树转成heap createHeap(heap,i,index);

for(i=index-1;i>=1;i--) //开始进行堆排序 {

temp=heap[i+1]; //heap的root值和最后一个值交换 heap[i+1]=heap[1]; heap[1]=temp;

createHeap(heap, 1, i); //对其余数值重建堆*/ printf(\目前的排序为:\ //打印堆处理过程*/ for(j=1;j<=index;j++)

printf(\ //printf(\ } }

void showmenu()

{ //显示菜单 printf(\ 欢迎使用数据排序小软件\\n\ printf(\、冒泡排序\\n\ printf(\、快速排序\\n\ printf(\、堆排序\\n\ printf(\、退出程序\\n\ }

void main() {

int list[MAX]; //默认数组最大长度为20 int i,num; //数组索引/

int node; //读入输入值所使用的暂存变量 int choice; while(1) { showmenu(); printf(\ 请输入你的选择：\ scanf(\ switch(choice) { case 1: printf(\请输入需要排序的元素个数：\ scanf(\ produce_data(list,num); printf(\排序前的数据为:\\n\ print_data(list,num); bubbleSort(list,num); printf(\最终的排序结果为:\\n\ print_data(list,num); printf(\ system(\ system(\ break; case 2:printf(\请输入需要排序的元素个数：\ scanf(\ produce_data(list,num); printf(\排序前的数据为:\\n\ print_data(list,num); printf(\排序过程如下：\\n\ QuickSort(list,0,num-1,num); printf(\最终的排序结果为:\\n\ print_data(list,num); printf(\ system(\ system(\

break; case 3:printf(\请输入需要排序的元素个数：\ scanf(\ produce1_data(list,num); printf(\排序前的数据为:\\n\ print1_data(list,num); printf(\排序过程如下：\\n\ HeapSort(list,num); printf(\最终的排序结果为:\\n\ print1_data(list,num); printf(\ system(\ system(\ break; case 4: return; default: printf(\你的选择有误，请从新输入！\\n\ } } }

（二） 挑战篇

设计一个小程序，实现所有排序算法的排序演示过程。 【实验小结】 (总结本次实验的重难点及心得、体会、收获)

得 分_____________

评阅日期_____________

教师签名__ __________

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