import random

def generate_data(): """生成n个0~100的随机整数链表""" n = 10 nodes = [] head = -1 for i in range(n): nodes.append([random.randint(0, 100), -1]) if i == 0: head = i else: nodes[i-1][1] = i return head, nodes

def print_list(head, nodes): """打印链表中的所有值（顺序）""" if head == -1: print("空链表") return cur = head vals = [] while cur != -1: vals.append(str(nodes[cur][0])) cur = nodes[cur][1] print(" -> ".join(vals))

def louis_sixteen_sort(head, nodes): """路易十六排序（降序）""" if head == -1 or nodes[head][1] == -1: return head pre=nodes[head][1] cur=nodes[pre][1] while cur!=-1: pre=cur,cur=nodes[pre][1]#要放到最后 if nodes[cur][0]>nodes[pre][0]: cut=2*nodes[cut][0]//3 if cut<nodes[pre][0]: now=head while now!=cur: if cut<nodes[now][0] and cut>nodes[nodes[now][1]][0]: # 需在最后加入now的迭代 after=now while after!=cur: after=nodes[after][1] a=nodes[nodes[after][1]][0] nodes[nodes[after][1]][0]=nodes[after][0] #实现插入

                    nodes[nodes[now][1]][0]=cut
                    





return head

生成初始数据

head, nodes = generate_data() print("原始链表（随机顺序）：") print_list(head, nodes)

执行排序

sorted_head = louis_sixteen_sort(head, nodes) print("\n排序后链表（降序）：") print_list(sorted_head, nodes)