算法设计与分析实验报告
实验一 快速排序
院班学姓
系级号名
：
： 计算机科学与技术 ： ：
任课教师： 成
绩
：
湘 潭 大 学 2016年5月
实验一 快速排序
一. 实验内容
运用分治递归思想，编程实现快速排序算法。通过不同实例测试，分析最坏、最好、平均情况下的时间复杂度，并设计实验程序验证分析结果。
二．实验目的
1、理解递归的概念及实现方法；
2、掌握分治策略的基本思想以及用分治法解决问题的一般技巧； 3、掌握求解递归算法时间复杂度的一般方法。
三. 算法描述
/*递归形式的快速排序算法*/
Void QSort(SqList &L，int low,int high){
//对顺序表L中的子序列L.r[low..high]作快速排序
If(low < high){ pivotloc = Partition(L,low,high);//将L.r[low..high]一分为二
QSort(L,low，pivotloc - 1); //对低子表递归排序 QSort(L，pivotloc + 1,high); //对高子表递归排序 }
}//QSort
Void QuickSort(SqList &L){ //对顺序表L作快速排序
QSort(L,1,L.length); }//QuickSort
四. 算法实现
1.数据结构及函数说明
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比
另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
int Partition (SqList &L,int low,int high){
//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所 //在位置，此时在它之前的记录均不大于它。
L.r[0] = L.r[low];//用子表的第一个记录作枢轴记录
2
pivotkey = L.r[low].key;枢轴记录关键字
while(low < high){ //从表的两端交替的向中间扫描
while(low < high && L.r[high].key >= pivotkey) --high; L.r[low] = L.r[high]; //将比枢轴记录小的记录移到低端 while(low < high && L.r[high].key <= pivotkey) ++low; L.r[high] = L.r[low]; //将比枢轴记录大的记录移到高端 }
L.r[low] = L.r[0]; //枢轴记录到位 return low; }
//返回枢轴位置
函数说明：
int choose_pivot(int i,int j ) {
return((i+j) /2);//取中轴数 }
2.源程序代码
#include
#include
int choose_pivot(int i,int j ) {
return((i+j) /2); }
void quicksort(int list[],int m,int n) {
int key,i,j,k; if( m < n)
{
k = choose_pivot(m,n); swap(&list[m],&list[k]); key = list[m]; i = m+1; j = n;
while(i <= j)
3
