线性表的单向链表的排序的代码实现（python语言）

短命女 2022-05-24 04:06 183阅读 0赞

![70][]

注：代码中的cort就是表中的crt

def sort_m(self):  # 表元素排序（从小到大）
        if self.head is None:  # 将要排序的表为空则直接返回
            return
        cort = self.head.next  # cort赋为表的第二节点
        while cort is not None:  # cort不为空
            x = cort.elem  # x指向cort指向的节点的值
            p = self.elem  # p指向表头的elem指向的节点
            while p is not cort and p.elem <= x:  # 如果已排序片段的下一项比已排序片段的最后一个片段大，则p指向下一节点的
                p = p.next
            while p is not cort:  # p还在已排序片段
                y = p.elem  # p.elem和cort.elem交换（未排序片段的第一项小于已排序片段的话就交换）
                p.elem = x
                x = y
                p = p.next
            cort.elem = x  # 最后的回填
            cort = cort.next

![70 1][]

注：代码中的cort就是表中的crt

def sort(self):  # 表元素排序
        if self.head is None:  # 如果链表为空直接返回
            return
        last = self.head  # 初始，排序段只有一个节点
        cort = last.next
        while cort is not None:
            p = self.head  # 设置扫描指针初值
            q = None
            while p is not cort and p.elem <= cort.elem:
                q = p  # 顺序更新两个扫描指针
                p = p.next
            if p is cort:  # p是cort时不用修改链接，设置last到下一节点cort
                last = cort
            else:
                last.next = cort.next  # 取下当前节点
                cort.next = p  # 接好后的链接
                if q is None:
                    self.head = cort  # 作为新的首节点
                else:
                    q.next = cort  # 或者接在表中间
            cort = last.next  # 无论什么情况，cort总是last的下一个节点

[70]: /images/20220524/215ef004552e4070a38ff814e554d831.png
[70 1]: /images/20220524/a42e8dc74fd547be825579ac5e91373f.png