- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
快速排序(实验报告附C源码)
快速排序
问题描述
在操作系统中,我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做,任务也要操作系统一件件地处理。当操作系统处理一件任务时,其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低,但我们可以安排它们的处理顺序,将耗时少的任务先处理,耗时多的任务后处理,这样就可以使所有任务等待的时间和最小。
只需要将n 件任务按用时去从小到大排序,就可以得到任务依次的处理顺序。当有 n 件任务同时来临时,每件任务需要用时ni,求让所有任务等待的时间和最小的任务处理顺序。
需求分析
输入事件件数n,分别随机产生做完n件事所需要的时间;
对n件事所需的时间使用快速排序法,进行排序输出。排序时,要求轴值随机产生。
输入输出格式:
输入:
第一行是一个整数n,代表任务的件数。
接下来一行,有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把数组分成了两个子数组。分别对两个子数组,进行类似的操作,便能得到正确的排序结果。
程序的流程
输入事件件数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);//递归调用,对数组左右两部分进行排序
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个随机数
结果: //提示
正确的排序结果
测试结果
实验心得(可选)
这个实验,不难。但是关键在于理解快速排序的那个过程,如何根据轴值将数组分成两部分,然后将轴值放到合适的位置,继续对分成两部分的数组,执行类似的操作。
附录(实验源码)
#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;
cou
文档评论(0)