閹即鈧垼濮冲鈧�
实验九 快速排序算法设计
一、预习报告
实验目的
1、 掌握用Turbo C上机调试常规排序算法的程序； 2、 掌握快速排序的基本方法和过程
基本原理与方法 利用快速排序算法原理用C语言编程实现
实验设备 PC机一台、配置Turbo C软件 二、实验内容
〔问题描述〕 对于用户输入的数据序列，用快速排序法按从大到小和小到大两种顺序进行
排序，并显示每一趟的排序过程；
[基本要求] 采用递归与非递归两种算法 ； [算法实现] 利用快速排序原理编写C程序； [参考程序]
#include
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)