《算法分析与设计实验报告2： 快速排序及归并排序(分治策略)》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告2： 快速排序及归并排序(分治策略)（4页珍藏版）》请在金锄头文库上搜索。
1、天津商业大学学生实验报告开课实验室： 开课时间 2019年4月26日 实验报告 2019年5月 9日学院名称信息工程学院年级、专 业、班软件1803班学号20181132姓 名董健伟同组 姓名无课程 名称算法分析与设计实验项 目名称实验二快速排序及归并排序(分治策略)指导教师宋建材实验类型验证综合口设计口创新口成绩教师评语：教师签字：一、实验目的通过快速排序和归并排序的算法实现来加深对分治策略的了解。二、实验描述快速排序和归并排序都是使用分治策略的算法，他们将原有冒泡排序和插入排序的时间复杂度从O(n2) 降低到O(nlgn)。是当下最为流行的排序算法。三、实验内容编程完成随机生成100个数，
2、用快速排序和归并排序进行排序，并完成实验报告(要求粘贴代码和实验 结果截图)。四、实验代码1、归并排序#includeiostream#include ti me.h#define MAX 100using namespace std;void merge(int array, int p, int(, int r)int i, k;int beginl, endl, begin2, end2;int* temp = new intr - p + 1;beginl = p ;endl =(;begin2 = q + 1;end2 =:;k = 0;while (beginl = endl) &
3、 (begin2 = end2)if (array beginl array begin2)te mpk = array beginl;begin1+;elsetempk = arraybegin2; begin2+;k+;while (beginl = endl)tempk+ = arraybegin1+;while (begin2 = end2)tempk+ = arraybegin2+;for (i = 0; i (r - p + 1); i+)array p + i = te mpi;delete (temp);void merge_sort(int data, int left, i
4、nt right)if (left right)int mid = (left + right) / 2;merge_sort(lata, lef , mid);merge_sort(lata, mid + 1, right); merge(data, left, mid, right);void main()int numberMAX = 0 ;srand( time (NULL);printf(排序前：);for (int i = 0; i MAX; i+)numberi = rand() % 100;prin tf (%d , numberi);cout endlendl;merge_s
5、o rt( number, 0, 99);printf(排序后：);for (int j = 0; j MAX; j+)prin tf (%d , numberj);2、快速排序#includeiostream#include ti me.h#define MAX 100#define SWAP(x,y)int t;t二x;x=y;y=t; using namespace std;void quicksort(int number, int left, int right) int i, j, s; if (left right)s = number(left + right) / 2;i =
6、 left - 1;j = right + 1; while (1)while (number +i s);if (i = j)break; SWAP (number i, numberj);quickso rt( number, lef t, i - 1); quicksort(number, j+1, right);void main()int numberMAX = 0 ; srand( time (NULL); printf(排序前：);for (int i = 0; i MAX; i+) numberi = rand() % 100; prin tf (%d , numberi);c
7、out endl endl; quickso rt( number, 0, 99);printf(排序后：);for (int j = 0; j MAX; j+)prin tf (%d , numberj);五、实验结果截图Microwft Visual 5tudi o 週试空制台评序前;62 5 70 26 9225 99 71 50 61 41 50 -44 4fi 5 S671 6726 4147 86 85 95 12 29 57 41 63 51 71 18 20 18 1 83 34 3 47 20 4311 77 曲 76 65 73 Si 91 10 32 21 51 37 I
8、S 7 63 16 40 47 20 5 74 6S 7S3752595B5 66 52 9C: UsersLenDosoijr匚erepoEPro iectSMebugPr 口 Ge 蛊住颯试停止时自动关闭控制台.扉用“一尸：空ct2b曰盖曰1进走 幻-厂“调舌插崔餐键奠闭此窗口.7 9 10 11 12 15 16 18 10 18 20 20 20 2D 21 22 25 25 26 26 26 50 50 51 51 52 52 56 57 58 58 58 59 59 61 62 63 63 64 65 65 ，05 S6 86 87 S9 91 92 92 9& 99 992 5
9、5 .46 4 :79 8c排序后：1 2 卍 43 44 44 476 76 77 ?!间控制台。排序丽;S62881283080 4S21 33139126710653947805252P 72 52213991317721 1372 404224.7E；75gg! 55，7C)12:3152! 7C75 69 0 i564S96229550 SQ11 4B5E2695140653Q5850:排序肓:o :2 24 |6 67 :10 1011 121213131921212122242525(40 414212 434347 18 4843 5050 I50515252525253555556Microwft Visual 5tudi c 週试逹制台2658285856675E6536 8722 20791567769226853889593725725E6：4 调试停止时OeVj-u此窗r.75 75 7578 80 80SL 34 36 88 90909191949596间控制台”注1.每个实验项目一份实验报告。2.实验报告第一页学生必须使用规定的实验报告纸书写，附页用实验报告附页纸或 A4 纸书写。3实验教师必须对每份实验报告进行批改，用红笔指出实验报告中的错、漏之处，并给出成绩，签全名、注明日期。
