内部排序算法的性能分析
10 / 36
? 定义静态全局变量无符号整形timeuse统计每次调用排序函数的时间消
耗
? 定义比较宏每次比较自动统计比较次数（一次）,详见表2 ? 定义SWAP宏每次交换自动统计移动次数（三次）,详见表2 ? 定义MOV宏每次移动自动统计移动次数（一次）,详见表2
4 详细设计
4.1直接排序
1） 基本思想[4]
每次都将序列中待排数据插入到之前已经有序的序列中的某个位
置，使新序列依然保持有序。可以从序列的第二个关键字开始，与第一个关键字比较大小决定顺序再取第三个关键字继续和已经有序的第一、 二个关键字比较，以此类推。直至整个序列有序。 2） 性能分析[4]
直接插入排序算法简单， 容易实现。程序有两层循环嵌套，每个待
排数据都要和前面有序的数据作比较，故时间复杂度为O (n2) ；要用到 1个额外存储空间来交换数据。 3） 程序测试
图5 直接插入算法演示
10
内部排序算法的性能分析
11 / 36
4.2起泡排序
1） 基本思想[4]
一个最简单的交换排序方法是起泡排序法，它和气泡从水中往上冒
的情况有些类似。 其具体做法是：对1至n个记录，先将第n个和第n-1个记录的键值进行比较，如：r[n].key < r[n-1].key，则将两个记录交换。 然后比较第n-1个和第n -2个记录的关键字；依次类推，直到第2个记录和第1个记录进行比较交换，这称为一趟冒泡。这一趟最明显的效果是：将键值最小的记录传到了第 1位。然后，对2至n个记录进行同样操作，则具有次小键值记录被安置在第2位上。 重复以上过程，每次的移动都向最终排序的目标前进，直至没有记录需要交换为止。 2） 性能分析[4]
冒泡排序属于简单的排序，时问性能为 0(n2) ，占用 1个额外的存
储空间。 3） 程序测试
图6 起泡排序算法演示
4.3选择排序
1） 基本思想[4]
每一趟从待排序数据元素中选出关键字最小的一个元素，与第一个
元素交换位置， 在其余的元素中再找到一个最小的交换到第二个位置，
11
内部排序算法的性能分析
12 / 36
直到全部待排序的数据元素排完。 2） 性能分析[4]
简单选择排序只需 1个额外空间作为交换元素的中间变量；算法由
两层循环嵌套构成，时间复杂度为O(n2) 。 3） 程序测试
图7 简单选择算法演示
4.4快速排序
1） 基本思想[5]
它是冒泡排序的改进算法，基于分治策略。通过一趟排序将待排记
录分割成独立的两部分，其中一部分记录关键字均比另一部分记录关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 2） 性能分析[5]
若初始记录序列按关键字有序或基本有序时， 快速排序将蜕化为冒
泡排序， 这是最坏的情况。当每次都能将序列恰好分成两个相等序列时， 出现了快速排序的最佳情况， 此时n个关键需要做log2n趟排序，在每一趟中所有划分关键字的和是n。时间复杂度为O(n2) 3） 程序测试
12
内部排序算法的性能分析
13 / 36
图8 快速排序算法演示
4.5希尔排序
1） 基本思想[2]
先将整个待排序记录序列分割成为若干个子序列分别进行直接插入
排序，待整个序列中记录“基本有序”时，再对全体记录进行一次直接插入排序 2） 性能分析[2]
当增量序列为dlta[k] = 2 ^ (t-k+1) -1,1<=k<=t<=[log2(n+1)]时，时间复
杂度为O(n3/2) 3） 程序测试
图9 希尔排序演示
4.6堆排序
1） 基本思想[2]
先将初始文件建成一个大根堆， 此堆为初始的无序区；再选得一个
13
内部排序算法的性能分析
14 / 36
关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1 个记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 2） 性能分析
由于它在直接选择排序的基础上利用了比较结果形成， 效率提高很
[2]
大。时间复杂度为O(nlog2n)。 3） 程序测试
图10 堆排序算法演示
4.7总结和实现
? 如表 3所示，对六种排序算法的总结对比
表3 六种排序算法性能对比
排序方法 插入排序 起泡排序 选择排序 快速排序 希尔排序 堆排序 平均时间 O ( n2 / 4 ) O ( n2 ) O ( n2 ) O ( n log n) O ( n2 ) O ( n log n) 最坏情况 O ( n2 ) O ( n2 ) O ( n2 ) O ( n log n) O ( n2 ) O ( n log n) 辅助存储 O(1) O(1) O(1) O (log n) O (1) O (1) ? 详见附件《程序清单》
14