数据结构实验八：快速排序

几乎是满分,自己的报告

HUNANUNIVERSITY

课程实验报

告

题 目：快速排序

学生姓名

学生学号

专业班级 指导老师 李晓鸿 完 成 日 期 2 0 1 5年 1月 7日

几乎是满分,自己的报告

一、需求分析

1．程序的功能

由用户输入任务件数和任务时间，使用快速排序，输出使得所有任务等待时间最小的序列。

2.输入的形式

本程序由用户输入任务总数以及每个任务所花时间，中间用空格或换行隔开，任务总数必须为正整数。

请输入任务总数：

请输入各个任务所花时间：

3.输出形式

在对这些任务所花时间进行快速排序后，将这些数据从小到大输出任务时间。

任务所花时间的排序如下：

4.测试数据

1.请输入任务总数：

9

请输入各个任务所花时间：

5 3 4 2 6 1 5 7 3

任务所花时间从小到大的排序如下：

几乎是满分,自己的报告

123345567

2.请输入任务总数：

10

请输入各个任务所花时间：

6 5 1 2 3 5 4 8 6 1

任务所花时间从小到大的排序如下：

1 1 2 3 4 5 5 6 6 8

3.请输入任务总数：

6

请输入各个任务所花时间：

10 10 19 45 23 5

任务所花时间从小到大的排序如下：

5 10 10 19 23 45

4.请输入任务总数：

8

请输入各个任务所花时间：

8 7 6 5 4 3 2 1

任务所花时间从小到大的排序如下：

1 2 3 4 5 6 7 8

几乎是满分,自己的报告

5.请输入任务总数：

10

请输入各个任务所花时间：

2 4 6 8 1 0 12 14 26 15

任务所花时间从小到大的排序如下：

0 1 2 4 6 8 12 14 15 26

二、概要设计

1.抽象数据类型

将每一个元素储存在一个有序并且有限的序列中，每一个元素都有一个自己的位置，也都有一个数据类型，所以使用线性表来储存各个任务所花的时间。

2.ADT

ADT alist

{

数据对象：定义线性表的最大储存元素maxsize;

当前储存元素数listsize;

数据关系：若listsize=0,则线性表没有元素，为空;

基本操作：alist(int n)//构造函数

~alist()//析构函数

几乎是满分,自己的报告

bool append(int a)//增加元素

}

3.算法的基本思想

设要排序的线性表中元素是A[0]……A[N-1]，首先通过时间函数余作为关键数据piot，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，通过前后指针的移动，实现快速排序。再将piot值左右两边的线性表进行快速排序，直到需要快速排序的线性表只有1个元素。

4.程序基本流程

程序分为三个模块：

输入模块：由用户读入任务总数n以及各个任务所花时间； 排序模块：对这些时间进行快速排序；

输出模块：输出排序后的序列。

三．详细设计

1.物理数据类型

由于线性表长度已知，并且进行大量的交换操作，所以使用顺序表来实现。

顺序表的伪代码 class alist

{

几乎是满分,自己的报告

public:

int maxsize;

int listsize;

int* listarry;

alist(int n) {

maxsize = n; listsize = 0;

listarry = new int[maxsize];

}

~alist()

{

delete[]listarry;

}

bool append(int a)

{

if (listsize == maxsize)return false;

listarry[listsize++] = a;

return true;

}};

2.详细设计

获取piot值——partation——quicksort

获取piot值：获取随机数，通过随机数获得piot值。为了防止随机数大于所有数，对随机数就行求余，对求余后的值加1（防止左边界为0，右边界为1的情况，（r+l）/2==0）.

int findpiot(int a, int b)

{

srand(time(0));

int n = rand() % ((a+b)/2+1);

return n;

}

partation（划分）：开始参数l.r紧挨要分割子线性表的实际边界。每一轮执行外层do循环时，l和r都将向的线性表中间移动，若在移动过程中，l遇到比piot值大的值就停止，l遇到比piot小的就

几乎是满分,自己的报告

停止，交换l和r所对应的值，再次移动，直到它们交叉为止。 int partition(int l, int r, int &pivot)

{ do

{

while (listarry[++l]< pivot);

while ((r != 0) && (listarry[--r]> pivot));

swap( l, r);

} while (l < r);

swap( l, r);

return l;

}

quicksort（快速排序）：通过递归，获取piot值后，对线性表从位置i到位置j进行一次划分，通过k值获得排序后poit值所在位置，对起始位置i到k和k+1到末尾j再次快速排序。

void qsort( int i, int j) { if (j <= i) return; int pivotindex = findpiot( i, j); int k = partition(i - 1, j, listarry[j]); swap( k, j); qsort( i, k - 1); qsort( k + 1, j);

}

3．算法的时空分析及改进设想

最好情况O（nlogn），最差情况（n^2）

4.输入和输出的格式

输入：

输入任务数量，任务时间：

请输入任务数: .....

几乎是满分,自己的报告

请输入任务时间: ......

cout <<"输入任务数\n"; cin >> n;

alist a(n);

cout <<"输入任务时间\n";

for (int i = 0; i < n; i++)

{

cin >> temp;

a.append(temp);

}

输出：

任务所花时间排序如下：

.........

cout <<"任务所花时间排序如下\n";

for (int i = 0; i < n; i++)

cout << a.listarry[i] <<"";

cout << endl;

四．测试结果

测试1

几乎是满分,自己的报告

测试2

测试

3

几乎是满分,自己的报告

测试4

几乎是满分,自己的报告

测试5

五．试验心得

书上快速排序十分详细，用抽象数据类型做也就多了定义类。

六．附录 #include"iostream"

#include"time.h"

using namespace std;

class alist

{

public:

int maxsize;

int listsize;

int* listarry;

alist(int n)

{

maxsize = n;

listsize = 0;

listarry = new int[maxsize];

}

~alist()

{

delete[]listarry;

}

bool append(int a)

几乎是满分,自己的报告

{

if (listsize == maxsize)return false; listarry[listsize++] = a;

return true;

}

int findpiot(int a, int b)

{

srand(time(0));

int n = rand() % ((a+b)/2);

return n;

}

int partition(int l, int r, int &pivot)

{

do

{

while (listarry[++l]< pivot);

while ((r != 0) && (listarry[--r]> pivot)); swap( l, r);

} while (l < r);

swap( l, r);

return l;

}

void qsort( int i, int j)

{

if (j <= i)

return;

int pivotindex = findpiot( i, j);

int k = partition(i - 1, j, listarry[j]); swap( k, j);

qsort( i, k - 1);

qsort( k + 1, j);

}

void swap( int a, int b)

{

int temp;

temp = listarry[a];

listarry[a] = listarry[b];

listarry[b] = temp;

}

};

int main()

{

int n,temp;

几乎是满分,自己的报告

} cout <<"输入任务数\n"; cin >> n; alist a(n); cout <<"输入任务时间\n"; for (int i = 0; i < n; i++) { cin >> temp; a.append(temp); } cout << endl; a.qsort(0, n - 1); cout <<"任务所花时间排序如下\n"; for (int i = 0; i < n; i++) cout << a.listarry[i] <<""; cout << endl; system("pause"); return 0;

本文来源：https://www.bwwdw.com/article/nf5i.html