链表中的快排以及归并排序
发布时间
阅读量：
阅读量
链表快排
采用快速排序算法对单链表进行排序操作时，其核心在于partition函数的设计。由于单链表不具备反向遍历的能力，因此无法使用传统的头尾双指针相互靠近的partition方式，而需采用从链表头部出发的双指针实现方法，关于两种具体的partition函数实现方式可参考：快排的两种partition函数
相较于数组形式的快速排序，链表快排在partition函数中的差异主要体现在遍历终止条件以及递归终止条件的设定上。
# 链表快排
class Node:
def __init__(self, val):
self.val = val
self.next = None
def bulid_list(data_list):
head = Node(0)
cur = head
for val in data_list:
cur.next = Node(val)
cur = cur.next
return head.next
def print_list(root):
while root:
print(root.val)
root = root.next全部评论 (0)
还没有任何评论哟~