本科生毕业论文（设计）题目 排序方法综述及其性能演示平台设计 姓名 学号 院系 信息科学与工程学院 专业 软件工程 指导教师 职称 副教授 2016 年 5 月 20 日教务处制目 录摘要1关键词1Abstract1Key Words1引言11 研究背景与内容21.1 研究背景21.2 本文内容22 基本内部排序方法22.1 冒泡排序22.1.1 基本原理22.1.2 核心代码22.1.3 举例演示32.1.4 性能分析32.2 快速排序32.2.1 基本原理32.2.2 核心代码32.2.3 举例演示32.2.4 性能分析42.3 直接插入排序42.3.1 基本原理42.3.2 核心代码42.3.3 举例演示42.3.4 性能分析42.4 希尔排序52.4.1 基本原理52.4.2 核心代码52.4.3 举例演示52.4.4 性能分析52.5 简单选择排序52.5.1 基本原理52.5.2 核心代码62.5.3 举例演示62.5.4 性能分析62.6 堆排序62.6.1 基本原理62.6.2 核心代码62.6.3 举例演示72.6.4 性能分析83 算法性能对比83.1 时间性能对比83.1.1 时间复杂度分析83.1.2 示例性能测试93.1.3 极端情况下算法性能对比103.2 算法稳定性对比113.3 空间性能对比123.4 演示平台设计12结论13致谢14参考文献14附录15II排序方法综述及其性能演示平台设计摘要：数据结构是计算机专业中的一门基础专业课程，而排序算法则是数据结构课程中研究的基本课题之一，其目的是方便记录的查找、插入和删除。本文介绍了几种基本的排序算法，并利用多组规模不同的测试数据进行测试，从而可以从具体的运行时间上对多种排序算法进行客观的性能比较。从样例数据测试结果得知，在不同的情况下，不同的排序算法在性能上有很大的差异。在某一种数据环境中性能表现出色的算法很可能在另一种数据环境中效率变得较低。而这种差异性说明，不存在绝对完美的排序算法，要根据实际的应用环境选择最为合适的排序算法，或者对某一大规模数据先后使用多种不同的算法进行处理，以达到优势互补，效率最大化。关键词：排序 性能 测试Sorting Algorithm Summary and Performance Demonstration Platform DesignAbstract: Data Structures is a basic professional course in computer science, and sorting algorithm is one of the basic project in the study of data structures, its purpose is to facilitate the record search, insert and delete. The article describes several basic sorting algorithm and use of several different sizes data for testing, so that we can make an objective performance comparison of several sorting algorithms from specific run-time. We can learn from the test result of the sample data that in different environment, different sorting algorithms shows a vary widely difference in performance. An algorithm which have excellent performance in a particular data environment maybe have a worse effectiveness in another data environment. And this difference explained that doesnt exist the absolutely perfect algorithm, and should choose the best appropriate algorithm based on the actual application environment, or using several different algorithms for processing against a large scale data in order to have the maximum efficiency.Key Words: sort; performance; test引言排序1是计算机科学中研究的基本课题之一。在不同的情况下，比如数据正序或逆序，不同排序算法的时间性能、比较次数、交换次数有很大差异。在选择排序算法2时，只能根据实际情况以及约束条件来确定。1 研究背景与内容1.1 研究背景排序算法在计算机软件开发中应用十分广泛，同时也是计算机专业课程教学中十分重要的一个组成部分。在日常生活、工作中接触到的计算机软件大多都与排序有着密不可分的联系。例如：教师需要对某个班级全体学生的成绩进行排序，从而更清楚地知晓每位同学进步与否；在图像处理软件中，程序要确定多个图层之间的层叠顺序从而确保得到正确的渲染结果；购物网站要对顾客提出的价格区间进行快速准确地排序并呈现在页面上。因此，排序在计算机程序中无处不在。然而排序算法自最早提出至今已经发展多年，不同的排序算法层出不穷。在现实生活中，不同的排序算法去处理同一组数据会产生非常明显的性能差异。因此深入研究排序算法的原理对开发高效率程序有着十分重要的意义，也是任何程序员算法入门的基础。通过对排序算法的性能分析一方面有助于加深对各个排序算法的理解，另一方面有助于开发者在不同的环境下选择不同的排序算法以获得最佳性能1.2 本文内容本文主要研究几种基本的排序算法的时间性能和执行次数。几种基本的排序算法主要包括冒泡排序3、快速排序4、直接插入排序5、希尔排序6、简单选择排序7和堆排序8。其中冒泡排序和快速排序属于交换类排序，直接插入排序和希尔排序属于选择类排序，简单选择排序和堆排序属于插入类排序。第一节主要叙述了关于排序算法的实际应用意义以及研究比较不同排序算法间性能差异的重要性。第二节分别论述了几种排序算法的核心思想以及执行原理，通过一组相同的示例数据来简单演示算法的执行过程，并对其进行时间性能的分析。第三节主要进行多重排序算法间的性能比较，主要从测试得到的数据来进行论证，包括算法执行时间以及交换次数。并通过设置特殊数据（递增数列和递减数列）来比较不同的算法在极端条件下时间性能，从而可以得到较为全面的算法分析。附录主要包括程序源代码。2 基本内部排序方法2.1 冒泡排序2.1.1 基本原理算法从数据前部开始，将相邻的数据进行两两比较，按照从大到小或者从小到大的顺序进行交换3。针对所有元素重复此步骤直至最后一个元素。此时一趟排序完成，最后一个元素为数据中的最大值（或最小值）。然后再从第一个元素开始重复进行上面的步骤，直到一趟排序中没有任何元素发生交换，此时排序结束。2.1.2 核心代码for (int i = 1; i temp.length; i+) for (int j = 0; j tempj + 1) int t = tempj + 1;tempj + 1 = tempj;tempj = t;2.1.3 举例演示初始记录：48 37 64 96 75 12（设从小到大排列）第一趟： 37 48 64 75 12 96第二趟： 37 48 64 12 75 96第三趟： 37 48 12 64 75 96第四趟： 37 12 48 64 75 96第五趟： 12 37 48 64 75 962.1.4 性能分析最好情况：待排序数据为正序排列，此时仅需一趟比较，不发生元素交换。最坏情况：待排序数据为逆序排列，此时算法需要n-1趟排序，共比较n*(n-1)/2次，取平均值的时间复杂度为O(n2)。2.2 快速排序2.2.1 基本原理快速排序算法是对冒泡排序的一种改进4。首先任意选取一个元素（通常选用数组第一个元素）作为轴值元素，第一趟排序将记录分割为两个相对独立的部分，其中一部分中所有元素都比轴值元素小，另一部分中所有元素都比轴值元素大。取两个指针low和high分别指向分割后每一部分的第一个元素和最后一个元素，设置轴值为pivot。第二趟排序时，对上述分割后的两部分元素重复第一趟排序的操作。重复此过程直至low=high结束。2.2.2 核心代码int center = arrayleft;/轴值元素取数组第一个元素while (left right) while (left = center)right-;if (left right) arrayleft = arrayright;left+;while (left right & arrayleft = center)left+;if (left right) arrayright = arrayleft;right-;arrayleft = center;2.2.3 举例演示初始记录：48 37 64 96 75 12（设从小到大排列）第一趟： (12 37) 48 (96 75 64)第二趟： (12) 37 48 (64 75) 96第三趟： 12 37 48 64 (75) 962.2.4 性能分析快速排序的时间主要花费在划分操作上，对长度为k的区间进行划分，共需要k-1次关键字的比较。在最好情况下，每次划分所取得轴值都