golang list sort

golang 的序列化容器有数组、slice 和 list,前两个是语言内置的,后一个是标准库提供的。用数组的场景并不多,因为其最大缺点是 —— 长度固定,所以我们更倾向于会动态增加长度的 slice 和 list。slice 底层是数组,所以是连续存储的结构;list 底层是链表,非连续存储结构。slice/list 相当于 java 中的 ArrayList/LinkedList ,或是 c++ 中的 vector/list。不同的储存结构结果就决定了它们的优缺点:

  • slice:特点:连续存储;优点:访问(第i个元素)方便,直接访问;缺点:删除和添加(第i个)元素不方便,需要大量移动数据;
  • list:特点:非连续存储;优点:删除和添加元素方便,不需要大量移动数据;缺点:访问(第i个元素)不方便,线性复杂度;

前面都是在说废话,现在入正题。排序算法很多:冒泡排序、希尔排序、堆排序、快速排序以及基数排序等。一般语言都提供快速排序 quicksort/qsort/sort 算法,其平均时间复杂度为 O(nlogn),采用的是递归分治的思想。关于快速排序可以看这篇文章

仔细研究你会发现,排序算法针对都是连续储存结构的数据,对 data[i] 和 data[j] 的访问都是线性的,否则时间复杂度就不是 O(nlogn) 了,而是 O(n2logn) 了。golang 对 slice 的排序可以看这篇文章。那么 golang 如何排序 list 呢?标准库没有提供相应的排序算法,╮(╯▽╰)╭

轮子造起。

思路

sort 只能用于 slice,那么对于 list 怎么办呢?运用转化思想,将 list 转换为 slice ,然后排序 slice, 最后将 slice 拷回 list。但是有个问题,如果是纯数据进行拷贝,那么算法 swap 的时候要频繁交换元素的值,代价会很大(当然本身数据拷贝代价也可能很大,不过是 O(n) 级的,而 swap 是 O(nlogn) 级的)。那么我们借助指针来避开 swap 真正的 value 值。

代码实现

  1. // sorted_list.go
  2. package sort_ext
  3.  
  4. import (
  5.         "container/list"
  6.         "sort"
  7. )
  8.  
  9. type sortedList struct {
  10.         list *list.List
  11.         data []*list.Element
  12.         cmp  func(a, b *interface{}) bool
  13. }
  14.  
  15. func (slist *sortedList) init() {
  16.         for ele := slist.list.Front(); ele != nil; ele = ele.Next() {
  17.                 slist.data = append(slist.data, ele)
  18.         }
  19. }
  20.  
  21. func (slist *sortedList) post() {
  22.         slist.list.Init()
  23.         for _, value := range slist.data {
  24.                 slist.list.PushBack(value.Value)
  25.         }
  26. }
  27.  
  28. func (slist sortedList) Len() int {
  29.         return len(slist.data)
  30. }
  31.  
  32. func (slist sortedList) Swap(i, j int) {
  33.         slist.data[i], slist.data[j] = slist.data[j], slist.data[i]
  34. }
  35.  
  36. func (slist sortedList) Less(i, j int) bool {
  37.         return slist.cmp(&slist.data[i].Value, &slist.data[j].Value)
  38. }
  39.  
  40. func SortList(data *list.List, cmp func(a, b *interface{}) bool) {
  41.         if data == nil {
  42.                 panic("error: input list is nil")
  43.         }
  44.         if cmp == nil {
  45.                 panic("error: cmp is nil")
  46.         }
  47.         var slist sortedList = sortedList{list: data, cmp: cmp}
  48.         slist.init()
  49.         sort.Sort(slist)
  50.         slist.post()
  51. }

上面 init() 函数来把 list 指针拷贝到 slice 中,然后排序之,最后 post() 函数再把 slice 的结果拷贝会 list 中去。需要注意的是:因为 list 不支持 Element* 的添加,所以最后的 post() 是把所有的 value 重新 PushBack 回 list, 这里有一个 O(n) 的数据拷贝。

SortList 的原型是:func SortList(data *list.List, func cmp(a,b *interface{})bool); 第一个参数是 list 指针;第二个参数是一个比较函数,通过两个元素指针来比较值的 < 关系。

测试代码

下面是使用 sort_ext.SortList 的一个 demo:

  1. package main
  2.  
  3. import (
  4.         "container/list"
  5.         "fmt"
  6.         "github.com/antark/list_ext"
  7. )
  8.  
  9. func main() {
  10.         var data list.List
  11.         var item uint64
  12.         for {
  13.                 _, err := fmt.Scan(&amp;item)
  14.                 if err != nil { // 遇到 EOF 则 err != nil
  15.                         break
  16.                 }
  17.                 data.PushBack(item)
  18.         }
  19.         sort_ext.SortList(&amp;data, func(a, b *interface{}) bool {
  20.                 return (*a).(uint64) &lt; (*b).(uint64)
  21.         })
  22.         for ele := data.Front(); ele != nil; ele = ele.Next() {
  23.                 fmt.Println(ele.Value) // ele.Value ==&gt; (*ele).Value
  24.         }
  25. }

Tags: 

Article type: