数据结构实验 实验10 快速排序

《数据结构实验 实验10 快速排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验五排序的操作(2)一、实验目的1．深刻理解排序的定义和各种排序方法的特点；2．掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。二、实现提示起泡排序的排序过程：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被放在最后。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被放在第n-1个位置。重复上述过程，直到“在一趟排序过程中没有进行

2、过交换记录的操作”为止。快速排序的基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。快速排序的排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设rp=r[s]，x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i=j为止。再分别对两个子序列进行快速排序，直

3、到每个子序列只含有一个记录为止。三、实验内容起泡排序与快速排序的实现，并统计每一种排序算法所耗费的时间。四、程序填空与调试#include#include#include#defineN10intE[N]={213,111,222,77,400,300,987,1024,632,555};voidmerge_step(inte[],inta[],ints,intm,intn)/*两个相邻有序段的合并*/{inti,j,k;k=i=s;j=m+1;while(i<=m&

4、&j<=n)/*当两个有序都未结束时循环*/if(e[i]<=e[j])/*取其中小的元素复制*/a[k++]=e[i++];elsea[k++]=e[j++];while(i<=m)/*复制还未合并完的剩余部分*/a[k++]=e[i++];while(j<=n)/*复制还未合并完的剩余部分*/a[k++]=e[j++];}voidmerge_pass(inte[],inta[],intn,intlen)/*完成一趟完整的合并*/{intf_s,s_end;f_s=0;while(f_s+len

5、段*/s_end=f_s+f_s+2*len-1;if(s_end>=n)/*最后一段可能不足len个结点*/s_end=n-1;merge_step(e,a,f_s,f_s+len-1,s_end);/*相邻有序段合并*/f_s=s_end+1;/*下一对有序段中左段的开始下标为上一对末尾+1*/}if(f_s

6、=0;p=(int*)malloc(n*sizeof(int));while(len

7、序列为:");for(i=000;i