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

士不可以不弘毅，任重而道远。仁以为己任，不亦重乎?死而后已，不亦远乎?——《论语》

实验8快速排序

1．需求分析

（1）输入的形式和输入值的范围：

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

接下来一行，有n个正整数，代表每件任务所用的时间。中间用空格或者回车隔开。

不对非法输入做处理，及假设用户输入都是合法的。

（2）输出的形式：

输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的

任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。

（3）程序所能达到的功能：

在操作系统中，当有n件任务同时来临时，每件任务需要用时ni，输出所有任务

等待的时间和最小的任务处理顺序。

（4）测试数据：

输入

请输入任务个数：9

请输入任务用时：534261573

输出

任务执行的顺序：123345567

2．概要设计

（1）抽象数据类型的定义：

为实现上述程序的功能，应以整数存储用户的第一个输入。并将随后输入的一组数

据储存在整数数组中。

（2）算法的基本思想：

如果将任务按完成时间从小到大排序，则在完成前一项任务时后面任务等待的时间

总和最小，即得到最小的任务处理顺序。

采取对输入的任务时间进行快速排序的方法可以在相对较小的时间复杂度下得到

从小到大的顺序序列。

3．详细设计

（1）实现概要设计中定义的所有数据类型：

第一次输入的正整数要求大于零，为了能够存储，采用int型定义变量。

接下来输入的一组整数，数据范围大于零，为了排序需要，采用线性结构存储，即

int类型的数组。

（2）实现程序的具体步骤：

一.程序主要采取快速排序的方法处理无序数列：

1．在序列中根据随机数确定轴值，根据轴值将序列划分为比轴值小和比轴值

大的两个子序列。

1

士不可以不弘毅，任重而道远。仁以为己任，不亦重乎?死而后已，不亦远乎?——《论语》

2．对每个子序列采取从左右两边向中间有哪些信誉好的足球投注网站的方式，不断将值与轴值比较，

如果左边的值大于轴值而右边的小于轴值则将二者交换，直到左右交叉。

3．分别对处理完毕的两个子序列递归地采取1，2步的操作，直到子序列中只

有一个元素。

二.程序各模块的伪代码：

1、主函数

intmain()

{

intn;

请输入任务个数：请输入任务个数：

cinn;

inta[n];

请输入任务用时：请输入任务用时：

for(inti=0;in;i++)cina[i];

qsort(a,0,n-1);//调用“快排函数”

任务执行的顺序：任务执行的顺序：

for(inti=0;in;i++)for(inti=0;in;i++)//输出排序结果

}

2、快速排序算法：

voidqsort(inta