数据结构与算法排序资料.docx

1、数据结构与算法排序资料数据结构与算法实验报告班级学号姓 名实验周次实验日期xxxxxxxxxxxxxxxxx2015年10月 28 日实验02：排序一、实验目的1掌握各种常用排序方法的特点及其存储的方式。2掌握各种排序算法的要求、方法和过程。3了解各种排序算法效率的分析和计算方法。二、实验内容以Sort01（ReferenceParameter）.cpp或者Sort02（PointerParameter）.cpp为基础，实现如图2-1程序界面所示的常用排序算法。注意：功能4（快速排序）、功能6（堆排序）和功能7（归并排序）是需要完成的部分；功能5（希尔排序）因为本学期采用的课本上没有提及，所以

2、直接将答案给出了，大家只需看懂理解即可，其它和排序无关的功能项均已给出实现代码，大家无需更改。三、实验要求1、Sort01（ReferenceParameter）.cpp和Sort02（PointerParameter）.cpp选做其中一题即可（两题代码的思路完全一致，只有实现时参数传递方式的差别）。2、演示程序SortDemo.exe中的所有排序均是升序排列，但完成本实验时，学号为单号的同学：排序时要求升序排列；学号为双号的：排序时要求降序排列。3、实验报告电子稿和打印稿及其它提交方面的要求同实验01。四、运行结果图2-1 随机产生一批整数并快速排序图2-2 随机排列表中元素并希尔排序图2-

3、3 随机排列表中元素并希尔排序图2-4 随机排列表中元素并归并排序五、参考程序#include stdio.h#include stdlib.h#include time.h#define MAX 50/ 顺序表结构体typedef struct int sMAX; / 存放一批随机整数，数组大小MAX不能扩充 int length; / 当前表中元素的个数 SeqList;/ 功能菜单void menu() printf(nt*排-序*n); printf(t* 1 随机产生一批整数 *n); printf(t* 2 手动输入一批整数 *n); printf(t* 3 将表中数据随机化 *n

4、); printf(t* 4 快速排序 *n); printf(t* 5 希尔排序 *n); printf(t* 6 堆排序 *n); printf(t* 7 归并排序 *n); printf(t* 8 依次显示表中所有数据 *n); printf(t* 0 退出程序 *n); printf(t*n);/* 初始化一个空的顺序表 */SeqList *init() / 开辟顺序表空间 SeqList *p=(SeqList *)malloc(sizeof(SeqList); / 设置顺序表的初始长度为0 p-length=0; / 返回整个顺序表的（起始）地址 return p;/* 随机产生

5、一批整数到线性表中 */void randGen(SeqList *p) int num, i; printf(请输入元素个数（=%d）：n, MAX-1); scanf(%d, &num); srand(int)time(0); if(num = MAX) / 随机产生num个整数存入顺序表中（从1号单元开始存放，0号单元留作“哨兵”） for(i=1; isi=1+(int)(100.0*rand()/(RAND_MAX+1.0); p-length=num; printf(顺序表中已成功放入%d个整数!n, num); else printf(顺序表空间不够，请重新输入元素个数!n);/

6、* 手动输入一批整数到线性表中 */void manInput(SeqList *p) int num, i; printf(请输入元素个数（=%d）：n, MAX-1); scanf(%d, &num); printf(请输入%d个整数：n, num); if(num = MAX-1) / 输入num个整数存入顺序表中（从1号单元开始存放，0号单元留作“哨兵”） for(i=1; isi); p-length=num; printf(顺序表中已成功输入%d个整数!n, num); else printf(顺序表空间不够，请重新输入元素个数!n);/* 将顺序表中现有元素打乱为随机排列 */v

7、oid randomizeList(SeqList *p) int i, selectLoc, tmp; / 借助选择法排序的思想，每次从尚未挑选的序列中随机挑选一个元素， / 将随机选中的元素交换到尚未选中元素序列的最前面或最后面。 for(i=1; ilength; i+) / 产生一个属于区间i,p-length的随机数selectLoc selectLoc = i+(int)(p-length-i)*rand()/(RAND_MAX+1.0); if(selectLoc != i) tmp = p-si; p-si = p-sselectLoc; p-sselectLoc = tmp;

8、 / 反过来再来一遍 for(i=p-length; i1; i-) / 产生一个属于区间0，i的随机数selectLoc selectLoc = 1+(int)(i*rand()/(RAND_MAX+1.0); if(selectLoc != i) tmp = p-si; p-si = p-sselectLoc; p-sselectLoc = tmp; printf(顺序表中的元素已经重新随机排列!n);/ 快速排序划分函数int Partition(int R, int low, int high) /对记录子序列Rlow.high进行一趟快速排序，并返回枢轴记录所在位置 int pivo

9、tkey; R0=Rlow; pivotkey=Rlow; while(lowhigh) /从表的两端交替向中间扫描 while(low=pivotkey) -high; if(lowhigh) Rlow+=Rhigh; /将比枢轴记录小的记录移到低端 while(lowhigh & Rlow=pivotkey) +low; if(lowhigh) Rhigh-=Rlow; /将比枢轴记录大的记录移到高端 Rlow=R0; return low; / 最后返回枢轴的位置（下标）/ 快速排序递归函数void QSort(int R, int s, int t) / 对记录Rs.t进行快速排序 i

10、nt pivotloc; if(ss,1,p-length); printf(已采用快速排序算法成功排序!n);/ 一趟希尔插入排序（实质为直接插入排序的变形）void shellInsert(SeqList *p, int dk) int i, j; for(i=dk+1; ilength; +i) if(p-si si-dk) p-s0 = p-si; / 设置插入排序的“哨兵” for(j=i-dk; j0 & p-s0 sj; j-=dk) p-sj+dk = p-sj; p-sj+dk = p-s0; /* 希尔排序（缩小增量排序），假设增量设置为5，3，1 */void shell

11、Sort(SeqList *p, int dlta, int t) int k; / 按增量序列dlta0.t-1对顺序表中的元素作希尔排序 for(k=0; ksm.n区间元素重新调整为堆的函数void heapAdjust(SeqList *p, int m, int n) / 使得p-sm.n成为大堆 int j,rc; rc=p-sm; for(j=2*m; j=n; j*=2) if(jsj sj+1) +j; if(rc=p-sj) break; p-sm=p-sj; m=j; p-sm=rc;/* 堆排序 */void heapSort(SeqList *p) / 对顺序表p进行

12、堆排序 int rc,i; for(i=p-length/2; i0; -i) heapAdjust(p,i,p-length); for(i=p-length; i1; -i) rc=p-s1; p-s1=p-si; p-si=rc; heapAdjust(p,1,i-1); printf(已采用堆排序算法成功排序!n); / 归并排序合并有序表/ 将有序的SR1.m和SRm+1.n归并为有序的TRi.nvoid Merge(int SR, int TR, int i, int m, int n) / 将有序的SRi.m和SRm+1.n归并为有序的TRi.n int k,j; for(j=m

13、+1,k=i; i=m & j=n; +k) /将SR中记录由小到大的并入TR if(SRi=SRj) TRk=SRi+; else TRk=SRj+; while(i=m) TRk+=SRi+; /将剩余的SRi.m复制到TR while(jlength+1)*sizeof(int); / 调用递归函数作归并排序 Msort(p-s, auxSpa, p-s, 1, p-length); / 释放辅助空间 free(auxSpa); printf(已采用归并排序算法成功排序!n);/* 显示表中所有数据 */void showAll(SeqList *p) int i; if(p-lengt

14、h 0) printf(当前表中的元素个数为%d，依次如下：n, p-length); for(i=1; ilength; i+) printf(%d , p-si); printf(n); else printf(当前顺序表为空!n);void main() int choice=-1; SeqList *plist; int incArr=5,3,1; / 将希尔排序的增量设置为5，3，1 plist=init(); while(1) menu(); fflush(stdin); printf(t请选择一个菜单项：); scanf(%d, &choice); switch(choice)

15、case 1: / 随机产生一组整数放入表中 randGen(plist); showAll(plist); break; case 2: / 手动输入一批整数放入表中 manInput(plist); showAll(plist); break; case 3: / 将现有表中数据随机化排列 randomizeList(plist); showAll(plist); break; case 4: / 快速排序 quickSort(plist); showAll(plist); break; case 5: / 希尔排序（增量为3个，依次为5，3，1） shellSort(plist, incArr, 3); showAll(plist); break; case 6: / 堆排序 heapSort(plist); showAll(plist); break; case 7: / 归并排序 mergeSort(plist); showAll(plist); break; case 8: / 按顺序显示表中所有数据 showAll(plist); break; case 0: exit(0); break; default: printf(t您输入的菜单项不存在，请重新选择!n); choice=-1; / 表示未选择菜单项 或者 菜单项选择错误