快速排序问题

《快速排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、HUNANUNIVERSITY题目快速排序问题学生姓名王家威学生学号201308070217专业班级智能科学与技术1302班指导老师朱宁波背景排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。假设含n个记录的序列为｛R1,R2,…,Rn｝其•相应的关键字序列为｛K1,K2,Kn｝这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kpl

2、有理论上的重要意义,又有实际应用价值。它在计算机阁形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。例1:有时候应用程序本身就耑要对信息进行排序。为了准备客户账目，银行耑要根据支票的号码对支票排序；例2:在一个绘制互相重脊的阁形对象的程序屮，可能需要根据一个“在上方”关系将各对象排序，以便自下而上地绘出对象。例3:在一个由n个数构成的集合上，求集合中第i小/大的数。例4:对一个含有n个元数的集合，求解屮位数、k分位数。问题描述在操作系统屮，我们总是希望以最短的

3、时间处理完所有的任务。但事情总是要一件件地做,任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理吋间不能降低，但我们可以安排它们的处理顺序，将耗吋少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。只需要将n件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有n件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。基本要求(1)数据的输入输出格式：输入：第一行是一个整数n,代表任务的件数。接下来一行，有n个正整数，代表每件任务所用的时间

4、。输出：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。(2)使用快速排序，轴值采用随机数确定。测试数据输入9534261573输出123345567代码如下：#include#include#include//pragmawarning(disable:4996)usingnamespacestd;intaa[110],bb[110];void_sort(intI,intr){if(I==rjreturn;i

5、ntmid=(I+r)/2;_sort(l,mid);_sort(mid+1,r);intp=I,q=mid+1;intcnt=0;for(;p<=mid&&q<=r;){if(aa[p]

6、(inti=0;i&按任意键继续•--