快速排序(实验报告附c源码)

《快速排序(实验报告附c源码)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、快速排序一、问题描述在操作系统屮，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需耍等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的吋间和最小。只需要将n件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有n件任务同时来临时，每件任务需要用时n：，求让所有任务等待的时间和最小的任务处理顺序。二、需求分析1.输入事件件数n，分别随机产生做完n件事所需要的时间；2.对n件事所需的吋间使用快速排序法，进行排序

2、输出。排序吋，要求轴值随机产生。3.输入输出格式：输入：第一行是一个整数n,代表任务的件数。接下来一行，有n个正整数，代表每件任务所用的时间。输出：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。4.测试数据：输入9534261573输出123345567三、概要设计抽象数据类型因为此题不需要存储复杂的信息，故只需一个整型数组就nJ•以丫。算法的基本思想对一个给定的进行快速排序，首先需要选择一个轴值，假设输入的数组中冇k个小于轴值的数，于是这些数被放在数组最左边的k个位置上，而人于周知的结点被放在数组右边的n-

3、k个位置上。k也是轴值的下标。这样k把数组分成了两个子数组。分别对两个子数组，进行类似的操作，便能得到正确的排序结果。程序的流程输入事件件数n--＞随机产生做完没个事件所需时间--〉对n个时间进行排序一＞输出结果快速排序方法(因图难画，举一个实例)：72657888542r726578885421r672578885421r67257888542r172657888542r167257888542r1初始状态1第一趟循环第一次交换第二次交换反转交换第二趟循环这就是依靠轴值，将数组分成两部分的实例(特殊情况下，可能为一部分，其中42是轴值)。对分成的两部分数组，分别尽心类似的操作，便可得符合要

4、求的结果。快速排序的函数模块；voidqsort(int氺array,int1,intr){if(r＜=l)return;intpivotlndex=l+rand()%(r_l+l);//随机选定轴值swapl(array,pivotlndex,r);//将选定的轴值放到每段数组的最后intRepartition(array,1-1,r,array[r]);//依靠轴值，将数组分//成两部分swap1(array,k,r);//将轴值放到正确的位置上qsort(array,1,k_l);//递归调用，对数组左右两部分进行排序qsort(array,k+1,r);A将大于轴值的放右边，小于轴值

5、的放左边算法实现呤intpartition(int氺array,int1,intr,constintpivot)do{while(array[++1]

6、试结果五、实验心得（可选）这个实验，不难。但是关键在于理解快速排序的那个过程，如何根据轴值将数组分成两部分，然后将轴值放到合适的位罝，继续对分成两部分的数组，执行类似的操作。六、附录(实验源码)#include#includeusingnamespacestd;//产生n个随机数，存储到数组int*crtArray(int&size){intn;cin»n;//设罝随机种子srand(time(NULL));int*intArray=newint[nj;size=n;cout«"原始序列：n«endl;for(inti=0;i

7、;intArray[il=rand()%10;if(intArray[i]==0){i-；continue;}cout«intArray[i]«"M;}cout«endl;returnintArray;}//交换数组中的两个值voidswapl(int*array,int&a，int&b){inttemp=array[a];array[a]=array[b];array[b]=temp;}//对指定的数组部分