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

实验五 排序的操作(2)一、 实验目的1深刻理解排序的定义和各种排序方法的特点；2掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。二、 实现提示起泡排序的排序过程：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被放在最后。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被放在第n-1个位置。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。快速排序的基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。快速排序的排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设rp=rs，x=rp.key。初始时令i=s, j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i=j为止。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。三、 实验内容起泡排序与快速排序的实现，并统计每一种排序算法所耗费的时间。四、程序填空与调试#include#include#include#define N 10int EN = 213, 111, 222, 77, 400, 300, 987, 1024, 632, 555 ;void merge_step( int e, int a, int s, int m, int n )/* 两个相邻有序段的合并 */int i, j, k;k = i = s;j = m + 1;while( i = m & j=n )/* 当两个有序都未结束时循环 */if( ei = ej )/* 取其中小的元素复制 */ak+=ei+;elseak+ = ej+;while( i = m ) /* 复制还未合并完的剩余部分 */ak+ =ei+;while( j = n ) /* 复制还未合并完的剩余部分 */ ak+ = ej+;void merge_pass( int e, int a, int n, int len )/* 完成一趟完整的合并 */int f_s, s_end;f_s = 0;while( f_s + len = 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 n )/* 当还剩一个有序段时， 将其从e复制到a */for( ; f_s n; f_s+ )af_s = ef_s;void merge( int e, int n )/* 二路合并排序 */int *p, len=1, f=0;p = (int *)malloc( n * sizeof(int) );while( len n ) /* 交替地在e和p之间来回合并 */if( f = 0 )merge_pass(e,p,n,len);elsemerge_pass(p,e,n,len);len*=2;/* 一趟合并后，有序结点数加倍 */f = 1 - f;/* 控制交替合并 */if( f = 1 )/* 当经过奇数趟合并时，从p复制到e */for( f = 0; f n; f+ )ef = pf;free( p );void main()int i;printf( 归并排序，初始数据序列为:n );for( i = 000; i N; i+ )printf( %d , E