【学生版】实验八 排序技术的编程实现.doc

实验八 排序技术的编程实现【实验目的】排序技术的编程实现要求：排序技术的编程实现（2学时，综合型），掌握排序技术的编程实现，可以实现一种，也可以实现多种。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】综合性实验，其综合性体现在本实验的内容具有的实际应用价值，多种数据结构的综合应用，各种具有代表性的算法设计和程序实现。（学时数：2H）【实验内容】1. 使用冒泡排序法设计一个排序程序。2. 使用快速排序法设计一个排序程序。3. 使用堆排序法设计一个排序程序。4. 鼓励同时开发多种排序的程序，并且用菜单管理。【注意事项】1. 建议把数据先存在文件中，避免调试程序时反复输入，同时增加程序的通用性。2. 建议把排序的中间过程显示出来体现排序的原理和过程。【思考问题】1. 排序算法通常使用什么数据结构和存储结构？为什么？2. 各种排序算法的效率分析和比较？3. 快速排序主要使用什么思路？4. 举出排序的应用范例？【参考代码】（以下内容，学生任意选择一个完成即可）（一） 提高篇/利用冒泡排序，快速排序和堆排序完成一批数据的排序。 #include#define MAX 1000void bubbleSort(int *list, int index) /利用冒泡排序算法，完成对数组list中的index个数进行排序。/快速排序程序构思： /1.读入欲排序的数值。 /2.使用快速排序法 / (1)设置左右端指针（i-左指针，j-右指针） / (2)设分割指针pivot / (3)i往右找比pivot大时停止，j往左找比pivot小时停止/ (4)若i=j，listleft和listj内容值对调 / (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;inum;i+) datai=rand()%100; void produce1_data(int data,int num) /随机产生一批数 /专门用于堆排序，数据从data1开始存放 int i; srand(unsigned)time(NULL); for(i=1;i=num;i+) datai=rand()%100; void print_data(int data,int num) /输出数据int i;int count;for(i=0;inum;i+)printf(%5d,datai); count+;if(count%10=0)printf(n);void print1_data(int data,int num) /输出数据 /专门用于堆排序，数据从data1开始输出int i;int count;for(i=1;i=num;i+)printf(%5d,datai); count+;if(count%10=0)printf(n);void createHeap (int *heap, int root, int index) int i,j; int temp; /于数值交换时的暂存变量 int finish; /判断堆是否建立完成 j=2*root; /子结点的index temp=heaproot; /暂存heap的root值 finish=0; /默认堆建立尚未完成 while (j=index & finish=0) /找最大的子结点 if (jindex) if (heapj=heapj) finish=1; /堆建立完成 else heapj/2=heapj; /父结点=目前结点 j=2*j; heapj/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=heapi+1; /heap的root值和最后一个值交换 heapi+1=heap1;heap1=temp; createHeap(heap, 1, i); /对其余数值重建堆*/ printf(n目前的排序为:); /打印堆处理过程*/ for(j=1;j=index;j+) printf(%3d,heapj); /printf(n); void showmenu() /显示菜单printf( 欢迎使用数据排序小软件n);printf(t1、冒泡排序n);printf(t2、快速排序n);printf(t3、堆排序n);printf(t4、退出程序n);void main() int listMAX; /默认数组最大长度为20 int i,num; /数组索引/ int node; /读入输入值所使用的暂存变量 int choice;while(1)showmenu();printf( 请输入你的选择：);scanf(%d,&choice);switch(choice) case 1:printf(请输入需要排序的元素个数：);scanf(%d,&num);produce_data(list,num); printf(排序前的数据为:n);print_data(list,num);bubbleSort(list,num);printf(n最终的排序结果为:n);print_data(list,num);printf(n);system(pause); system(cls);break;case 2:printf(请输入需要排序的元素个数：); scanf(%d,&num); produce_data(list,num); printf(排序前的数据为:n); print_data(list,num); printf(n排序过程如下：n); QuickSort(list,0,num-1,num); printf(n最终的排序结果为:n); print_data(list,num); printf(n); system(pause); system(cls); break;case 3:printf(请输入需要排序的元素个数：); scanf(%d,&num); produce1_data(list,num); printf(排序前的数据为:n); print1_data(list,num); printf(n排序过程如下：n); HeapSort(list,num); printf(n最终的排序结果为:n); print1_data(list,num); pri