一种基于有序双端链表的高效排序算法 |
| |
作者姓名: | 谭 林 廖光忠 |
| |
作者单位: | 武汉科技大学计算机科学与技术学院,湖北 武汉,430065,武汉科技大学智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉,430065 |
| |
基金项目: | 国家自然科学基金资助项目(60803160);湖北省自然科学基金重点资助项目(2009CDA136,2009CDA034);湖北省教育厅科学研究计划项目(Q20101110,D2009110). |
| |
摘 要: | 本文提出一种新的基于有序双端链表的比较排序算法,即ODListsort(ordered double-end linked list sort)算法。该算法首先要定义一个可共存的链表最大数量,然后通过生成链表、根据规则插入数据以及合并操作来对数据集进行排序。在ODListsort算法中,数据元素是以链表形式进行动态内存分配的,因此它比一些经典的排序算法性能更优。实验结果表明,对于随机数据集,ODListsort排序与快速排序的速度接近,比归并排序、选择排序、插入排序以及冒泡排序的速度更快;对于有序数据集,ODListsort排序的效率远超快速排序,略高于归并排序。
|
关 键 词: | 排序算法 链表 快速排序 归并排序 时间复杂度 |
An efficient sorting algorithm based on ordered double-end linked list |
| |
Authors: | Tan Lin and Liao Guangzhong |
| |
Institution: | College of Computer Science and Technology,Wuhan University of Science and Technology, Wuhan 430065,China and Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System, Wuhan University of Science and Technology, Wuhan 430065,China |
| |
Abstract: | |
| |
Keywords: | sorting algorithm linked list quick sort merge sort time complexity |
本文献已被 CNKI 等数据库收录! |
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |
|