单向链表快速排序算法

QuickSort algorithm for singly linked list

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。

Singly linked list is widely used for the dynamic storage structure, the current singlylinked list sorting algorithms generally have low efficiency, and the QuickSort algorithm with the high- est average efficiency is inapplicable to singly linked list. Based on the divide and conquer strategy and the recursive method, through re-linking the nodes of singly linked list, the paper proposes the Quick- Sort algorithm for singly linked list. Its average time complexity is O（nlog2n）, its auxiliary space com- plexity is 0（0）, and its average space complexity of recursion stack is O（log2n）. Algorithm analysis and experimental testing are conducted. The results show that its efficiency improves greatly over the other singly linked list sorting algorithms and more traditional QuickSort algorithm based on linear array. We can conclude that the proposed algorithm solves the inefficient problem on singly linked list sorting.