google-app-engine - Go中的字母数字排序

Question

我正在从 GAE 数据存储中读取行，我想按字母数字顺序对它们进行排序。

假设我有这样的东西:

key      name      description    sequence  
===========================================  
ASD..    maths1    it is maths    chap21.1  
ASD..    maths2    it is maths    chap21.10  
ASD..    maths3    it is maths    chap21.2  

我希望结果在序列字段上按字母数字排序，如下所示:

key      name      description    sequence  
===========================================  
ASD..    maths1    it is maths    chap21.1  
ASD..    maths3    it is maths    chap21.2 
ASD..    maths2    it is maths    chap21.10   

Answer 1

使用ISO/IEC 14651:2011构造序列排序键。例如，

package main

import (
    "fmt"
    "sort"
)

const maxByte = 1<<8 - 1

func isDigit(d byte) bool {
    return '0' <= d && d <= '9'
}

func SequenceKey(key string) string {
    sKey := make([]byte, 0, len(key)+8)
    j := -1
    for i := 0; i < len(key); i++ {
        b := key[i]
        if !isDigit(b) {
            sKey = append(sKey, b)
            j = -1
            continue
        }
        if j == -1 {
            sKey = append(sKey, 0x00)
            j = len(sKey) - 1
        }
        if sKey[j] == 1 && sKey[j+1] == '0' {
            sKey[j+1] = b
            continue
        }
        if sKey[j]+1 > maxByte {
            panic("SequenceKey: invalid key")
        }
        sKey = append(sKey, b)
        sKey[j]++
    }
    return string(sKey)
}

type Chapter struct {
    Key         string
    Name        string
    Description string
    Sequence    string
    SequenceKey string `datastore:"-"`
}

type Chapters []*Chapter

var chapters = Chapters{
    {Key: "ASD..", Name: "maths1", Description: "it is maths", Sequence: "chap21.1"},
    {Key: "ASD..", Name: "maths2", Description: "it is maths", Sequence: "chap21.10"},
    {Key: "ASD..", Name: "maths3", Description: "it is maths", Sequence: "chap21.2"},
}

func (s Chapters) Len() int {
    return len(s)
}

func (s Chapters) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

type BySequenceKey struct{ Chapters }

func (s BySequenceKey) Less(i, j int) bool {
    return s.Chapters[i].SequenceKey < s.Chapters[j].SequenceKey
}

func main() {
    for _, chapter := range chapters {
        chapter.SequenceKey = SequenceKey(chapter.Sequence)
    }
    fmt.Println("Unsorted:")
    for _, chapter := range chapters {
        fmt.Printf("  sequence: %#v\n", chapter.Sequence)
        fmt.Printf("    sort key: %#v\n", chapter.SequenceKey)
        fmt.Printf("      name: %#v\n", chapter.Name)
    }
    fmt.Println("Sorted:")
    sort.Sort(BySequenceKey{chapters})
    for _, chapter := range chapters {
        fmt.Printf("  sequence: %#v\n", chapter.Sequence)
        fmt.Printf("    sort key: %#v\n", chapter.SequenceKey)
        fmt.Printf("      name: %#v\n", chapter.Name)
    }
}

输出:

Unsorted:
  sequence: "chap21.1"
    sort key: "chap\x0221.\x011"
      name: "maths1"
  sequence: "chap21.10"
    sort key: "chap\x0221.\x0210"
      name: "maths2"
  sequence: "chap21.2"
    sort key: "chap\x0221.\x012"
      name: "maths3"
Sorted:
  sequence: "chap21.1"
    sort key: "chap\x0221.\x011"
      name: "maths1"
  sequence: "chap21.2"
    sort key: "chap\x0221.\x012"
      name: "maths3"
  sequence: "chap21.10"
    sort key: "chap\x0221.\x0210"
      name: "maths2"