快速排序算法实验报告

快速排序算法实验报告 篇一:快速排序(实验报告附C++源码) 快速排序 一、 问题描述 在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。 只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。 二、 需求分析 1. 输入事件件数n，分别随机产生做完n件事所需要的时间; 1 2. 对n件事所需的时间使用快速排序法，进行排序输出。排序时，要求轴 值随机产生。 3. 输入输出格式: 输入: 第一行是一个整数n，代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 任务的件数。 接下来一行，有n个正整数，代表每件任务所用的时间。 输出: 输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。 4. 测试数据: 输入 9 5 3 4 2 6 1 5 7 3 输出 1 2 3 3 4 5 5 6 7 三、 概要设计 抽象数据类型 因为此题不需要存储复杂的信息，故只需一个整型数组就可以了。 算法的基本思想 对一个给定的进行快速排序，首先需要选择一个轴值，假设输入的数组中有k个小于轴值的数，于是这些数被放在数组最左边的k个位置上，而大于周知的结点被放在数组右边的n-k个位置上。k也是轴值的下标。这样k把数组分成了 2 两个子数组。分别对两个子数组，进行类似的操作，便能得到正确的排序结果。 程序的 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 输入事件件数n--随机产生做完没个事件 所需时间--对n个时间进行 排序--输出结果 快速排序方法(因图难画，举一个实例): 初始状态 72 6 57 88 85 42 l r 第一趟循环 72 6 57 88 85 42 l r 第一次交换 6 72 57 88 85 42 l r 第二趟循环 6 72 57 88 85 42 r l 第二次交换 72 6 57 88 85 42 r l 反转交换 6 72 57 88 85 42 r l 这就是依靠轴值，将数组分成两部分的实例(特殊情况下，可能为一部分，其中42是轴值)。对分成的两部分数组，分别尽心类似的操作，便可得符合要求的结果。 快速排序的函数模块; void qsort(int* array,int l,int r) { if(r=l)return; int pivotIndex=l+rand()%(r-l+1);//随机选定轴值 swap1(array,pivotIndex,r);//将选定的轴值放到每段数组的最后 int k=partition(array,l-1,r,array[r]); //依靠轴值，将数组分//成两部分 swap1(array,k,r);//将轴值放到正确的位置上 qsort(array,l,k-1);//递归调用，对数组左右两部分进行排序 3 qsort(array,k+1,r); } /*将大于轴值的放右边，小于轴值的放左边 算法实现*/ int partition(int* array,int l,int r,const int pivot) { do{ while(array[++l]pivot); while((r!=0)&&(array[--r]pivot)); swap1(array,l,r); }while(lr); } swap1(array,l,r); return l; 算法的时空分析 快速排序在最差情况下，时间代价为Θ(n2)，但很少出现这种情况。如果快速排序找到了完美的轴值，那么整个算法的时间代价为Θ(n?n)。 输入和输出的格式 输入 n= //提示 等待输入 输出 原始序列: //提示 随机产生的n个随机数 结果://提示 正确的排序结果 四、 测试结果 五、 实验心得(可选) 这个实验，不难。但是关键在于理解快速排序的那个过程， 4 如何根据轴值将数组分成两部分，然后将轴值放到合适的位 置，继续对分成两部分的数组，执行类似的操作。 六、 附录(实验源码) #includeiostream #includectime using namespace std; //产生n个随机数，存储到数组 int* crtArray(int& size){ int n; cout "n="; cin n; //设置随机种子 srand(time(NULL)); int* intArray=new int[n]; size=n; cout "原始序列: endl; for(int i=0;in;i++) { intArray[i]=rand()%10;if(intArray[i]==0){ i--; continue;}cout intArray[i] "; } cout endl; return intArray; } //交换数组中的两个值 void swap1(int* array,int& a,int& b){ int temp=array[a]; array[a]=array[b]; array[b]=temp; } //对指定的数组部分进行分割 int partition(int* array,int l,int r,const int pivot) { do{while(array[++l]pivot);while((r!=0)&&(array[--r]=pivot));swap1(array,l,r); }while(lr); swap1(array,l,r); return l; } 5 //快速排序的实现部分 void qsort(int* array,int l,int r) { if(r=l)return; int pivotIndex=r; int k=partition(array,l-1,r,array[r]); swap1(array,k,r); qsort(array,l,k-1); qsort(array,k+1,r); } /*主函数*/ int main() { int size; int* Array; Array=crtArray(size); qsort(Array,0,size-1); cout "结果: endl; for(int i=0;isize;i++)cout Array[i] "; cout endl; return 0; } 篇二:数据结构实验八 快速排序实验报告 数据结构实验课程最终报告 题 目:实验八快速排序 专业班级:计算机科学与技术 姓 名:XXX 学 号: 指导老师:李晓鸿 完成日期:2015.01.06 一、 需求分析 背景 排序是计算机内经常进行的一种操作，其目的是将一组 “无序”的记录序列调整为“有序”的记录序列。 假设含n个记录的序列为{ R1, R2, ?， Rn } 其相应的关键字序列为 { K1, K2, ?，Kn } 6 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 : Kp1?Kp2???Kpn 按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, ?，Rpn }的操作称作排序。 排序算法是计算机科学中最重要的研究问题之一。对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。 例1:有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据支票的号码对支票排序; 例2:在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将各对象排序，以便自下而上地绘出对象。 例3:在一个由n个数构成的集合上，求集合中第i小/大的数。 例4:对一个含有n个元数的集合，求解中位数、k分位数。 1. 问题描述 在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件 7 地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。 只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。 2. 程序要求实现的功能 当有 n 件任务同时来临时，每件任务需要用时ni，求出让所有任务等待的时间和最小的任务处理顺序。 3. 输入输出要求 a) 输入要求: 第一行是一个整数n，代表任务的件数。 接下来一行，有n个正整数，代表每件任务所用的时间。 b) 输出要求: 输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。 4. 测试数据 1. 输入: 请输入任务件数:-1 8 输出: 输入有误，请重新输入～ 2. 输入: 请输入任务件数:4 请输入各任务所需时间:2 4 3 0 输出: 输入有误，请重新输入～ 3. 输入: 请输入任务件数:4 请输入各任务所需时间:2 4 3 6 输出: 任务执行的先后顺序为: 2 3 4 6 4. 输入: 请输入任务件数:9 请输入各任务所需时间:5 3 4 2 6 1 5 7 3 输出: 任务执行的先后顺序为: 1 9 2 3 3 4 5 5 6 7 二、 概要设计 (一) 函数调用关系图 int int Partition(int start,int random(int start,int end) ; void change(int a[],int i,int j); a[],int 主 函数 void QuickSort(int a[],int end); start,int end); void QuickSort(int a[],int start,int end); 三、 详细设计 (一)物理数据类型 本程序所输入的任务件数和任务时间均为整数，可使用整 10 数 int实现数据的存储。使用数组实现快速排序。 (二)具体步骤和伪代码 1. 输入任务件数及任务时长 while(1) { cout"请输入任务件数: "; cinsize; while(size) //任务件数大于0，则执行该循环，否则重新输入件数{ int i; cout"请输入各任务所需时间:"; for(i=0;isize;i++) { cina[i]; if(a[i]=0) { cout"输入有误，请重新输入～"endl; break; } } if(i==size) break; 11 } cout"输入有误，请重新输入～"endl; } 2. 调用函数取随机轴值 int random(int start,int end) { int t; srand(time(NULL));//设置随机数种子，对多组数据排序时不会取相同的轴值 while(1) { t=rand()%(end+1); if(t=start) return t; } } 3. 数组中的两个元素交换位置 void change(int a[N],int i,int j) { int t; t=a[i]; a[i]=a[j]; a[j]=t; 12 } 4. 快速排序时对数据进行划分区域 int Partition(int a[],int start,int end) { int temp=random(start,end);//得到随机轴值 change(a,temp,end); int i=start-1;//i用来指示轴值之后插入的位置 int base=a[end]; //以最后一个数作为划分的基点 for(int j=start;jend;j++) { if(a[j]=base) { i++; change(a,i,j); } } change(a,i+1,end); return i+1; } 5. 快速排序 void QuickSort(int a[N],int start,int end) { 13 if(end=start) return;//没有数据或只有一个数据 篇三:实验报告_排序与查找 电 子 科 技 大 学 实验报告 课程名称: 学生姓名:学 号:点名序号:指导教师: 实验地点: 实验时间: 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名 学 号: 指导教师: 实验地点: 基础实验大楼 实验时间:5月20日 一、实验室名称:软件实验室 二、实验项目名称:数据结构与算法—排序与查找 三、实验学时:4 四、实验原理: 快速排序的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 14 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据(通常选用第一个数据)作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是: 1)设置两个变量I、J，排序开始的时候I:=1，J:=N 2)以第一个数组元素作为关键数据，赋值给X，即X:=A[1]; 3)从J开始向前搜索，即(J:=J-1)，找到第一个小于X的值，两者交换; 4)从I开始向后搜索，即(I:=I+1)，找到第一个大于X的值，两者交换; 5)重复第3、4步，直到I=J。 二分法查找(折半查找)的基本思想: (1)确定该区间的中点位置:mid=(low+high)/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置 (2)将待查a值与结点mid的关键字(下面用R[mid].key)比较，若相等，则查找成功，否则确定新的查找区间: A)如果R[mid].keya，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].keya,则等于a的关键字如果存在，必然在 15 R[mid].key右边的表中。这时low=mid; C)如果R[mid].key=a，则查找成功。 (3)下一次查找针对新的查找区间，重复步骤(1)和(2) (4)在查找过程中，low逐步增加，high逐步减少，如果highlow，则查找失败。 五、实验目的: 本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。 六、实验内容: (1)实现数据序列的输入; (2)实现快速排序算法,并对输入的序列排序后输出; (3)实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地 查找,并输出查询结果。 七、实验器材(设备、元器件): PC机一台，装有C语言集成开发环境。 八、数据结构与程序: #includestdio.h #includestdlib.h #define MAX 1000 #define FROMFILE 1 typedef struct JD{ 16 int key; }JD; int bich(JD r[],int n,int k) { int low,high,mid,found; low=1; high=n; found=0; while((low=high)&&(found==0)) { mid=(low+high)/2; if(kr[mid].key) low=mid+1; else if(k==r[mid].key) found=1; elsehigh=mid-1; } if(found==1) return(mid); else return(0); } void quicksort(JD r[],int low,int high){ int i,j,k; JD x; if(low=high)return; i=low; j=high; 17 x=r[i]; while(ij){ while((ij)&&(r[j].key=x.key))j--;if(ij){r[i]=r[j];i++ ;} while((ij)&&(r[i].key=x.key))i++;if(ij){r[j]=r[i];j-- ;} } r[i]=x; quicksort(r,low,j-1); quicksort(r,j+1,high); }//快速排序 int main(){ printf("欢迎使用快速排序与二分查找。\n\n"); #ifdef FROMFILE printf("请输入你所要查找的数组长度:"); int length; scanf("%d",&length); getchar(); JD a[length+1]; a[0].key=0; 18 int i; for(i=1;i=length;i++){ printf("输入第%d个数字:",i); scanf("%d",&a[i].key); getchar(); } #else FILE *fp; fp = fopen("test.txt","r"); if(!fp) { printf("文件不存在!"); return 0; } JD a[MAX]; a[0].key=0; int i=1; while (fscanf(fp,"%d",&a[i++].key)!=EOF); int length=i-1; printf("文件内的信息:"); for (i=1;ilength;i++) { 19 printf("%d ",a[i].key); } printf("\n"); length--; fclose(fp); #endif quicksort(a,0,length); printf("\n"); int key; printf("请输入你想查找的数字:"); scanf("%d",&key); getchar(); printf("\n"); int location=bich(a,length,key); printf("位置 :"); for(i=1;i=length;i++){ printf("%3d ",i); } printf("\n"); printf("数字 :"); for(i=1;i=length;i++){ printf("%3d ",a[i].key); 20 } printf("\n"); if(location){ int count=0; printf("目标数字出现的位置:"); 21