快速排序算法实验报告

在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，只需要将n件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有n件ni，求让所有任务等待的时间和最小的任务处理顺序。二、需求分析n，nn值随机产生。3.输入输出格式：n，接下来一行，有n输出有n用的时间。按此顺序进行，则使得所有任务等待时间最小。4.测试数据：输入53426157312334556kkn-k个位置上。k也是轴值的下标。这样k把数组分成了两个子数组。分别对两个子数组，输入事件件数n快速排序方法（因图难画，举一个实例）：初始状态72657888542lr循环72657888542lr第一次交换67257888542lr第二趟循环7257888542rl第二次交换72657888542r反转交换67257888542r这就是依靠轴值，将数组分成两部分的实例（42voidqsort(int*array,intl,intr){intpivotIndex=l+rand()%(r-l+1swap1(array,pivotIndex,r);//将选定的轴值放到每段数组的最后intk=partition(array,l-1,r,array[r]);//依靠轴值，将数组分//成两部分swap1(array,k,r)qsort(array,l,k-1);//递归调用，对数组左右两部分进行排序qsort(array,k+1,r);}/*将大于轴值的放右边，小于轴值的放左边算法实现*/intpartition(int*array,intl,intr,constintpivot){while((r!=0)&&(array[--r]>pivot));swap1(array,l,r);returnΘ(n2)，但很少出现这种情况。如果快速排序找到了Θ(nn)。n=原始序列：//提示随机产生的n四、测试结果五、实验心得（可选六、附录（实验源码#include<iostream>#include<ctime>usingnamespace//产生nint*crtArray(int&size){intn;cout<<"n=";cin>>n;srand(time(NULL));int*intArray=newint[n];size=n;cout<<"原始序列："<<endl;for(inti=0;i<n;i++){intArray[i]=rand()%10;if(intArray[i]==0){i--;continue;}cout<<<<"";cout<<endl;returnvoidswap1(int*array,int&a,int&b){inttemp=array[a];array[a]=array[b];array[b]=temp;}intpartition(int*array,intl,intr,constint{do{while(array[++l]<pivot);while((r!=0)&&(array[--r]>=pivot));swap1(array,l,r);}while(l<r);swap1(array,l,r);returnl;}voidqsort(int*array,intl,intr){if(r<=l)return;intpivotIndex=r;intk=partition(array,l-1,r,array[r]);swap1(array,k,r);qsort(array,l,k-1);qsort(array,k+1,r);}/*主函数*/intmain(){intsize;int*Array;Array=crtArray(size);qsort(Array,0,size-1);cout<<"结果："<<endl;for(inti=0;i<size;i++)cout<<Array[i]<<"";cout<<endl;return0;}姓名：XXX一、需求分析排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。假设含nR1,R2,?，Rn}其相应的关键字序列为{K1,K2,?，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：按此固有关系将上式记录序列重新排列为{Rp1,Rp2,?，Rpn排序算法是计算机科学中最重要的研究问题之一。对于排序的研究既有理论上的重要意义，领域具有广泛应用。常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速1：有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据支2：在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将各3：在一个由ni4：对一个含有nk在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，只需要将n件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有n件任务同时来临时，每件任务需要用时ni当有nni，求出让所有任务等待的时间和最小的n，接下来一行，有n输出有n请输入任务件数：-2.请输入任务件数3.请输入任务件数4.请输入任务件数6157(一)函数调用关系图intstart,intrandom(intstart,intend);voidchange(inta[],inti,intj);a[],int函数voidQuickSort(inta[],intend);start,intend);QuickSort(inta[],intstart,int（一）本程序所输入的任务件数和任务时间均为整数，可使用整数intcout<<"请输入任务件数:";while(size)//任务件数大于0，则执行该循环，否则重新输入件数{inti;cout<intrandom(intstart,intintsrand(time(NULL));//设置随机数种子，对多组数据排序时不会取相同的轴值returnt;voidchange(inta[N],inti,intintt;intPartition(inta[],intstart,intinttemp=random(start,end);//得到随机轴值inti=start-1;//iintbase=a[end];//以最后一个数作为划分的基点for(intj=start;j<end;j++)returni+1;voidQuickSort(inta[N],intstart,int电子科技大学学生姓名：学号：点名序号：指导教师：2014-2015-2学生姓名实验地点：基础实验大楼实验时间：520快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）I、J以第一个数组元素作为关键数据，赋值给X，即J（J：=J-1），XI（I：=I+1），X3、4I=J二分法查找（折半查找）min，low，highamid（R[mid].key）比较，若相等，则查找成功，如果R[mid].key>a，则由表的有序性可知，R[mid].keya，aR[mid].keyhigh=mid-1;如果R[mid].key<a,则等于aR[mid].key如果R[mid].key=a，下一次查找针对新的查找区间，重复步骤（1）和在查找过程中，lowhighhigh<low，则查找失败。实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地查找,并输出查询结果。PCC#defineMAX#defineFROMFILE1typedefstructJD{intkey;intbich(JDr[],intn,int{intlow,high,mid,found;low=1;high=n;found=0;{mid=(low+high)/2;if(k>r[mid].key)low=mid+1;elseif(k==r[mid].key)found=1;voidquicksort(JDr[],intlow,inthigh){inti,j,k;JDwhile((i<j)&&(r[j].key>=x.key))j--while((i<j)&&(r[i].key<=x.key))i++;if(i<j){r[j]=r[i];j--int#ifdefFROMFILEprintf("请输入你所要查找的数组长度:");intlength;JDinti;printf("输入第%di);FILE*fp;fp=fopen("test.txt","r");return0;JDinti=1;while(fscanf(fp,"%d",&a[i