Comments

Golang 排序

Interface 接口

Go 语言标准库提供了排序的package sort,也实现了对 intfloat64string 三种基础类型的排序接口。所有排序调用 sort.Sort,内部根据排序数据个数自动切换排序算法(堆排、快排、插排)。下面这段代码出自 Go 标准库 sort/sort.go:

func quickSort(data Interface, a, b, maxDepth int) {
    for b-a > 7 {
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        maxDepth--
        mlo, mhi := doPivot(data, a, b)
        // Avoiding recursion on the larger subproblem guarantees
        // a stack depth of at most lg(b-a).
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }
    if b-a > 1 {
        insertionSort(data, a, b)
    }
}

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
    n := data.Len()
    maxDepth := 0
    for i := n; i > 0; i >>= 1 {
        maxDepth++
    }
    maxDepth *= 2
    quickSort(data, 0, n, maxDepth)
}

这里不详细探讨排序算法的实现和性能细节,主要写一下如何使用标准库对基础数据进行排序,以及如何实现对自定义类型的数据进行排序。

标准库提供一个通用接口,只要实现了这个接口,就可以通过调用 sort.Sort 来排序。

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less returns whether the element with index i should sort
    // before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

基本数据类型的排序

Interface 接口的三个函数分别用于获取长度(Len)、大小比较(Less)和交换(Swap)。对 intfloat64string 的排序,标准库已经做好了封装,直接调用即可。以 int 为例简单说明:

package main                                                                                                                                                                                                 

import (
    "fmt"
    "sort"
)

func main() {
    a := []int{100, 5, 29, 3, 76}
    fmt.Println(a)     // [100 5 29 3 76]
    sort.Ints(a)       // sort.Sort(IntSlice(a)) 的封装
    fmt.Println(a)     // [3 5 29 76 100],默认的 Less() 实现的是升序

    a = []int{100, 5, 29, 3, 76}
    fmt.Println(a)     // [100 5 29 3 76]
    sort.Sort(sort.Reverse(sort.IntSlice(a)))
    fmt.Println(a)     // [100 76 29 5 3]
}

float64string 的排序,和上面类似。需要注意的是,默认的 sort.Less 实现的是升序排列,如果想要让结果降序,可以先用 sort.Reverse 包装一次。这个调用会得到一个 reverse 的类型,包含一个 Interface 的匿名字段,其 Less 函数与 Interface 里的相反,从而实现逆序。

自定义数据类型的排序

如果要对自定义的数据类型进行排序,需要实现 sort.Interface 接口,也就是实现 LenLessSwap 三个函数。很多场景下 LenSwap 基本上和数据类型无关,所以实际上只有 Less 会有差别。

例如有个游戏下载排行榜,知道游戏ID和对应的下载量,需要把数据根据下载量进行排序。

package main

import (
    "fmt"
    "math/rand"
    "sort"
)

type GameDownloadItem struct {
    GameID        int // 游戏ID
    DownloadTimes int // 下载次数
}

func (self GameDownloadItem) String() string {
    return fmt.Sprintf("<Item(%d, %d)>", self.GameID, self.DownloadTimes)
}

type GameDownloadSlice []*GameDownloadItem

func (p GameDownloadSlice) Len() int {
    return len(p)
}

func (p GameDownloadSlice) Swap(i int, j int) {
    p[i], p[j] = p[j], p[i]
}

// 根据游戏下载量 降序 排列
func (p GameDownloadSlice) Less(i int, j int) bool {
    return p[i].DownloadTimes > p[j].DownloadTimes
}

func main() {
    a := make(GameDownloadSlice, 7)
    for i := 0; i < len(a); i++ {
        a[i] = &GameDownloadItem{i + 1, rand.Intn(1000)}
    }

    fmt.Println(a)
    sort.Sort(a)
    fmt.Println(a)
}

第一次输出结果是随机(每次运行结果都一样)生成的未排序的数据:

[<Item(1, 81)> <Item(2, 887)> <Item(3, 847)> <Item(4, 59)> <Item(5, 81)> <Item(6, 318)> <Item(7, 425)>]

排序后:

[<Item(2, 887)> <Item(3, 847)> <Item(7, 425)> <Item(6, 318)> <Item(1, 81)> <Item(5, 81)> <Item(4, 59)>]

Vs. Python

相比之下,Python 里的排序就非常简单便捷了,直接调用 listsort 方法(in-place)即可,还可以用 built-in 函数 sorted (返回新列表)。对于自定义类型指定属性,或 tuple 指定列的排序也很简单,只需要重新定义一下 sort 方法的 key 参数。对于上面游戏下载量排序的例子,下面是 python 实现版本:

#!/usr/bin/env python                                                                                                                                                                                        
# -*- coding: utf-8 -*-

import random

class GameDownloadItem(object):

    def __init__(self, game_id, download_times):
        self.game_id = game_id
        self.download_times = download_times

    def __str__(self):
        return '<Item(%d, %d)>' % (self.game_id, self.download_times)

def display(items):
    for item in items:
        print item,
    print '\n'


if __name__ == "__main__":
    items = [GameDownloadItem(i+1, random.randrange(1000)) for i in range(7)]
    display(items)

    items.sort(key=lambda item: item.download_times, reverse=True)
    display(items)

某一次的执行结果:

<Item(1, 819)> <Item(2, 959)> <Item(3, 812)> <Item(4, 193)> <Item(5, 408)> <Item(6, 884)> <Item(7, 849)>

<Item(2, 959)> <Item(6, 884)> <Item(7, 849)> <Item(1, 819)> <Item(3, 812)> <Item(5, 408)> <Item(4, 193)>

Comments

getElementsByTagName('BODY')[0]).appendChild(s); }()); getElementsByTagName('BODY')[0]).appendChild(s); }()); getElementsByTagName('BODY')[0]).appendChild(s); }()); comments powered by Disqus ript">comments powered by Disqus.