单向链表快速排序算法

J4 ›› 2014, Vol. 36 ›› Issue (01): 115-120.

单向链表快速排序算法

白宇,郭显娥

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

收稿日期:2012-05-28 修回日期:2012-09-26 出版日期:2014-01-25 发布日期:2014-01-25

QuickSort algorithm for singly linked list

BAI Yu,GUO Xiane

(School of Mathematics & Computer Science,Shanxi Datong University,Datong 037009,China)

Received:2012-05-28 Revised:2012-09-26 Online:2014-01-25 Published:2014-01-25

摘要/Abstract

摘要：

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

关键词: 单向链表, 快速排序, 原地排序, 分治策略

Abstract:

Singly linked list is widely used for the dynamic storage structure, the current singly linked list sorting algorithms generally have low efficiency, and the QuickSort algorithm with the highest 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 QuickSort algorithm for singly linked list. Its average time complexity is O(nlog2n), its auxiliary space complexity is O(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.

Key words: singly linked list;QuickSort;inplace sort;divide and conquer strategy

白宇,郭显娥. 单向链表快速排序算法[J]. J4, 2014, 36(01): 115-120.

BAI Yu,GUO Xiane. QuickSort algorithm for singly linked list [J]. J4, 2014, 36(01): 115-120.