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

一．问题描述

在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。

只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。

二．基本要求

（1）数据的输入输出格式：

输入：

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

接下来一行，有n个正整数，代表每件任务所用的时间。

输出：

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

（2）使用快速排序，轴值采用随机数确定。

三．算法，数据结构

算法步骤为：

从数列中挑出一个元素，称为 "轴值"，

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割操作。

递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

数据结构：

function quicksort(q)

var list less, pivotList, greater

if length(q) ≤ 1 {

return q

} else {

select a pivot value pivot from q

for each x in q except the pivot element

if x < pivot then add x to less

if x ≥ pivot then add x to greater

add pivot to pivotList

return concatenate(quicksort(less), pivotList, quicksort(greater))