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

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