数据结构课程设计报告快速排序详析
专业
学生姓名班级学号指导教师完成日期
物联网工程方振华152
1510706205刘骞
2016年12月22日
f目录
一、简介1二、算法说明1三、测试结果7四、分析与探讨9五、数据异常测试案例15六、小结17七、参考文献18八、源程序清单18
241
f快速排序详析
一、简介
排序是计算机程序设计中常用的数据处理操作。经过一学期数据结构的学习，我们学到很多种排序方法，如插入排序、交换排序、选择排序、归并排序、技术排序等。经过分析与对比，我们总结出一种快速排序的优化版本，并对其设计思想和具体实现进行详解。
二、算法说明
1、各种排序算法方法性能比较
图1：各种排序算法方法性能比较（1）就时间性能而言，快速排序，堆排序和归并排序都有较好的时间性能。相对而言，快速排序速度最快，不过快速排序在最坏情况下，时间性能达到了O（
2），不如堆排序和归并排序快。（2）就空间性能而言，直接插入排序，冒泡排序，简单选择排序，堆排序要求的辅助空间比较小。其中直接插入排序，冒泡排序，简单选择排序比较简单，容易实现，但时间性能较差。快速排序是一种有效的排序算法。虽然算法在最坏的情况下运行时O
2，但由于平均运行时间为O（
log
），并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是
341
f最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法，其基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键词比另一部分记录的关键词小，则可分别对这两部分记录进行排序，以达到整个序列有序。2、步骤
快速排序基本算法QuicksortS由以下4个步骤组成：1如果S中的元素数目为0或一，则返回。2选择S中的任意一个元素vv叫做支点Pivot。3将Sv剩下的元素在S中分成两个分开的部分。所有小于v的元素和所有大于v的元素。4依次返回QuicksortL，v和Quicksort的结果基本的快速排序算法可以应用递归实现，关键的细节包括支点的选取和如何分组。该算法允许把任何元素作为支点。支点把数组分为两组，图2展示了算法的基本过程。
441
f541
r