v1.0 可编辑可修改
数据结构实验课程最终报告
题 目：实验八快速排序
专业班级：计算机科学与技术
姓 名：XXX
学 号：
指导老师： 李晓鸿
一、 完成日期：需求分析
背景
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
1
v1.0 可编辑可修改 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn }
这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …，Rpn }的操作称作排序。
排序算法是计算机科学中最重要的研究问题之一。对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。
例1：有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据支票的号码对支票排序；
例2：在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将各对象排序，以便自下而上地绘出对象。
例3：在一个由n个数构成的集合上，求集合中第i小/大的数。 例4：对一个含有n个元数的集合，求解中位数、k分位数。
1. 问题描述
在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。
只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。 2. 程序要求实现的功能
当有 n 件任务同时来临时，每件任务需要用时ni，求出让所有任务等待的时
2
v1.0 可编辑可修改 间和最小的任务处理顺序。 3. 输入输出要求 a) 输入要求：
第一行是一个整数n，代表任务的件数。
接下来一行，有n个正整数，代表每件任务所用的时间。 b) 输出要求：
输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。
4. 测试数据
1. 输入：
请输入任务件数：-1 输出：
输入有误，请重新输入！ 2. 输入：
请输入任务件数：4
请输入各任务所需时间：2 4 3 0
输出：
输入有误，请重新输入！ 3. 输入：
请输入任务件数：4
请输入各任务所需时间：2 4 3 6 输出：
任务执行的先后顺序为：
2 3 4 3
v1.0 可编辑可修改 6
4. 输入：
请输入任务件数：9
请输入各任务所需时间：5 3 4 2 6 1 5 7 3
输出：
任务执行的先后顺序为：
1 2 3 3 4 5 5 6 7
二、 概要设计
(一) 函数调用关系图
4
v1.0 可编辑可修改 int
int
Partition(int
start,int
random(int
start,int end) ;
主函
void QuickSort(int a[],int
start,int
a[],int
void change(int a[],int i,int j);
void QuickSort(int a[],int start,int
三、 详细设计
（一）物理数据类型
本程序所输入的任务件数和任务时间均为整数，可使用整数 int实现数据的存储。使用数组实现快速排序。
(二)具体步骤和伪代码 1. 输入任务件数及任务时长 while(1) {
cout<<\请输入任务件数: \
5
cin>>size;
while(size) //任务件数大于0，则执行该循环，否则重新输入件数 {
int i;
cout<<\请输入各任务所需时间:\ for(i=0;i cin>>a[i];
数据结构实验八 快速排序实验报告
