sort实现原理

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

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))
}

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)
}

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)
	}
}

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) }

代码实现

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
}

个人主页：