数据结构实验报告（华夏）

实验九 快速排序算法设计

一、预习报告

实验目的

1、 掌握用Turbo C上机调试常规排序算法的程序； 2、 掌握快速排序的基本方法和过程

基本原理与方法 利用快速排序算法原理用C语言编程实现

实验设备 PC机一台、配置Turbo C软件 二、实验内容

〔问题描述〕 对于用户输入的数据序列，用快速排序法按从大到小和小到大两种顺序进行

排序，并显示每一趟的排序过程；

[基本要求] 采用递归与非递归两种算法 ； [算法实现] 利用快速排序原理编写C程序； [参考程序]

#include #difile MAX 100

void disparr ( ) ; /*建立原始数据序列函数*/ int a[MAX],n , m ; void creatarr () { int i=0 ;

printf (“建立原始数据序列\\n”) ; printf (“\\t元素个数：“)； scanf(%d”,&n); while ( i

{ printf (“\\t输入第%d个元素的值：“，i+1)；

scanf(%d”,&a[i]; i++ ; } }

int cmp ( int lval , int rva1 , int order ) { if (order = = 1)

{ if (lva1 < rva1 ) return (1)

else return (0) ; } else

{ if (lva1 > rva1 ) return (1)

else return (0) ; } }

void quicksort(int x[] , int low , int high , int order )

/* 把x[low]至x[high]的元素进行快速排序*/ { int i= low , j=high , k , temp ; temp=x[i]; while (i

while ( i

{ x[i]=x[j] ; i++ ; }

while ( i

{ x[j]=x[i] ; j-- ; }

} x[i]=temp ;

printf (“\\t (%d) “, m++) ; for ( k=0 ; k < n ; k++)

{ if (k = = low) printf ( “ { “ } ; if (k = = i) printf ( “) “ ) ; printf (“ %d “, x[k] ) ;

if (k = = i ) printf ( “ { “ } ; if (k = = high) printf ( “) “ ) ; } printf (“ \\n “ ) ;

if ( low < i) quicksort( x , low , i-1 ,order ) ; if ( i

void disparr ( ) /* 输出序列函数*/ { int i ;

for (i=0 ; i

main () {

creatarr ( ) ; m=1 ;

printf( “\\n 原来的数据序列为： “)； disparr ( ) ;

printf( “\\n 从小到大排序 ： “)； quicksort( a , 0 , n-1 ,1) ;

printf( “\\n 从小到大排序的数据序列为 ： “)； disparr ( ) ; m=1;

printf( “\\n 从大到小排序 ： “)； quicksort( a , 0 , n-1 ,0) ;

printf( “\\n 从大到小排序的数据序列为 ： “)； disparr ( ) ; }

三、实验结果与分析讨论

1． 输入的数据序列为：9，4，0，2，5，3，8，7，1，6 程序执行的结果是：

2． 若输入的数据序列为：0，1，2，3，4，5，6，7，8，9 程序执行的结果： 3. 若输入的数据序列为：9，8，7，6，5，4，3，2，1，0 程序执行的结果

4. 比较运行结果，找出快速排序法的使用场合。

作业部分

第1章 绪论

1 、有以下几种用二元组表示的数据结构，画出它们对应的图形，指出它们分别属于何种结构

（1）A=(K,R) 其中 K={a，b，c，d，e} R={,,,

（2）B=(K,R) 其中 K={a，b，c，d，e} R={,,,

（3）C=(K,R) 其中 K={a，b，c，d，e} R={,,,

2 、下列算法suanfal(n)中语句〞x=x*2;〞的执行次数是多少？算法的时间复杂度是多少？

Void suanfal(int n) { int i,j,x=1;

for(i=0;i

printf(〞%d〞,x); }

3、执行和分析下面的算法： int suanfan1(int m,int n) { int i,j,s=0；

for(i=0；i<=m；i++) { for(j=0；j<=n；j++)

s++； printf(\； }

return s； }

回答问题：

（1）表达式\共计执行多少次？ （2）表达式\共计执行多少次？ （3）表达式\共计执行多少次？ （4）分析算法的时间复杂度；

（5）假定m=n=4,算法的输出结果是什么？算法的返回值是多少？ 4、算法分析题 设有算法如下：

float what (float x, int n) { float y; y=x;

while(n>1)