排序方法综述及其性能演示平台设计--软件工程本科生毕业论文.docx

本科生毕业论文（设计）

题　　目
排序方法综述及其性能演示平台设计

姓　　名
学号

院　　系
信息科学与工程学院

专　　业
软件工程

指导教师
职称 副教授

2016 年 5 月 20 日
教务处制

目 录
摘要 1
关键词 1
Abstract 1
Key Words 1
引言 1
1 研究背景与内容 2
1.1 研究背景 2
1.2 本文内容 2
2 基本内部排序方法 2
2.1 冒泡排序 2
2.1.1 基本原理 2
2.1.2 核心代码 2
2.1.3 举例演示 3
2.1.4 性能分析 3
2.2 快速排序 3
2.2.1 基本原理 3
2.2.2 核心代码 3
2.2.3 举例演示 3
2.2.4 性能分析 4
2.3 直接插入排序 4
2.3.1 基本原理 4
2.3.2 核心代码 4
2.3.3 举例演示 4
2.3.4 性能分析 4
2.4 希尔排序 5
2.4.1 基本原理 5
2.4.2 核心代码 5
2.4.3 举例演示 5
2.4.4 性能分析 5
2.5 简单选择排序 5
2.5.1 基本原理 5
2.5.2 核心代码 6
2.5.3 举例演示 6
2.5.4 性能分析 6
2.6 堆排序 6
2.6.1 基本原理 6
2.6.2 核心代码 6
2.6.3 举例演示 7
2.6.4 性能分析 8
3 算法性能对比 8
3.1 时间性能对比 8
3.1.1 时间复杂度分析 8
3.1.2 示例性能测试 9
3.1.3 极端情况下算法性能对比 10
3.2 算法稳定性对比 11
3.3 空间性能对比 12
3.4 演示平台设计 12
结论 13
致谢 14
参考文献 14
附录 15

II

排序方法综述及其性能演示平台设计
摘要：数据结构是计算机专业中的一门基础专业课程，而排序算法则是数据结构课程中研究的基本课题之一，其目的是方便记录的查找、插入和删除。本文介绍了几种基本的排序算法，并利用多组规模不同的测试数据进行测试，从而可以从具体的运行时间上对多种排序算法进行客观的性能比较。从样例数据测试结果得知，在不同的情况下，不同的排序算法在性能上有很大的差异。在某一种数据环境中性能表现出色的算法很可能在另一种数据环境中效率变得较低。而这种差异性说明，不存在绝对完美的排序算法，要根据实际的应用环境选择最为合适的排序算法，或者对某一大规模数据先后使用多种不同的算法进行处理，以达到优势互补，效率最大化。
关键词：排序 性能 测试
Sorting Algorithm Summary and Performance Demonstration Platform Design
Abstract: 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 doesn’t 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 < temp.length - i; j++) {
if (temp[j] > temp[j + 1]) {
int t = temp[j + 1];
temp[j + 1] = temp[j];
temp[j] = 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 96
2.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 = array[left];
//轴值元素取数组第一个元素
while (left < right) {
while (left < right && array[right] >= center)
right--;
if (left < right) {
array[left] = array[right];
left++;
}
while (left < right && array[left] <= center)
left++;
if (left < right) {
array[right] = array[left];
right--;
}
}
array[left] = 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) 96
2.2.4 性能分析
快速排序的时间主要花费在划分操作上，对长度为k的区间进行划分，共需要k-1次关键字的比较。
在最好情况下，每次划分所取得轴值都是当前无序区的“中值”元素，划分的结果是轴值的左、右两个无序子区间的长度大致相等，此种情况下时间复杂度为O(nlogn)。
最坏情况下，每次划分所选取的基准都是当前无序区中关键字最小（或）最大的元素，划分的结果是轴值左边的无序子区间为空（或右边的无序子区间为空），而划分所得的另一个非空的子区间中元素数目仅仅比划分前无序区间中元素个数少一个，此种情况下时间复杂度为O(n2)。
平均情况下快速排序依然是基于关键字比较的内部排序算法中最快的，平均时间复杂度为O(nlog2n)。
2.3 直接插入排序
2.3.1 基本原理
直接插入排序是一种相对较简单的排序方法。它的基本原理是：每次将一个待排序元素按其关键字大小直接插入到一个已经排好序的有序序列中，直至元素全部插入完成为止[5]。
2.3.2 核心代码
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
// 0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
int temp = array[i];
int k = i - 1;
for (int j = k; j >= 0 && temp < array[j]; j--) {
array[j + 1] = array[j];
k--;
}
array[k + 1] = temp;
}
}
2.3.3 举例演示
初始记录：48 37 64 96 75 12（设从小到大排列）
第一趟： 37 48
第二趟： 37 48 64
第三趟： 37 48 64 96
第四趟： 37 48 64 75 96
第五趟： 12 37 48 64 75 96
2.3.4 性能分析
在直接插入排序执行过程中，在寻找待插入元素在数组中位置时，需要遍历数组元素。为了防数组下标越界要在每一次插入过程中检查数组下标，这无疑十分浪费时间。因此引入哨兵元素并赋值与待插入元素相同，将其放置在数组头节点，这样就可以节省每一次前移都要检查下标的操作，大大提高算法的时间效率。
直接插入排序算法十分简洁，容易实现。主要的时间花费在查找关键字位置和移动后续元素上。
最好情况下，待排序元素已经是正序排列时，所花费比较次数和移动次数最少，每趟仅需比较一次即可找到待插入位置。此时时间复杂度为O(n)。
最坏情况下，待排序元素为逆序排列，每一次插入都要移动至数组起始位置，总的比较次数为：(n+2)*(n-1)/2。此时时间复杂度为O(n2)。
取以上两种情况综合分析，直接插入排序平均时间复杂度为O(n2)。
2.4 希尔排序
2.4.1 基本原理
希尔排序是插入排序的一种，又称缩小增量排序，也是直接插入排序的改进版。其基本原理是：先取一个小于n的整数s1作为第一个增量，将全部待排序元素中所有相隔距离为s1的倍数的元素放在同一组中，在每一组内部进行直接插入排序；然后取第二个小于s1的增量s2，再将待排序数组划分为更多个小序列，然后重复进行插入排序。重复进行分组与排序过程，直至所取增量s=1时，即每一个元素都是一个独立的组，进行最后一趟直接插入排序，算法结束[6]。
2.4.2 核心代码
int gap = list.length / 2;
while (1 <= gap) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for (int i = gap; i < list.length; i++) {
int j = 0;
int temp = list[i]; // 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
gap = gap / 2; // 减小增量
}
2.4.3 举例演示
初始记录：48 37 64 96 75 12（设从小到大排列）
第一趟： (48 96) (37 75) (12 64)
第二趟： (12 37 48) (64 75 96)
第三趟： 12 37 48 64 75 96
2.4.4 性能分析
希尔排序没有快速排序算法快，在中等规模数据下表现良好但不适用于规模非常大的数据。希尔排序算法在最坏情况和平均情况执行效率相似。希尔排序的时间复杂度与增量选取的序列有关，而描述所取增量序列的函数涉及到一些数学上尚未解决的难题，因此计算关键字的比较次数与元素移动次数和增量序列选择之间的关系，并给出完整的数学证明至今仍无法实现。只有针对特定的排序序列才能准确计算出其时间复杂度。
总体而言，希尔排序时间复杂度在O(nlog2n)和O(n2)之间。
2.5 简单选择排序
2.5.1 基本原理
选择排序是一种简单直观的排序算法。其基本原理是每一次从待排序元素中选取出最小（或最大）元素，取出的元素不是待排序序列的第一个元素，那么将其与待排序序列第一个元素交换。然后从余下的n-1个元素中再取出关键字最小的元素，重复上述过程直至所有元素均有序[7]。
2.5.2 核心代码
for (int i = 0; i < list.length - 1; i++) {
int temp = 0;
int index = i; // 用来保存最小值得索引
for (int j = i + 1; j < list.length; j++) {//寻找第i小的数值
if (list[index] > list[j]) {
index = j;
}
}
//元素插入
temp = list[index];
list[index] = list[i];
list[i] = temp;
}
2.5.3 举例演示
初始记录：48 37 64 96 75 12（设从小到大排列）
第一趟： 12 37 48 64 96 75
第二趟： 12 37 48 64 96 75
第三趟： 12 37 48 64 96 75
第四趟： 12 37 48 64 96 75
第五趟： 12 37 48 64 75 96
第六趟： 12 37 48 64 75 96
2.5.4 性能分析
简单选择排序的比较次数与初始序列无关。而当待排序序列为正数时移动次数最少，为0次；当待排序序列为逆序是移动次数最多，为3n*(n-1)/2次。
综上所述，简单选择排序的时间复杂度为O(n2)。
2.6 堆排序
2.6.1 基本原理
堆排序是利用堆（假设利用大根堆）的特性进行排序的方法[8]。其基本思想是：首先将待排序记录构造成一个大根堆，根据堆的相关特性，堆顶元素即为当前记录中关键字最大元素。然后将堆顶记录移走，并将剩余的记录再调整成大根堆。重复此过程直至堆中只有一个元素为止。取出元素的序列即为递增序列。
2.6.2 核心代码
private static void maxHeapify(int[] data, int heapSize, int index) {
// 当前点与左右子节点比较
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int largest = index;
if (left < heapSize && data[index] < data[left]) {
largest = left;
}
if (right < heapSize && data[largest] < data[right]) {
largest = right;
}
// 得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
if (largest != index) {
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
maxHeapify(data, heapSize, largest);
}
}
private static void heapsort(int[] data) {
// 末尾与头交换，交换后调整最大堆
for (int i = data.length - 1; i > 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
2.6.3 举例演示
初始记录：48 37 64 96 75 12（建立小根堆）

图2.1 初始化堆

图2.2 调整64

图2.3 调整37

图2.4 调整48

图2.5 调整结束（小根堆已建立）
第六步：取出堆顶元素12，放入已有序数组中。将64放入堆顶，并重新调整小根堆。待调整结束后重复上述操作直至堆中仅剩一个元素，将其取出并放入已有序数组队尾，排序结束。
2.6.4 性能分析
堆排序只需要一个元素的辅助空间，对于待排序元素个数较多时很有效。堆排序主要的运行时间消耗在初始建堆和重建堆时进行的反复筛选上。堆排序对待排序记录的排列状态不敏感。初始建堆需要O(n)时间，第i次取堆顶记录重建堆需要用O(log2i)时间，并且需要取n-1次堆顶元素。因此堆排序的时间复杂度为O(nlog2n)。
3 算法性能对比
3.1 时间性能对比
3.1.1 时间复杂度分析

从整体上看，快速排序无疑是效率最高、时间最短的排序算法。但是快速排序在最坏情况下时间性能不如堆排序。在序列较小且基本有序时，直接插入排序拥有最快速的执行时间。各种排序算法的时间性能对比如下表所示。
表3.1 六种排序时间性能对比
类别
排序算法
时间复杂度
平均情况
最好情况
最差情况
交换排序
冒泡排序
O(n2)
O(n)
O(n2)
快速排序
O(nlog2n)
O(nlog2n)
O(n2)
插入排序
直接插入排序
O(n2)
O(n)
O(n2)
希尔排序
O(nlog2n)至O(n2)之间
选择排序
简单选择排序
O(n2)
O(n2)
O(n2)
堆排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
3.1.2 示例性能测试
通过使用随机函数生成数列并分别传递给各个算法，并计算排序时间来进行量化的时间性能对比评价。测试分别使用10个数据、50个数据、100个数据、1000个数据以及10000个数据对所有算法进行测试，统一进行从小到大的递增排序。因算法执行时间较短，无法以秒为单位进行计时，故程序统一使用微秒（μs）作为时间计量单位。
表3.2 数据规模为10的测试数据表
排序方法
运行时间（单位：μs）
冒泡排序
2
快速排序
5
直接插入排序
1
希尔排序
2
简单选择排序
2
堆排序
11
表3.3 数据规模为50的测试数据表
排序方法
运行时间（单位：μs）
冒泡排序
40
快速排序
16
直接插入排序
16
希尔排序
14
简单选择排序
24
堆排序
47
表3.4 数据规模为100的测试数据表
排序方法
运行时间（单位：μs）
冒泡排序
171
快速排序
35
直接插入排序
51
希尔排序
32
简单选择排序
100
堆排序
99

表3.5 数据规模为1000的测试数据表
排序方法
运行时间（单位：μs）
冒泡排序
6364
快速排序
443
直接插入排序
5381
希尔排序
458
简单选择排序
9094
堆排序
2058
表3.6 数据规模为10000的数据测试表
排序方法
运行时间（单位：μs）
冒泡排序
1638945
快速排序
16673
直接插入排序
498943
希尔排序
8004
简单选择排序
760164
堆排序
134961
从各项图表中可以直观的看出，冒泡排序算法在数据规模较小时有着比较不错的时间性能，而当数据规模开始成倍增长时，冒泡排序的运算时间也近乎是成倍增长，因此冒泡排序并不适合大规模数据。究其原因主要是冒牌排序相对较简单的算法思想。在规模较小时效率尚可，无法与其他算法体现出明显的差异。当数据量达到一定规模时，算法的先天不足便体现出来了，大量的重复比较及交换浪费了太多的时间，导致效率表现一般。
而快速排序作为冒泡排序的改进算法，在各项规模的测试中可以明显的看到其排序思想的优越性。在应对大量数据时快速排序与冒泡排序甚至可以出现一个数量级的时间差距。这说明无论是面对大量数据还是小规模数据快速排序都是一个不错的选择。
与快速排序同样出色的还有希尔排序。目前希尔排序的时间复杂度尚无法准确计算，如果可以找到一个最佳增量序列，希尔排序的执行时间必定还会有很大的提升空间。
堆排序由于需要先进行建堆操作，因此算法较为复杂，所以在数据量较小时，堆排序为这六种算法中最慢的。因为堆排序算法花费大量时间在进行大根堆（或小根堆）的维护，面对较少的数据时显得太为复杂。在一定量规模以上堆排序的时间效率逐步提高。因此堆排序更适合处理大量数据排序以及优先级队列相关问题。根据堆排序在各种情况下的时间复杂度来看，其算法效率十分稳定，在特殊情况下会超过快速排序。
3.1.3 极端情况下算法性能对比
实际应用中无法预先预知具体的待排序数据特点，而有可能会出现待排序数列已经是正序排列或逆序排列的情况。在这种极端情况下部分算法的排序效率会发生明显变化，一些算法甚至会退化成为另一种算法。
表3.7 数据规模为50的正序测试数据
排序方法
运行时间（单位：μs）
冒泡排序
1
快速排序
26
直接插入排序
1
希尔排序
8
简单选择排序
23
堆排序
49
表3.8 数据规模为1000的正序测试数据
排序方法
运行时间（单位：μs）
冒泡排序
21
快速排序
6096
直接插入排序
18
希尔排序
294
简单选择排序
8804
堆排序
1686
从测试数据中可以看到，在正序情况下，冒泡排序和直接插入排序速度最快。数据正序时，冒泡排序仅仅进行一趟比较就结束排序，不发生任何交换。
直接插入排序在处理正序数列时，每一趟仅需比较一个关键字即可找到插入位置，因此执行速度较快。冒泡排序和直接插入排序在正序情况下时间复杂度仅为O(n)。
正序时时间性能最差的为快速排序和简单选择排序，时间复杂度为O(n2)。而对于堆排序（以大根堆为例）来说，虽然正序数列对其有利，但算法仍然需要花费大量时间用于建立和维护堆的形态，造成其时间性能表现一般。
表3.9 数据规模为50的逆序测试数据、
排序方法
运行时间（单位：μs）
冒泡排序
51
快速排序
30
直接插入排序
29
希尔排序
11
简单选择排序
24
堆排序
40
表3.10 数据规模为1000的逆序测试数据
排序方法
运行时间（单位：μs）
冒泡排序
6754
快速排序
5763
直接插入排序
5539
希尔排序
406
简单选择排序
9438
堆排序
1576
从逆序序列的测试数据中可以看到，在正序下速度最快的冒泡排序和直接插入排序的速度有较大程度的下滑。而快速排序效率依然很低。因为在数据基本有序的情况下，快速排序将退化为冒泡排序，造成其时间复杂度为O(n2)。而希尔排序作为直接插入排序的一种改进，只要数据基本有序便可达到最佳性能。
综上所述，同一排序算法在不同的情况下其时间性能可能会发生较大幅度的变化。
3.2 算法稳定性对比
算法的稳定性是指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则该算法称为不稳定的。
从排序稳定性上看，上述六种排序算法稳定性对比如下表。

表3.11 六种排序算法稳定性对比
类别
排序算法
稳定性
交换排序
冒泡排序
稳定
快速排序
不稳定
插入排序
直接插入排序
稳定
希尔排序
不稳定
选择排序
简单选择排序
不稳定
堆排序
不稳定
3.3 空间性能对比
从算法运行时占用的空间来看，上述六种排序算法的空间性能对比如下表：
表3.12 六种排序算法空间性能对比
类别
排序算法
空间复杂度
交换排序
冒泡排序
O(1)
快速排序
O(nlog2n)
插入排序
直接插入排序
O(1)
希尔排序
O(1)
选择排序
简单选择排序
O(1)
堆排序
O(1)
3.4 演示平台设计

图3.1 软件平台准备就绪

图3.2 数据规模为10时运行结果

图3.3 数据规模为50时运行结果
结论
综合文中所有测试数据，可以看出堆排序算法的选择并没有统一的标准，在排序序列不同的情况下上述几种排序算法表现出了不同的时间性能，每种算法都有其优缺点，要从待排序数列的的特点以及占用空间和稳定性的多方面进行评估。
一般来说，冒泡排序算法最为简单易懂，结构单一，在数据规模较小时有着较为不错的时间性能，但是并不适合于大规模数据的情况；快速排序在一般情况下有着最为出色的排序效率，不失为一种最佳选择方案，但是在数据序列基本有序时快速排序将退化为冒泡排序，而且当数据规模十分巨大时快速排序将消耗过多的内存空间从而十分容易发生堆栈溢出；直接插入排序和希尔排序同属插入排序，直接插入排序并不适合处理大规模数据，希尔排序作为直接插入排序的改进相对比较容易实现而且其最坏情况与平均情况下的时间复杂度相差无几，因此特别适合对原始数据进行初步排序；简单选择排序和冒泡排序性能类似，同样不适合大规模数据；堆排序借助堆的特性来进行待排序数据的储存，由于不需要大量的递归或者多维数组，因此堆排序尤其适合数据规模特别大时的数据处理，同时由于其稳定的性能表现，堆排序在极端情况下同样有着良好的时间性能。
本演示平台基本实现了所需的功能，通过大量的不同测试数据来分析相对应的排序算法的时间性能。整个演示平台设计的过程严格按照软件工程[9]标准进行，整个开发过程增强了软件开发中的工程意识和设计能力，并且在开发过程中显著的提高了动手能力。
软件依然有诸多不足之处，比如随机数列[10]的处理仍然不够精细，希尔排序中对增量序列的选取并非最佳，由于开发平台限制无法产生更大规模的数据进行测试等。希望在以后的学习中可以陆续得到改进。
致谢
本课题是在老师的热切关心和耐心指导下完成的。在论文编写的过程中，老师给与了细致以及耐心的指导，提出了很多宝贵的意见与建议。老师渊博的知识和严谨的求学态度我受益匪浅。在老师的帮助下，软件设计与开发过程中的难题与疑惑被逐一攻破，使我得以顺利地完成毕业论文。在此再次向老师表示感谢。
感谢我的同学在论文编写过程中给与的帮助与支持，正是由于他们的帮助才使得软件功能细节得以完善，在此向他们表示深深的谢意。
感谢大学四年来所有授课于我老师，没有老师们的无私奉献与耐心讲授，我不会获得这些年的知识积淀，更不会有足够的能力完成这篇论文。
最后向在百忙之中抽时间对本文进行评审的各位老师表示衷心的感谢！
由于作者水平和经验所限，文章中难免出现各种错误和纰漏，还请各位老师给与批评指正，必悉心改正。
参考文献
[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].清华大学出版社，2012:5.
[2] Mark AIlen Weiss.数据结构与算法分析：Java语言描述[M].2版.机械工业出版社,2009:7.
[3] 杨晓波,庞双双,张龙辉,张林.冒泡排序可视化的设计与实现[D].咸阳：西藏民族学院，2013:4
[4] 汤亚玲, 秦锋. 高效快速排序算法研究[J]. 计算机工程, 2011, 37(6): 17-20
[5] 李晶. 直接插入排序算法分析与实现[J]. 中国科技信息, 2007, (24): 2-3
[6] 杨智明. 希尔排序算法实现与分析[J]. 电脑编程技巧与维护, 2010, (2): 7-9
[7] 柴文慧. 选择排序法和冒泡排序法的解析与探讨[N]. 湖北函授大学学报, 2013(26)
[8] 冯广慧，陈守孔.从n个元素中选取前k(k(《)n)个元素的排序方法[D].珠海：吉林大学珠海学院，2014:13.
[9] 张海藩. 软件工程导论 (第六版) [M]. 清华大学出版社，2013:65-66.
[10] Daniel Liang. Java语言程序设计（第十版）[M].戴开宇,译.机械工业出版社，2015:13.

附录
MainProgram.java
package Sort;
public class MainProgram {
public static void main(String[] args) {
new GUI();
}
}

GUI.java
package Sort;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class GUI implements ActionListener {
JFrame frame = new JFrame("排序算法性能演示平台");
JPanel panel = new JPanel();
JButton btn = new JButton("开始测试");
JTextArea sort_result = new JTextArea();
JTextArea sort1 = new JTextArea("冒泡排序");
JTextArea sort2 = new JTextArea("快速排序");
JTextArea sort3 = new JTextArea("插入排序");
JTextArea sort4 = new JTextArea("希尔排序");
JTextArea sort5 = new JTextArea("选择排序");
JTextArea sort6 = new JTextArea("堆排序");
JTextArea sort1_result = new JTe