数据结构课程设计(快速排序).docxVIP

数据结构课程设计 PAGE \* MERGEFORMAT PAGE \* MERGEFORMAT 1 数据结构课程设计报告 快速排序详析 专业 物联网工程 学生姓名 方振华 班级 152 学号 1510706205 指导教师 刘 骞 完成日期 2016年12月22日  目 录 TOC \o 1-5 \h \z \u HYPERLINK \l _Toc21020 一、简介 1 HYPERLINK \l _Toc6375 二、算法说明 1 HYPERLINK \l _Toc22401 三、测试结果 7 HYPERLINK \l _Toc2422 四、分析与探讨 9 HYPERLINK \l _Toc30272 五、数据异常测试案例 15 HYPERLINK \l _Toc1046 六、小结 17 HYPERLINK \l _Toc2406 七、参考文献 18 HYPERLINK \l _Toc10922 八、源程序清单 18  快速排序详析 简介 排序是计算机程序设计中常用的数据处理操作。经过一学期数据结构的学习，我们学到很多种排序方法，如插入排序、交换排序、选择排序、归并排序、技术排序等。经过分析与对比，我们总结出一种快速排序的优化版本，并对其设计思想和具体实现进行详解。 算法说明 1、各种排序算法方法性能比较 图1：各种排序算法方法性能比较 （1）就时间性能而言，快速排序，堆排序和归并排序都有较好的时间性能。相对而言，快速排序速度最快，不过快速排序在最坏情况下，时间性能达到了O（n^2），不如堆排序和归并排序快。 （2）就空间性能而言，直接插入排序，冒泡排序，简单选择排序，堆排序要求的辅助空间比较小。其中直接插入排序，冒泡排序，简单选择排序比较简单，容易实现，但时间性能较差。 快速排序是一种有效的排序算法。虽然算法在最坏的情况下运行时O(n^2)，但由于平均运行时间为O（nlogn），并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法，其基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键词比另一部分记录的关键词小，则可分别对这两部分记录进行排序，以达到整个序列有序。 2、步骤 快速排序基本算法Quicksort(S)由以下4个步骤组成： (1).如果S中的元素数目为0或一，则返回。 (2).选择S中的任意一个元素v,v叫做支点(Pivot)。 (3).将S-{v}(剩下的元素在S中)分成两个分开的部分。所有小于v的元素和所有大于v的元素。 (4).依次返回Quicksort(L)，v和Quicksort的结果 基本的快速排序算法可以应用递归实现，关键的细节包括支点的选取和如何分组。该算法允许把任何元素作为支点。支点把数组分为两组，图2展示了算法的基本过程。 图2：算法基本过程 3、分析 最好情况： 快速排序的最好情况是支点把集合分成两个同等大小的子集并且在递归的每个阶段都这样划分。然后就有了两个一般大小的递归调用和线性的分组开销。在这种情况下运行的时间复杂度是O（nlog2n）。 最坏情况： 假设在每一步的递归调用中支点都恰好是最小的元素。这样小元素的集合L就是空的而大元素集合R拥有除了支点以外的所有元素。 设T（N）是对N各元素惊醒快速排序所需的运行时间按并假设对0或1各元 素排序的时间刚好是1个时间单位。那么对由于N》1当每次都运气很差地最 小的元素作为支点得到的原型时间满足T（N）=T(N-1)+N.即对N各项进行排 序的时间等于递归排序大元素子集中的N-1各项所需要的时间加上进行分组的 N个单位的开销。最终得出T（N）=T(1)+2+3+…+N=N(N+1)/2=O(N^2) 支点选择： 错误方式：比较常见的不明智的选择就是把第一个元素作为支点。但如果输入是已经预先排过序的，或者是倒序的，该支点给出的分组就很糟，因为它是一个末端的元素；而且这种情况会在迭代中继续出现，会以O(N^2)的时间复杂度而告终，所以选择第一个元素作为支点不是好的策略。 中位选择： 把中间元素即待排序序列中间位置的元素作为支点是合理的选择。当输入已经排过序时这种选择在每次递归调用中都会给出理想的支点。 中值划分： 在上诉选择中使用中间值作为支点可以消除非随机输入时出现的退化情况。但这是一种消极的选择，就是说仅仅是试图避免一个坏的支点而并没有去尝试选择一个更好的支点。中值划分是一种选择比平均情况更好的支点的尝试。在中值划分中，一种比较简单而有效的策略是选择待排序列的第一个、中间一个以及最好一个记录这3个值的中值