数据结构实验八 快速排序实验报告

数据结构实验八 快速排序实验报告

数据结构实验课程最终报告

题 目:实验八快速排序

专业班级:计算机科学与技术

姓 名:XXX

学 号:

指导老师: 李晓鸿

完成日期:2015、01、06

数据结构实验八 快速排序实验报告

一、 需求分析

背景

排序就是计算机内经常进行的一种操作,其目的就是将一组“无序”的记录序列调整为“有序”的记录序列。

假设含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,求出让所有任务等待的时间与最小的任务处理顺序。 3. 输入输出要求 a) 输入要求:

第一行就是一个整数n,代表任务的件数。

接下来一行,有n个正整数,代表每件任务所用的时间。 b) 输出要求:

输出有n行,每行一个正整数,从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行,则使得所有任务等待时间最小。

4. 测试数据

1. 输入:

请输入任务件数:-1 输出:

数据结构实验八 快速排序实验报告

输入有误,请重新输入！ 2. 输入:

请输入任务件数:4

请输入各任务所需时间:2 4 3 0

输出:

输入有误,请重新输入！ 3. 输入:

请输入任务件数:4

请输入各任务所需时间:2 4 3 6 输出:

任务执行的先后顺序为:

2 3 4 6

4. 输入:

请输入任务件数:9

请输入各任务所需时间:5 3 4 2 6 1 5 7 3

输出:

任务执行的先后顺序为:

1 2 3 3 4 5 5 6 7

二、 概要设计

(一) 函数调用关系图