Implementation method and application of sort package in go language

preface

The sort package of Go implements built-in and user-defined sorting, and the sort package implements three basic sorting algorithms: insertion sort. Quicksort and heap sort. Like in other languages, these three methods are not public and are used only within the sort package. So users do not need to consider the sorting method when using the sort package. The three methods defined by sort.Interface: the Len() method to get the length of the data set, the Less() method to compare the size of two elements, and the Swap() method to exchange the location of two elements can successfully sort the data set. The sort package automatically selects an efficient sorting algorithm based on actual data.

Share with you before the Go language use sort package element for any type of collection sorting method, interested friends can refer to this article: https: / / www ofstack. com article / 60893. htm

Take a look at a simple example of the sort package:

type Interface interface {
 //  Returns the length of data to sort 
 Len() int
 // Let's compare the subscript i and j Corresponding data size, you can control the ascending and descending order   
Less(i, j int) bool
 //  Student: Swap subscript theta i . j Corresponding data 
 Swap(i, j int)
}

Any type that implements ES30en.Interface (1 is generally a collection) can be sorted using methods in that package. These methods require that the index listing elements in the collection be an integer.

Here I directly use the source code to explain the implementation:

1. Examples in source code:

type Person struct {
 Name string
 Age int
}

type ByAge []Person
// To achieve the sort The interface 3 You can use the sort method 
func (a ByAge) Len() int   { return len(a) }
func (a ByAge) Swap(i, j int)  { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func Example() {
 people := []Person{
  {"Bob", 31},
  {"John", 42},
  {"Michael", 17},
  {"Jenny", 26},
 }

 fmt.Println(people)
 sort.Sort(ByAge(people)) // This is called sort In the package Sort() methods , We look at 1 The next method 
 fmt.Println(people)

 // Output:
 // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
 // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
}

2. Sort(data Interface) method

//sort The package only provides this 1 Three publicly used sorting methods, 
func Sort(data Interface) {
 // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
 // If the depth of the element reaches 2*ceil(lg(n+1)) Heap sort is chosen 
 n := data.Len()
 maxDepth := 0
 for i := n; i > 0; i >>= 1 {
  maxDepth++
 }
 maxDepth *= 2
 quickSort(data, 0, n, maxDepth)
}

// Quick sort 
// It's going to automatically choose whether to do heap sort or insert sort or quicksort, which is quicksort 
func quickSort(data Interface, a, b, maxDepth int) {
 // If you slice less than that 102 Hill insertion is used 
 for b-a > 12 { // Use ShellSort for slices <= 12 elements
  if maxDepth == 0 {
   heapSort(data, a, b) // Heap sort method, a=0,b=n
   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)
 }
}

// Heap sort 
func heapSort(data Interface, a, b int) {
 first := a
 lo := 0
 hi := b - a

 // Build heap with greatest element at top.
 // Building the heap structure, the top of the largest element, is building the big root heap 
 for i := (hi - 1) / 2; i >= 0; i-- {
  siftDown(data, i, hi, first)
 }

 // Pop elements, largest first, into end of data.
 // the first Inserted into the data the end At the end 
 for i := hi - 1; i >= 0; i-- {
  data.Swap(first, first+i) // Data interchange 
  siftDown(data, lo, i, first) // Heap re-filtering 
 }
}

// siftDown implements the heap property on data[lo, hi).
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
 //hi Is the length of the array 
 // There's a 1 One way to do this is to save the following element, but in order to make the method more abstract, I'm going to omit this part and replace it with the following element swap "And exchange them with each other 
 root := lo // The subscript of the root element 
 for {
  child := 2*root + 1 // The index of the left leaf node 
  // control for Loop introduction, this is a more concise way to write, you can see my heap sort article 
  if child >= hi { 
   break
  }
  // To prevent the array index from crossing the line, determine the size of the left and right children 
  if child+1 < hi && data.Less(first+child, first+child+1) { 
   child++
  }
  // Determine the relationship between the largest child and the root element 
  if !data.Less(first+root, first+child) {
   return
  }
  // If all of the above   If so, data exchange will take place 
  data.Swap(first+root, first+child)
  root = child
 }
}

There are many other methods in this package, and this package implements many methods, such as sort reversal and two-point search. Sorting USES the method quickSort () to control whether the call is quicksort or heapsort.

conclusion