单向链表快速排序算法

• 作者: 白宇 郭显娥
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 单向链表 快速排序 原地排序 分治策略
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 算法研究
• 页码范围: 115-120
• 页数: 6页
• 分类号: TP311.12
• 字数: 4091字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2014.01.020

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭显娥	山西大同大学数学与计算机科学学院	20	146	7.0	11.0
2	白宇	山西大同大学数学与计算机科学学院	12	33	4.0	5.0