GO语言学习笔记6-Sort的使用

GoLang标准库的sort包提供了排序切片和用户自定义数据集以及相关功能的函数。

Sort操作的对象通常是一个slice，需要满足三个基本的接口，并且能够使用整数来索引。

1.sort实现原理

Sort排序的函数原型如下所示：

（1）Sort

// 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) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

（2) interface

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports 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)
}

(3) quickSort

func quickSort(data Interface, a, b, maxDepth int) {
    for b-a > 12 { // Use ShellSort for slices <= 12 elements
        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 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

2.Sort内部 []int排序

type IntSlice []int
// 获取此 slice 的长度
func (p IntSlice) Len() int           { return len(p) }

// 比较两个元素大小，升序
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }

// 交换数据
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

// Sort is a convenience method.
func (p IntSlice) Sort() { Sort(p) }

3.代码实现

Olymic Game 这道题采用Sort排序的实现方法如下：

package main

import (
    "fmt"
    "sort"
    "strings"
)

type MedalNum struct {
    name string
    gold int
    silver int
    bronze int
}

type MedalNumList []MedalNum

func (m MedalNumList) Len() int {
    return len(m)
}

// 奖牌数降序，国家名称字典序
func (m MedalNumList) Less(i, j int) bool {
    if m[i].gold > m[j].gold {
        return true
    } else if m[i].gold == m[j].gold {
        if m[i].silver > m[j].silver {
            return true
        } else if m[i].silver == m[j].silver {
            if m[i].bronze > m[j].bronze {
                return true
            } else if m[i].bronze == m[j].bronze {
                if strings.Compare(m[i].name, m[j].name) < 0 {
                    return true
                }
            }
        }

    }
    return false
}

func (m MedalNumList) Swap(i, j int) {
    m[i], m[j] = m[j], m[i]
}

func main() {
    var n int

    _, _ = fmt.Scan(&n)

    var medal MedalNumList

    var nameI string
    var goldI, sliverI, bronzeI int

    i := 0
    for {
        if i == n {
            break
        }
        _, err := fmt.Scanln(&nameI, &goldI, &sliverI, &bronzeI);

        if err != nil {
            break
        } else {
            medal = append(medal, MedalNum{name:nameI, gold:goldI, silver:sliverI, bronze:bronzeI})
        }

        i++
    }

    sort.Sort(medal)

    for _, m := range medal {
        fmt.Println(m.name)
    }

}

Compare是字符串比较函数，函数原型如下所示：

// Compare returns an integer comparing two strings lexicographically.
// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
func Compare(a, b string) int {
    if a == b {
        return 0
    }
    if a < b {
        return -1
    }
    return +1
}