一种基于有序双端链表的高效排序算法

An efficient sorting algorithm based on ordered double-end linked list

本文提出一种新的基于有序双端链表的比较排序算法,即ODListsort(ordered double-end linked list sort)算法。该算法首先要定义一个可共存的链表最大数量,然后通过生成链表、根据规则插入数据以及合并操作来对数据集进行排序。在ODListsort算法中,数据元素是以链表形式进行动态内存分配的,因此它比一些经典的排序算法性能更优。实验结果表明,对于随机数据集,ODListsort排序与快速排序的速度接近,比归并排序、选择排序、插入排序以及冒泡排序的速度更快;对于有序数据集,ODListsort排序的效率远超快速排序,略高于归并排序。

This paper puts forward a new comparative sorting algorithm based on ordered double-end linked list,namely ODListsort algorithm.It first defines the maximum number of coexisting linked lists,then sorts the data set by generating lists,inserting data according to the rule and merging operation.In ODListsort algorithm,computer memories are dynamically allocated to data elements in the form of linked list,so it＇s more efficient than some classic sorting algorithms.Experimental results show that,for the random data sets,ODListsort is very close to quick sort and superior to merge sort,selection sort,insertion sort and bubble sort in speed;for the ordered data sets,the efficiency of ODListsort is obviously higher than that of quick sort,slightly higher than that of merge sort.