Sort源码实现比较Go&Java语言风格(1)

 1type Person struct {
 2Name string
 3Age int
 4}
 5// ByAge implements sort.Interface for []Person based on the Age field.
 6type ByAge []Person
 7func (a ByAge) Len() int { return len(a) }
 8func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
 9func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
10func main() {
11sort.Sort(ByAge(people))
12}type Person struct {
13Name string
14Age int
15}
16// ByAge implements sort.Interface for []Person based on the Age field.
17type ByAge []Person
18func (a ByAge) Len() int { return len(a) }
19func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
20func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
21func main() {
22sort.Sort(ByAge(people))
23}

 1/ A type, typically a collection, that satisfies sort.Interface can be
 2// sorted by the routines in this package. The methods require that the
 3// elements of the collection be enumerated by an integer index.
 4type Interface interface {
 5// Len is the number of elements in the collection.
 6Len() int
 7// Less reports whether the element with
 8// index i should sort before the element with index j.
 9Less(i, j int) bool
10// Swap swaps the elements with indexes i and j.
11Swap(i, j int)
12}

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

 1func quickSort(data Interface, a, b, maxDepth int) {
 2for b-a > 7 {
 3if maxDepth == 0 {
 4heapSort(data, a, b)
 5return
 6}
 7maxDepth--
 8mlo, mhi := doPivot(data, a, b)
 9// Avoiding recursion on the larger subproblem guarantees
10// a stack depth of at most lg(b-a).
11if mlo-a < b-mhi {
12quickSort(data, a, mlo, maxDepth)
13a = mhi // i.e., quickSort(data, mhi, b)
14} else {
15quickSort(data, mhi, b, maxDepth)
16b = mlo // i.e., quickSort(data, a, mlo)
17}
18}
19if b-a > 1 {
20insertionSort(data, a, b)
21}
22}

1// Insertion sort
2func insertionSort(data Interface, a, b int) {
3for i := a + 1; i < b; i++ {
4for j := i; j > a && data.Less(j, j-1); j-- {
5data.Swap(j, j-1)
6}
7}
8}