Skip to content

Latest commit

 

History

History
113 lines (108 loc) · 4.25 KB

2A.md

File metadata and controls

113 lines (108 loc) · 4.25 KB
Raw

链表的排序

有些时候我们也希望得到有序链表，那么还得排序。

归并排序

链表不能象数组那样随机访问，分割要多费周章。不过由于链表的归并不需要额外空间，归并排序可以做到O(1)级的空间开销。

func mergeSort[T constraints.Ordered](list *ll.Node[T]) (head, tail *ll.Node[T]) {
    head, tail = list, ll.FakeHead(&head)
    size := 0
    for ; list != nil; size += 2 {             //先探规模
        if list.Next == nil {
            tail = list
            size++
            break
        }
        a, b := list, list.Next
        list = b.Next
        if a.Val > b.Val {
            tail.Next, b.Next, a.Next = b, a, list
            tail = a
        } else {
            tail = b
    }   }
    for step := 2; step < size; step *= 2 {
        list, tail = head, ll.FakeHead(&head)
        for list != nil {
            lst1 := list
            lst2 := cut(lst1, step)             //切至多step大小的一段
            list = cut(lst2, step)              //切第二段
            var node *ll.Node[T]
            tail.Next, node = merge(lst1, lst2) //归并之
            tail, node.Next = node, list
    }   }
    return head, tail
}

因为先分割后归并，归并排序在每轮处理中需要遍历两次链表，在速度上稍逊于快速排序。

内省排序

随机三点取中法在链表中难以实现，链表上的快速排序更容易陷入最坏情况。使用内省排序比较合理。

func introSort[T constraints.Ordered](list *ll.Node[T], life uint) (head, tail *ll.Node[T]) {
    head, tail = sort2(list)
    if head == nil {
        if life == 0 {
            head, tail = mergeSort(list)        //召唤小伙伴
        } else {
            lst1, pivot, lst2, _ := partition(list)
            head, tail = introSort(lst1, life-1)
            tail.Next = pivot                   //前后衔接
            pivot.Next, tail = introSort(lst2, life-1)
    }   }
    return head, tail
}

基数排序

和归并排序的情况类似，基数排序在链表上的实现比在数组上的实现较为容易，也无需太多的额外的空间。

func RadixSort[T constraints.Integer](head *ll.Node[T]) *ll.Node[T] {
    //...
    const bk = 1 << 8
    parts, tails := new([bk]*ll.Node[T]), new([bk]*ll.Node[T])
    for step := uint(0); step < bitWidth; step += 8 {
        for i := 0; i < bk; i++ {
            parts[i] = nil
            tails[i] = ll.FakeHead(&parts[i])
        }
        for node := head; node != nil; node = node.Next {
            radix := uint8(node.Val >> step)
            tails[radix].Next, tails[radix] = node, node
        }
        tail := ll.FakeHead(&head)
        for i := 0; i < bk; i++ {
            if parts[i] != nil {
                tail.Next = parts[i]
                tail = tails[i]
        }   }
        tail.Next = nil
    }
    //...
    return head
}

性能分析

通过简单的评测，我们可以看出链表上排序性能比数组上的要差不少：

Benchmark_MergeSort-6            3267426           741.1 ns/op
Benchmark_QuickSort-6            4010521           549.4 ns/op
Benchmark_IntroSort-6            4172546           537.5 ns/op
Benchmark_RadixSort-6            4724077           488.3 ns/op
Benchmark_DescMergeSort-6       16931956            90.29 ns/op
Benchmark_DescQuickSort-6         296650        119665 ns/op
Benchmark_DescIntroSort-6        7884870           164.8 ns/op
Benchmark_DescRadixSort-6       11793471           142.9 ns/op
ok      DSGO/linkedlist/sort

Benchmark_MergeSort-6           14570674            88.89 ns/op
Benchmark_QuickSort-6           16693329            84.88 ns/op
Benchmark_IntroSort-6           16923432            85.57 ns/op
Benchmark_RadixSort-6           58933306            25.33 ns/op
Benchmark_DescMergeSort-6       58247337            26.43 ns/op
Benchmark_DescQuickSort-6       100000000           13.41 ns/op
Benchmark_DescIntroSort-6       100000000           15.42 ns/op
Benchmark_DescRadixSort-6       22972530            50.76 ns/op
ok      DSGO/array/sort

相对连续结构，链式结构在访问效率上存在劣势。即使在不需要随机访问的场合，链表还是无法完全取代数组。

目录　上一节　下一节