《数据结构上机基本习题.ppt》由会员分享，可在线阅读，更多相关《数据结构上机基本习题.ppt（44页珍藏版）》请在三一办公上搜索。
1、单元实验二 排序算法,排序的分类,内部排序,外部排序,插入排序（直插排序、二分插入排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序（简单选择排序、树型排序、堆排序）,归并排序（二路归并排序、多路归并排序）,分配排序（多关键字排序、基数排序）,多路平衡归并排序,置换选择排序,最佳归并树,排序,直接插入排序,直接插入排序(Straight Insertion Sorting)的基本思想是：n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。,有序序列R1.
2、i-1,Ri,无序序列 Ri.n,有序序列R1.i,无序序列 Ri+1.n,冒泡排序,冒泡排序(Bubble Sorting)的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。,无序序列R1.n-i+1,有序序列 Rn-i+2.n,n-i+1,无序序列R1.n-i,有序序列 Rn-i+1.n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,第 i 趟起泡排序,若在一趟排序过程中没有进行过交换记录的操作，则整个排序过程终止。,简单选择排序,简单选择排序的基本思想是：第一趟在n个记录中选取最小记录作为有序序列的第一个记录，第二趟在n-1个记录中选取最小记录作为有序序列的第二
3、个记录，第i趟在n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。,有序序列R1.i-1,无序序列 Ri.n,第 i 趟简单选择排序,从中选出关键字最小的记录,有序序列R1.i,无序序列 Ri+1.n,基本要求,1用随机函数产生1000个（或更多）整数（或浮点数），保存在文件（intfile.dat/realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。（1）用冒泡法对数组A排序；（2）用简单选择排序方法对数组A排序；（3）用直接插入排序法对数组A排序；将上述排序算法分别用函数实现，输出每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的
4、时间（以s或ms为单位）；,基本要求,2将问题1中所有1000个（或更多）整数读入数组A，用快速排序算法对数组A中的元素排序，输出排序结果、排序过程中元素的比较和交换（移动）次数、排序算法消耗的时间;3.利用上面实现的任意一种排序算法，对实验题目一所产生的学生信息文件studinfo.dat，读取其中的所有学生信息：（1）按学号排序输出学生信息；（2）按姓名排序输出学生信息；（3）按三门课程的平均分从高到低排序输出学生信息（除了学生基本信息外，还要输出每个学生的平均成绩），最后再加一行输出信息：每门课程的平均成绩。,快速排序,快速排序(Quick Sorting)是迄今为止所有内排序算法中速度
5、最快的一种。其基本思想是：取待排序序列中的某个元素作为基准（也成为枢轴元素，一般取第一个元素），通过一趟排序，将待排序列划分为左右两个子序列，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字则大于或等于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。,无 序 的 记 录 序 列,无序的左子序列,无序的右子序列,枢轴,一次划分,分别进行快速排序,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,49,04,9,i,j,快速排序中的一趟划分,aj与pivot比较，aj小则ajai,38,65,97,13,27,49,55,1,2,3,
6、4,5,6,7,8,04,9,49,pivot,快速排序中的一趟划分,ai与pivot比较，ai大则ai aj；否则i增1,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,快速排序中的一趟划分,ai与pivot比较，ai大则ai aj；否则i增1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,aj与pivot比较，aj小则aj ai；否则j减1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivo
7、t,ai与pivot比较，ai大则ai aj；否则i加1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,aj与pivot比较，aj小则ai aj；否则j减1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,i与j相等时，完成一次划分，枢轴元素归位,快速排序中的一趟划分,38,27,13,49,97,49,55,1,2,3,4,5,6,7,8,04,65,9,int Partition(SqList/返回枢轴元素最后确定的位置/Partitio
8、n,38,65,97,13,27,49,55,49,04,8,40,30,20,15,9,25,1,2,3,4,5,6,7,8,10,5,9,i,j,快速排序中的一趟划分,10,10,快速排序,int Partition(SqList/返回枢轴元素的位置/Partition,void QSort(SqList/右子序列进行快速排序/if/QSort,快速排序过程分析,选作内容,用随机函数产生至少10000个整数，保存在文件（intfile.dat）中（1）通过建立大顶（根）堆实现堆排序，最后输出排序结果；（2）通过建立小顶（根）堆实现堆排序，每找出一个小元素就输出它，从小到大输出排序结果。,选
9、作内容,用随机函数产生至少10000个整数，保存在文件（intfile.dat）中，对其中的数据进行归并排序，最后将排序结果写入文件；产生两个已经排序的整数数据文件，将两个文件的数据归并成一个有序序列存入文件保存。,堆排序,堆的定义对于n个元素的序列k1,k2,.,kn，当且仅当满足以下关系时，称之为堆。,或,12,36,27,65,40,34,98,81,73,55,49,是小顶堆,12,36,27,65,40,14,98,81,73,55,49,不是堆,堆排序,堆(完全二叉树),96,83,38,11,27,9,(a)大顶堆(max heap),12,36,85,47,24,30,(b)小
10、顶堆(min heap),53,91,96,83,27,38,11,9,12,36,24,85,47,30,53,91,堆排序,对一组待排序记录的关键字，首先把它们按堆的定义建成小(大)顶堆，然后输出堆顶的最小(大)关键字所代表的记录，再对剩余的关键字建堆，以便得到次小(大)的关键字，如此反复进行，直到全部关键字排成有序序列为止。,实现堆排序需要解决两个问题：(1)如何建堆？(2)输出堆顶元素后，如何将剩余元素重新调整为一个新堆？,堆排序过程示例,下面是一个小顶堆，输出堆顶元素后（即将序列末端元素与堆顶元素交换），将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则
11、将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向,12,36,85,47,24,30,53,91,交换堆顶元素与序列末端的元素,比较,比较-,交换,return,堆排序过程示例(续),输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向,继续向叶子方向调整,比较,比较,交换,堆排序过程示例(续),一旦已调整为堆，则输出堆顶元素，重复将剩余元素重新调整为一个新堆。,交换堆顶元素与序列末端的元素,堆排序过程示例(续),输出堆顶元素后，将剩余元素重新调整为一个新堆,调整成堆,继续此过程，就可以将元
12、素按照需要的顺序排列要使得数组中元素最后从小到大排列，则宜采用大顶堆,堆排序过程分析,输出堆顶元素后，将剩余元素重新调整为一个新堆,反复将堆顶元素与序列末端的元素的交换，并重新调整成堆。,调整堆元素(筛选)对于给出的关键字序列，经初始建堆后便得到小(大)顶堆，从而得到最小(大)关键字。在输出堆顶元素之后，用堆中最后一个元素替代之。此时由于以K2和K3为根的子树仍具有堆的特性，因此只需自上而下进行调整即可。调整过程为：首先令K1的两个子树根进行比较，令其中较小(大)者与K1相比较，将最小(大)元素交换至K1，使得K1、K2和K3成为堆。由于交换后破坏了子树的堆性质，则需再次进行与上述过程类似的调
13、整，直至进行到最下层的叶结点为止。调整后即得到一个有n-1个元素的新堆，从而得到次小关键字。,堆排序过程分析(续),输出堆顶元素后，将剩余元素重新调整为一个新堆,调整堆元素(筛选)对于给出的关键字序列，经初始建堆后便得到小(大)顶堆，从而得到最小(大)关键字。在输出堆顶元素之后，用堆中最后一个元素替代之。此时由于以K2和K3为根的子树仍具有堆的特性，因此只需自上而下进行调整即可。首先令K1将的两个子树根进行比较，令其中较小(大)者与K1相比较，将最小(大)元素交换至K1，使得K1、K2和K3成为堆。由于交换后破坏了右子树的堆，则需再次进行与上述类似的调整，直至进行到最下层的叶结点。调整后即得到
14、一个有n-1个元素的新堆，从而得到次小关键字。,重复上述过程，将堆顶元素与堆中最后一个元素交换且调整，又得到了有n-2个元素的新堆。为节省存贮开销，可以把输出的最小(大)关键字放在Kn的位置上，把第二次输出的次小(大)关键字存放在Kn-1的位置上，直至最大(小)关键字放在K1的位置上。,如此，我们已经可以在初始情况为堆的情况下完成排序，那么，如何建立起初始堆呢？,建初始小顶堆,47,36,91,12,53,30,24,85,元素序列为：47,36,53,91,12,30,24,85,建立小顶堆,建初始堆,从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，
15、1等是否为堆，若否则调整为堆,return,建初始堆,47,36,85,12,24,30,53,91,从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆,(C),建初始堆,12,47,85,36,24,30,53,91,从最后一个具有叶子的结点(编号n/2)开始建子堆，依次考查结点n/2-1,n/2-2,.，1等是否为堆，若否则调整为堆,(e),当以下标1为根的完全二叉树为堆时，初始堆已建立,堆排序算法(续),typedef SqList HeapType;/堆采用顺序存储结构,void HeapSort(HeapType/将
16、H.rl.i-1 重新调整为大顶堆/HeapSort,for(i=H.length;i 1;-i)H.r1H.ri;/堆顶记录和当前未排子序列中最后一个记录相交换/三次移动元素 HeapAdjust(H,1,i-1);/将H.rl.i-1 重新调整为大/小顶堆,示例,将H建成大/小顶堆,for(i=H.length/2;i 0;-i)/把H建成大/小顶堆 HeapAdjust(H,i,H.length);,堆排序算法(筛选算法),typedef SqList HeapType;/堆采用顺序存储结构,void HeapAdjust(HeapType&H,int s,int m)/HeapAdju
17、st,rc=H.rs;/元素移动 for(j=2*s;j H.rj+l.key)+j;/j为key较小的记录的下标 if(rc.Key H.r j.key)break;H.rs=H.rj;/较小的孩子结点值换到父结点位置，元素移动 s=j;H.rs=rc;/rc应插入的位置在s处，元素移动,/H.rs.m中除H.rs.key外均满足堆的定义/调整H.rs的关键字，使H.rs.m成为一个小顶堆,示例,归并排序,归并所谓“归并”，是将两个或两个以上的有序序列合并成为一个新的有序序列。从第二章线性表的讨论中得知，将两个有序表归并为一个有序表，无论是顺序存储结构还是链式存储结构，都是容易实现的。利用归
18、并的思想可以进行排序。,归并排序可将由n个记录的一个无序序列看成是由n个长度为1的有序子序列组成的序列，然后进行两两归并，得到n/2个长度为2或1的有序子序列，再两两归并，如此重复，直到最后形成包含n个记录的一个有序序列为止。这种总是反复将两个有序序列归并成一个有序序列的排序方法称为两路归并排序。,有 序 序 列 Rl.n,有序子序列 Rl.m,有序子序列 Rm+1.n,2-路归并,两路归并过程示例,设初始关键字序列为:48 34 60 80 75 12 26 48*,48 34 6O 80 75 12 26 48*,第一趟归并：,34,48,60,80,第三趟归并：12,26,34,48,4
19、8*,60,75,80,60,80,12,75,26,48*,12,26,48*,75,34,48,第二趟归并：,合并两个序列时，将合并得到的序列与原序列分开存放也可以用分治思路处理,先分解再归并,设初始关键字序列为:48 34 60 80 75 12 26 48*,48 34 6O 80 75 12 26 48*,34 48,60 80,12 75,26 48*,12 26 48*75,34 48 60 80,12 26 34 48 48*60 75 80,两路归并排序算法,递归算法,void MergeSort(待排序列)/归并排序 if(待排序列长度 1)MergeSort(待排序列的前
20、半区间)；MergeSort(待排序列的后半区间)；已排好序的前半区间、后半区间合并成一个有序序列；/if/MergeSort,采用顺序存储结构，对于由下标st界定的一个序列，前半区间为s(s+t)/2，后半区间为(s+t)/2+1 t,void MergeSort(SqList/合并L.rsL.rm与L.rm+1L.rt/if/MergeSort,两路归并算法,以顺序表作为存储结构,void Merge(SqList&L,int i,int m,int n)/两路归并/引入辅助数组空间temp，有序序列为ri.m和rm+1.n/Merge,b=i;for(j=m+1,k=1;i=m+k)/f
21、or/ifi,if(L.ri.key L.rj.key)temp.rk=L.ri+;else temp.rk=L.rj+;,for(;i=m;)temp.rk+=L.ri+;for(;j=n;)temp.rk+=L.rj+;for(i=b,k=1;i=n;)L.ri+=temp.rk+;,随机数,随机函数rand()#include RAND_MAX在stdlib.h中定义，不大于双字节整数的最大值32767产生0,RAND_MAX 之间的随机数magic=rand();产生0,b-1 之间的随机数magic=rand()%b;产生a,a+b-1 之间的随机数magic=rand()%b+a;
22、,随机数,随机函数srand为函数rand()设置随机数种子来实现对函数rand所产生的伪随机数的“随机化”通过键入随机数种子，产生0,100之间的随机数scanf(%u,计算代码段运行时间示例,#include clock_t CLK_1,CLK_2;/typedeflongclock_t;CLK_1=clock();/此处为需要测试运行时间的代码段CLK_2=clock();printf(duration_time:%d,CLK_2 CLK_1);,#include time_t start_time,end_time;start_time=time(0);/此处为需要测试运行时间的代码段end_time=time(0);printf(duration_time:%lf,difftime(end_time,start_time);,
