快速排序详析的设计-数据结构课程设计报告.doc

1、数据结构课程设计报告（ 2015） 数据结构课程设计报告 快速排序详析的设计 专业 计算机科学与技术 学生姓名 班级 学号 指导教师 完成日期 数据结构课程设计报告（ 2015） 目 录 1. 设计内容 - 1 1.1 排序基本知识 -1 1.2 快速排序算法介绍 -1 1.3 设计题目 -2 2. 设计分析 - 3 2.1 快速排序的分析 - 3 2.2 系统流程图设计 - 4 2.3 系统的详细设计 - 5 3. 设计实践 - 6 3.1 开发环境 - 6 3.2 快速排序过程 - 7 3.3 调试过程 - 8 3.4 代码实现 - 11 4. 测试方法 - 11 4.1 测试方案 - 1

2、5 4.2 测试结果 - 15 5. 程序运行效果 - 15 6. 设计心得 - 19 参考文献 - 20 数据结构课程设计报告（ 2015） 1 快速排序详析的设计 1. 设计内容 1.1 排序基本知识 排序（ Sorting）是计算机程序设计的一种重要操作，它的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。由于待排 序的记录数量不同，使得排序过程中涉及的存储器的不同，可将排序方法分为两大类：一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录

3、，在排序过程中尚需要对外在进行访问的排序过程。 内部排序的方法有很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。按照其策略不同，可归纳为五类：插入排序、交换排序、选择排序、归并排序和基数排序。 1.2 快速排序算法介绍 快速排 序就像它的名称所暗示的，是一种快速的分而治之的算法，平均时间复杂度为 O(nlog2n)。它的速度主要归功于一个非常紧凑并且高度化的内部循环。其基本算法 Quicksort(S)由以下四个步骤组成： (1)如果 S中的元素的数目为 0 或 1，则返回。 (2)选择 S中的任意一个元素 v， v 叫做支点 (P

4、ivot)。 (3)将 S- v（剩下的元素在 S中）分成两个分开的部分。 L= x属于 S- v|x=v 。 (4)依次返回 Quicksort(L)、 v 和 Quicksort(R)的结果。 基本的快速排序算法可以应用递归实现。关键的细节包括支点的选择如何分组。该算法允许把任何元素作为支点。支点把数组分为两组：小于支点的元素集和大于支点的元素集。 显然该算法成立，但是不清楚的是，为什么它比归并排序快。如同归并排序那样，快速排序递归地解决两个之间问题并需要线性的附加工作（第 3 步），不过，与递归排序不同，这两个子问题并不保证逐步具有相等的大小，这是个潜在的隐患。快速排序更快的原因在于，第

5、 3 步划分成两组实际上是在适当的位置进行，并且非常有效，它的高效不仅弥补了大小不等的递归的不足而且还超过了它。 这里 介绍的方法是大量分析和经验研究的结果，它代表实现快速排序的非常有效的方法，哪怕是对该方法最微小的偏差都可能引起意想不到的不良结果。 数据结构课程设计报告（ 2015） 2 1.3 设计题目 设计并实现一种快速排序 (Quicksort)的优化版本，并且比较在下列组合情况下算法的性能表现。 cutoff 值从 020。 cutoff 值的作用是只有当数组的长度小于等于这个值时，才使用另一种简单排序方法对其排序，否则使用 Quicksort 算法排序。 选定支点的方法分别是“第一

6、个元素”，“三个元素的中值”，“五个元素的中值”。 对上述的测试分别要采用顺序、 逆序、随机三种类型的输入文件。 输入文件中测试数组的大小可以从 1000 个数到 10000 个数不等。程序从input.txt 文件中读取输入，输出到 output.txt 文件。例如： input.txt 内容如下。 5 /*数字的个数 */ 5 4 3 2 1 /*数字用空格分开 */ /*两组测试中间空一行 */ 10 4 6 8 7 5 1 3 9 2 0 相应的 output.txt 内容如下。 Case number :1 Number of elements:5 1 2 3 4 5 Case nu

7、mber :2 Number of elements:10 0 1 2 3 4 5 6 7 8 9 程序的重点在于对每种组合情况下算法性能的比较。不同的运行时间要用图表表示出来，在图表中要区分由文件大小的不同而产生的差别。 数据结构课程设计报告（ 2015） 3 2. 设计分析 2.1 快速排序的分析 （ 1） 最好情况： 快速排序的最好情况是支点把集合分成两个同等大小的子集，并且在递归的每个阶段都这样划分。然后就有了两个一半大小的递归调用和线性的分组开销。在这种情况下运行的时 间复杂度是 O(nlog2n)。 （ 2） 最坏情况： 假设在每一步的递归调用中，支点都恰好是最小的元素。这样小元素

8、的集合 L就是空的，而大元素集合 R 拥有了除支点以外的所有元素。 设 T 是对 N 个元素进行快速排序所需的运行时间，并假设对 0或 1个元素排序的时间刚好是 1 个时间单位。那么对于 N1，当每次都运气很差地选择最小的元素作为支点，得到的运行时间满足 T(N)=T(N-1)+N。即对 N 个项进行排序的时间等于递归排序大元素子集中的 N-1个项所需要的时间加上进行分组的 N个单位的开销。最终得出： T(N)=T(1)+2+3+ +N=N(N+1)=O(N2) 2 （ 3） 支点的选择 错误方式：比较常见的不明智的选择就是把第一个元素作为支点。但如果输入是已经预先排过序的，或者是倒序的，该支

9、点给出的分组就很糟糕，因为它是一个末端的元素；而且这种情况会在迭代中继续出现，会以 O(N2)的时间复杂度而告终，所以选择第一个元素作为支点不是好的策略。 中位选择： 把中间元素，即待排序序列中中间位置元素，作为支点是合理的选择。当输入已经排过序时，这种选择在每次递归调用 中都会给出理想的支点。 中值划分： 在上述选择中使用中间值得作为支点可以消除非随机输入时出现的退化情况。但这是一种消极的选择，就是说仅仅试图避免一个坏的支点而并没有尝试选择一个更好的支点。中值划分是一种选择比平均情况更好的支点的尝试。在中值划分中，一种比较简单而有效的策略是选择待排序列的第一个、中间一个以及最后一个记录这 3

10、 个值的中值作为支点。同样道理，也可以从待排序列中等距离地选取 5 个值，并将这 5 个值的中值作为支点。 数据结构课程设计报告（ 2015） 4 2.2 系统流程图设计 基本的快速排序算法可以应用递归实现。关键的细节包括支点 的选择和如何分组。 该算法允许把任何元素作为支点。支点把数组分为两组：小于支点的元素集和大于支点的元素集。图 2-1 展示了一组数据进行快速排序的基本过程。 8 3 7 1 4 5 6 9 2 0 8 3 7 1 4 5 9 6 2 0 9 8 7 0 3 4 1 2 5 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 6 6 Quickso

11、rt Quicksort 图 2-1 系统流程图 分组 选择支点 数据结构课程设计报告（ 2015） 5 2.3 系统的详细设计 程序主要由 6部分组成，分别是： (1)程序入口 main 函数 ，从 input.txt 文件中读取数据，放 Array 数组中，在执行 QuickSort 函数之前用 clock 函数获取系统时 95F44stop 变量中。使用stop-start 获得 QuickSort 函数的执行时间。将运行时间和排序后的数组一起输入到 output.txt 文件中。关闭 input.txt 文件，关闭 output.txt 文件。 (2)Quicksort，快速排序算法的

12、实现部分， Quicksort 函数包括五个参数分别是数组的地址 Array，待排序的第一个元素在数组中的下标，待排序的最后一个元素在数组中的下标， cutoff（小于 cutoff 时使用另一种简单的方法进行排序），支点 median。 Quicksort 函数分为以下几个步骤： 1 确定数组的大小是否为 0或 1，若为 0 或 1 则直接退出函数排序未完成 。 2 判断支点 median 取值是否为 1， 3或 5，否则返回错误。 3 判断 cutoff 取值是否恰当。 4 用 median 函数获得支点。 5 在分别设定指针 low 和 high 指向数组第一个和最后一个元素。 6 通过

13、 low+和 high-的方式让 low 和 high 向中间移动直到 Arraylow大于median 或 Arrayhigh小于 median。 7 判断 low 是否小于 high，若不小于，则交换 Arraylow与 Arrayhigh的值，否则跳出循环排序语句。 8 将原数组分成两部分后分别用 Quicksort 函数处理两个数组。 Quicksort 函数排序是一个将数组以 median 为分界分成一个元素都小于 median 的数组和一个元素都大于 median 的数组。再将这两个数组用 Quicksort 函数处理的递归调用过程。 (3)MedianOf3,选择三个值的中值作为

14、支点； (4)MedianOf5,选择五个值的中值作为支点； (5)Swap,简单地交换两个元素的值； (6)InsertionSort，在数组长度小于 cutoff 值时使用插入排序来代替快速排序。 下面描述 main 和 Quicksort 两个函数的基本算法的运算过程。 main函 数： 打开 input.txt 和 output.txt 文件； 读入数的个数 n; 从文件中顺序读入 n 个数，并放到数组中； 应用 Quicksort 对该数组排序； 将排序后的数输出到文件 output.txt 中； 读入下一个数组的个数，继续上述过程； 关闭文件。 Quicksort 函数： 数据结构

15、课程设计报告（ 2015） 6 参数：待排数组，待排段的起点位置，待排段的终点位置， cutoff 值，支点选择方法 If 数组是空的 Exit If 待排数段的元素个数大于等于 cutoff 值，且元素个数大于等于支点选择方法所要求的元素个数 根据支点选择方法选择一个元素作为 支点 设置 low 为起点值、 high 为终点值 While low=high While low 位置的值小于支点值 low+ While high 位置的值大于支点值 high- If lowhigh 交换 low、 high 两个元素 将 low 位置的元素与支点元素交换 Quicksort 递归调用左半段 Q

16、uicksort 递归调用右半段 Else 应用直接插入排序法对数组元素排序 3. 设计实践 3.1 开发 环境 Microsoft Visual C+ 6.0 Microsoft Visual C+，（简称 Visual C+、 MSVC、 VC+或 VC）是 Microsoft公司推出的开发 Win32 环境程序， 面向对象 的可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持 数据库接口 、OLE2， WinSock 网络、 3D 控制界面。 它以拥有“ 语法高亮 ”， In

17、telliSense（自动完成功能）以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及建置系统以 预编译头 文件、最小重建功能及累加连结著称。这些特征明显缩短程式编辑、编译及连结花费的时间，在大型软件计划上尤其显著。 数据结构课程设计报告（ 2015） 7 3.2 快速排序过程 在待排序的 n各记录中任取一条记录（通常去第一条记录），把它作为基准元素，确定该条记录的最终位置，即该条记录左边的记录的所有记录的关键字的值均小于该记录，右边的所有记录的关键字的值均大于等于该记录。待排序序列以基准元素为界

18、限被分割成两个区域，这个过程称作一次快速排序。之后对所有的区间分别重复上述过程，直至每个区间只有一条记录为止。快速排序是一个递归过程，整个排序过程对不同的区间进行快速排序。 假设要排序的数组是 A1 AN，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然 后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 设置两个变量 I、 J，排序开始的时候 I： =1， J： =N； 以第一个数组元素作为关键数据，赋值给 X ，即 X ：=A1； 从 J 开始向前搜索，即由后开始向前搜索（ J： =J-1），找到第一个小于 X 的值，两者交

19、换； 从 I 开始向后搜索，即由前开始向后搜索（ I： =I+1），找到第一个大于 X 的值，两者交换； 重复第 3、 4 步，直到 I=J； 【事例模范】 例：将数据（ 45， 53， 18， 36， 72， 30， 48， 93， 15， 36）进行快速排序。 快速排序的一次划分过程 如下所示： 【 45 53 18 36 72 30 48 93 15 36】移动比较 【 36 53 18 36 72 30 48 93 15 45】交换位置并比较 【 36 45 18 36 72 30 48 93 15 53】交换位置并比较 【 36 15 18 36 72 30 48 93 45 53】

20、交换位置并比较 【 36 15 18 36 45 30 48 93 72 53】交换位置并比较 【 36 15 18 36 30 45 48 93 72 53】交换位置 ,i=j 【 36 15 18 36 30】 45【 48 93 72 53】一趟排序的结果 i j i i i i i j j j j j 数据结构课程设计报告（ 2015） 8 一次完整的快速排序的排序过程（待排序区间以中括号括起来） 如下所示： 【 45 53 18 36 72 30 48 93 15 36】 【 30 36 18 36 15】 45【 48 93 72 53】 【 18 15】 30【 36 36】 4

21、5【 48 93 72 53】 15 18 30 【 36】【 36】 45【 48 93 72 53】 15 18 30 36 36 45 【 48 93 72 53】 15 18 30 36 36 45 48 【 93 72 53】 15 18 30 36 36 45 48 【 53 72】 93 15 18 30 36 36 45 48 53 72 93 3.3 调试过程 1. 启动 VC 启动 VC 的前提是首先要安装 VC 软件。如果你的系统安装了 VC软件，当你启动了 Windows 系统之后，从 “ 开始 ” 菜单进入 “ 所有程序 ” 子菜单，找到 Microsoft Visual C+ 6.0 并单击它 即进入 VC 软件的主窗口，如图 3-3-1所示： 2编辑程序 若要在 VC窗口下进行 C程序的编辑，首先，单击工具栏的 New Text File 按钮，生成一个新的文本文件窗口，如图所示；接着，单击 Save 按钮，激活 “ 保存为 ” 对话框，在指定的文件夹下，输入当前程序的文件名（注意：文件名必须给出 .C的扩展名），再按 “ 保存 ” 按钮。到此为止，在指定的目录下，就生成了一个由读者自己命名的 C 文件（比如 main.C），接下来，就可以进入编辑屏幕输入你的 C 源程序了。 图 3-3-1