白 宇，郭显娥

（山西大同大学数学与计算机科学学院，山西 大同037009）

1 引言

单向链表是一种典型的链式存储结构［1］，目前多使用 Two－way MergeSort算法［2］对单向链表进行排序，虽然Two－way MergeSort算法时间复杂度为 O （n log2n）［1～4］，但 其 空 间 复 杂 度 高 达O（n）［1～4］，在一些嵌入式系统研发中，由于对存储空间的使用数量有较严格的限制，故并不普遍适用。

排序算法中适应性最强且应用最广的是基于关键字比较的排序算法［1～4］，因为排序的本质就是按照一定规则相互比较关键字以确定其顺序，即关键字可比较是排序算法的充要条件［3］。而其它诸如基于哈希表的排序算法或基于对关键字运算的排序算法，由于对关键字有一些特殊要求，其应用相对较窄［4～6］。

在基于关键字比较的排序算法中，已证明时间复杂度最小可达O（nlog2n）［4～6］，其中应用最广泛的有QuickSort和HeapSort，HeapSort算法的常量因子较高［5，6］，QuickSort算法的实测平均性能最优［5，6］。但是，QuickSort算法最大不足之处在于，由于其基于可索引存储结构设计（一般为数组或索引表），因而无法用于链式存储结构［4］，而链式存储结构的实际应用非常广泛，例如动态存储管理、动态优先级调度等等。本文针对上述问题，以QuickSort的分治策略［1～6］为基础，提出一种可用于单向链表的QuickSort算法，其平均时间复杂度（包含最优及最差情况）为O（nlog2n），辅助空间复杂度为O（0），平均递归栈空间复杂度为O（log2n），从而实现了对链式存储结构高效排序的同时不增大空间复杂度。

2 算法分析

2.1 分治策略

QuickSort算法需要从线性表两端逐一选取元素与枢轴元素进行比较［1～6］，而单向链表只能从一个方向顺序访问，故无法做到；……