排序算法的实现.doc

附件2：北京理工大学珠海学院实验报告ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY班级 学号 姓名 指导教师 成绩实验题目 排序算法的实现 实验时间 一、实验目的、意义（1）掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识（2）掌握Shell排序的的基本思想和算法实现（3）掌握快速排序的基本思想和算法实现（4）掌握选择排序中堆排序的基本思想和算法实现（5）了解归并排序算法的基本思想和程序实现二、实验内容及要求说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：本实验含有四部分内容直接插入排序、希尔排序、选择排序、快速排序，在上述内容的基础上，将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路，新算法。1.考虑对20个整数的随机输入进行排序，各排序功能基本上都可以成为独立调用的模块，因此可以先写出排序算法，然后用主函数调用。三、实验所涉及的知识点本实验涉及各类排序算法。Shell排序：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量重复上述分组和排序，直至所取的增量dt=1(dtdt-1d2d1)，即所有记录放在同一组中进行直接插入排序为止。快速排序是对冒泡法的改进，其基本思想是：通过一趟排序将待排文件分割成独立的两部分，其中一部分记录的关键字值均比另一部分记录的关键字小，然后分别对这两部分进行排序，以达到整个序列有序。四、实验记录 这次实验的各种排序方法太多了，导致了各种算法的混乱，加上书本上的伪代码，在调试过程中，寻求了同学的帮忙和借阅同学的代码才得以完成这次实验。五、实验结果及分析（1） 插入排序；（2） 希尔排序；（3） 选择排序中的堆排序；（4）快速排序；六、总结与体会直接插入排序属于稳定的排序，快速排序属于不稳定排序，希尔排序属于不稳定排序，堆排序属于不稳定排序。通过这次排序算法的实验，虽然算法只是按照书本上的算法，但总算对于各种算法有了大致的了解。七、程序清单(包含注释)#include#include/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASLIBLE -1#define OVERFLOW -2#define MAXSIZE 20 /一个用作示例的小顺序表的最大长度#define EQ(a, b) (a) = (b)#define LT(a, b) (a) (b)#define LQ(a, b) (a) = (b)/-存储结构-typedef int KeyType; /定义关键字类型为整数类型typedef int Status;typedef int ElemType;typedef struct KeyType key; /关键字项/InfoType otherinfo; /其他数据项RedType; /记录类型typedef struct RedType rMAXSIZE + 1; /r0闲置或用作哨兵单元int length; /顺序表的长度SqList; /顺序表类型/-基本操作的函数实现-Status InitSqList(SqList *L) /构造一个空的线性表 Lint i;for (i = 0; i ri.key = 0;L - length = 0;return OK;/InitListStatus InsertSqList(SqList *L, KeyType num) / 将 num 插入到顺序表 L 中L - length += 1;L - rL - length.key = num;return OK;/InsertSqListvoid InsertSort(SqList *L) /对顺序表 L 作直接插入排序int i, j;for(i = 2; i length; i+) if(LT(L - ri.key, L - ri - 1.key) / ri插入有序子表L - r0 = L - ri; /复制为哨兵L - ri = L - ri - 1;for(j = i - 2; LT(L - r0.key, L - rj.key); j-)L - rj + 1 = L - rj; /记录后移L - rj + 1 = L - r0; /插入到正确位置/InsertSortStatus SqListTraverse(SqList *L, void (*visit)(KeyType) / 对顺序表 L 进行遍历，并对每个元素调用 visit 函数int i;for (i = 1; i length; i+) visit(L - ri.key);return OK;void visit(KeyType num) printf(%3d , num);void ShellInsert(SqList *L, int dk) /对顺序表 L 作一趟希尔插入排序。/前后记录位置的增量是 dk ，而不是 1/r0只是暂存单元，不是哨兵。当 j = 0 时，插入位置已找到int i, j;for(i = dk + 1; i length; i+) if(LT(L - ri.key, L - ri - dk.key) /需将 L - ri 插入有序增量子表L - r0 = L - ri; /暂存在 L - r0for(j = i - dk; j 0 & LT(L - r0.key, L - rj.key); j -= dk)L - rj + dk = L - rj; /记录后移，查找插入位置L - rj + dk = L - r0; /插入/ShellInsertvoid ShellSort(SqList *L, int dlta, int t) /按增量序列 dlta0.t-1对顺序表 L 作希尔排序int k;for(k = 0; k rs.m 中记录的关键字除 H - rs.key 之外均满足堆的定义，本函数调整 H - rs/的关键字，使 H - rs.m 成为一个大顶堆（对其中记录的关键字而言）RedType rc;int j;rc = H - rs;for(j = 2 * s; j = m; j *= 2) /沿 key 较大的孩子结点向下筛选if(j rj.key, H - rj + 1.key) +j; / j 为 key 较大的记录的下标if(!LT(rc.key, H - rj.key) break; / rc 应插入的位置 s 上H - rs = H - rj;s = j;H - rs = rc; /插入/HeapAdjustvoid HeapSort(HeapType *H) /对顺序表 H 进行堆排序int i, t;for(i = H - length / 2; i 0; i-) /把 H - r1.H - length 建成大顶堆HeapAdjust(H, i, H - length);for(i = H - length; i 0; i-) t = H - r1.key; /将堆顶记录和当前未经排序子序列 H - r1.i 中H - r1.key = H - ri.key; /最后一个记录相互交换H - ri.key = t; HeapAdjust(H, 1, i - 1); /将 H - r1.i - 1 重新调整为大顶堆/HeapSortint Partition(SqList *L, int low, int high) /交换顺序表 L 中子表 rlow.high 的记录，枢轴记录到位，并返回其所在的位置，此时/在它之前（后）的记录均不大（小）于它int pivotkey;L - r0 = L - rlow;pivotkey = L - rlow.key;while(low high) while(low rhigh.key = pivotkey) -high;L - rlow = L - rhigh;while(low rlow.key rhigh = L - rlow;L - rlow = L - r0;return low;/Partitionvoid QSort(SqList *L, int low, int high) /对顺序表 L 中的子序列 L - rlow.high 作快速排序int pivotloc;if(low rlow.high一分为二QSort(L, low, pivotloc - 1); /对低子表递归排序，pivotloc是枢轴位置QSort(L, pivotloc + 1, high); /对高子表递归排序/QSortvoid QuickSort(SqList *L) /对顺序表 L 作快速排序QSort(L, 1, L - length);/QuickSortint main() SqList R;int select;int dlta3 = 5, 3, 1;InitSqList(&R);InsertSqList(&R, 80);InsertSqList(&R, 50);InsertSqList(&R, 79);InsertSqList(&R, 15);InsertSqList(&R, 46);InsertSqList(&R, 4);InsertSqList(&R, 24);InsertSqList(&R, 13);InsertSqList(&R, 11);InsertSqList(&R, 99);InsertSqList(&R, 85);InsertSqList(&R, 77);InsertSqList(&R, 29);InsertSqList(&R, 18);while (1) system(cls);printf(初始数据：80 50 79 15 46 4 24 13 11 99 85 77 29 18n);printf(方法：1插入排序n);printf(2希尔排序n);printf(3选择排序（堆排序）n);printf(4快速排序n);do printf(请选择：);scanf(%d, &select);