排序算法的分类:
插入排序:直接插入排序、希尔排序 交换排序:冒泡排序、快速排序 各种算法的比较
(1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序较好。 (2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。 (3) 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。 (4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于"比较"的排序算法,至少需要O(nlog2n)的时间。 (5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。 |
|