排序性能分析(3)

课设 排序性能分析

前 言

排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，主要分为插入排序（如直接插入排序、折半插入排序、表插入排序、希尔排序）、交换排序（如冒泡排序、快速排序）、选择排序（如简单选择排序、树形选择排序、堆排序）、归并排序（如二路归并排序）、基数排序五种类型。一般情况下，排序时间省和占用空间少的要求很难两全。因此，很难说那一种算法好。在评价内排序算法的时间复杂性的优劣时，通常采用最坏情况下和平均情况下的代价加以衡量。由于内排序的算法所耗费的时间与结点或记录的初始分布情况是相关的，因此仅仅考虑在最坏情况下的时间代价是不全面的。通常假定结点或记录的各种分布情况都是等可能出现的，用平均情况下的时间代价衡量算法的好坏将更加客观。每一种方法都有各自的优缺点，适合在不同的环境下使用。

这几种排序算法是在顺序存储结构上实现的，因此在排序过程中需要进行大量记录的移动。当记录很大时，时间耗费很大，此时可采用静态链表作存储结构。但是有的排序方法，无法实现表排序。在这种情况下可以进行地址排序，即另设一个地址向量指示相应记录。