go语言中sort包的实现方法与应用详解

前言

Go语言的 sort 包实现了内置和用户定义类型的排序,sort包中实现了3种基本的排序算法:插入排序.快排和堆排序.和其他语言中一样,这三种方式都是不公开的,他们只在sort包内部使用.所以用户在使用sort包进行排序时无需考虑使用那种排序方式,sort.Interface定义的三个方法:获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法,就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。

之前跟大家分享了Go语言使用sort包对任意类型元素的集合进行排序的方法,感兴趣的朋友们可以参考这篇文章:http://www.jb51.net/article/60893.htm

下面来看看sort包的简单示例:

type Interface interface {
 // 返回要排序的数据长度
 Len() int
 //比较下标为i和j对应的数据大小,可自己控制升序和降序
Less(i, j int) bool
 // 交换下标为i,j对应的数据
 Swap(i, j int)
}

任何实现了 sort.Interface 的类型(一般为集合),均可使用该包中的方法进行排序。这些方法要求集合内列出元素的索引为整数。

这里我直接用源码来讲解实现:

1、源码中的例子:

type Person struct {
 Name string
 Age int
}

type ByAge []Person
//实现了sort接口中的三个方法,则可以使用排序方法了
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)) //此处调用了sort包中的Sort()方法,我们看一下这个方法
 fmt.Println(people)

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

2、Sort(data Interface)方法

//sort包只提供了这一个公开的公使用的排序方法,
func Sort(data Interface) {
 // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
 //如果元素深度达到2*ceil(lg(n+1))则选用堆排序
 n := data.Len()
 maxDepth := 0
 for i := n; i > 0; i >>= 1 {
  maxDepth++
 }
 maxDepth *= 2
 quickSort(data, 0, n, maxDepth)
}
//快速排序
//它这里会自动选择是用堆排序还是插入排序还是快速排序,快速排序就是
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) //堆排序方法,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)
 }
}
//堆排序
func heapSort(data Interface, a, b int) {
 first := a
 lo := 0
 hi := b - a

 // Build heap with greatest element at top.
 //构建堆结构,最大的元素的顶部,就是构建大根堆
 for i := (hi - 1) / 2; i >= 0; i-- {
  siftDown(data, i, hi, first)
 }

 // Pop elements, largest first, into end of data.
 //把first插入到data的end结尾
 for i := hi - 1; i >= 0; i-- {
  data.Swap(first, first+i) //数据交换
  siftDown(data, lo, i, first) //堆重新筛选
 }
}
// 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为数组的长度
 //这里有一种做法是把跟元素给取到存下来,但是为了方法更抽象,省掉了这部,取而代之的是在swap的时候进行相互交换
 root := lo //根元素的下标
 for {
  child := 2*root + 1 //左叶子结点下标
  //控制for循环介绍,这种写法更简洁,可以查看我写的堆排序的文章
  if child >= hi {
   break
  }
  //防止数组下标越界,判断左孩子和右孩子那个大
  if child+1 < hi && data.Less(first+child, first+child+1) {
   child++
  }
  //判断最大的孩子和根元素之间的关系
  if !data.Less(first+root, first+child) {
   return
  }
  //如果上面都 满足,则进行数据交换
  data.Swap(first+root, first+child)
  root = child
 }
}

这个包中还有很多方法,这个包实现了很多方法,比如排序反转,二分搜索。排序通过 quickSort()这个方法来控制该调用快排还是堆排。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

(0)

相关推荐

  • Go语言使用sort包对任意类型元素的集合进行排序的方法

    本文实例讲述了Go语言使用sort包对任意类型元素的集合进行排序的方法.分享给大家供大家参考.具体如下: 使用sort包的函数进行排序时,集合需要实现sort.Inteface接口,该接口中有三个方法: 复制代码 代码如下: // Len is the number of elements in the collection.  Len() int  // Less reports whether the element with  // index i should sort before t

  • golang使用sort接口实现排序示例

    本文实例讲述了golang使用sort接口实现排序的方法.分享给大家供大家参考,具体如下: 今天看见群里再讨论排序的sort.Interface的实现,有童鞋一直搞不定,我就上手了一下,哦耶搞定了,代码放在这里. 其实很简单sort.Interface借口有三个方法,给自己的struct实现这三个方法,然后用将自己的结构体传给sort.Sort方法就排序完成. 当然sort包也有几个常用的方法sort.Float64Slice sort.IntSlise sort.StringSlise,呵呵

  • go语言中sort包的实现方法与应用详解

    前言 Go语言的 sort 包实现了内置和用户定义类型的排序,sort包中实现了3种基本的排序算法:插入排序.快排和堆排序.和其他语言中一样,这三种方式都是不公开的,他们只在sort包内部使用.所以用户在使用sort包进行排序时无需考虑使用那种排序方式,sort.Interface定义的三个方法:获取数据集合长度的Len()方法.比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法,就可以顺利对数据集合进行排序.sort包会根据实际数据自动选择高效的排序算法. 之前跟大家分享了

  • C语言中const和C++中的const 区别详解

    C语言中const和C++中的const 区别详解 C++的const和C语言的#define都可以用来定义常量,二者是有区别的,const是有数据类型的常量,而宏常量没有,编译器可以对前者进行静态类型安全检查,对后者仅是字符替换,没有类型安全检查. 而C语言中的const与C++也有很大的不同,在C语言中用const修饰的变量仍是一个变量,表示这个变量是只读的,不可显示地更改,而在C++中用const修饰过后,就变成常量了.例如下面的代码: const int n=10; int a[n];

  • C语言中%c与%s的区别与划分详解

    %c格式对应的是单个字符,%s格式对应的是字符串. 例: char a; char b[20]; scanf("%c",&a); //只能输入一个字符. scanf("%s",b); //可以输入一串不超过20字符的字符串. %c对应类型为char, %s对应类型为char * , 即字符串. 用作输入时, 二者参数都要传char * 型. %c输入函数只会对一个字节空间赋值. 而%s会一直赋值,直到输入中遇到空白字符为止. 用作输出时, %c传char类型

  • Go语言中init函数和defer延迟调用关键词详解

    Go语言中init函数和defer延迟调用关键词 golang里面有两个保留函数 main 函数(只能应用于package main) init 函数(能够应用于所有的package) go程序会自动调用 init()和main() 所以你不能在任何地方调用这两个函数 package main 必须包含一个main 函数,但是每个package中的init函数都是可选的 一个package 里可以写多个init函数,建议每个包中只写一个init函数 单个包中代码执行顺序如下 main包 -->

  • C语言中break与continue的用法和区别详解

    目录 前言 一.循环体中两者的作用 1.while循环 2.for循环 3.do while循环 二.switch语句 总结 前言 本文将通过简单的实例来详细分析在C语言中break语句和continue语句的用法和区别,欢迎大家批评指正.(部分内容稍有重复,大家可自行选择跳转目录) 一.循环体中两者的作用 1.while循环 我们先看一个循环示例:此程序在屏幕上打印出数字1-10 int main() { int i = 1; while (i <= 10) { printf("%d &

  • R语言中ifelse、which、%in%的用法详解

    ifelse.which.%in%是R语言里极其重要的函数,以后会经常在别的程序中看到. ifelse ifelse是if条件判断语句的简写,它的用法如下: ifelse(test,yes,no) 参数 描述 test 一个可以判断逻辑表达式 yes 判断为 true 后返回的对象 no 判断为 flase 后返回的对象 举例: x = 5 ifelse(x,1,0) 如果x不等于0,就返回1,等于0就返回0. which which 返回条件为真的句柄,给正确的逻辑对象返回一个它的索引. wh

  • C语言中fchdir()函数和rewinddir()函数的使用详解

    C语言fchdir()函数:改变当前工作目录 头文件: #include <unistd.h> 定义函数: int fchdir(int fd); 函数说明:fchdir()用来将当前的工作目录改变成以参数fd 所指的文件描述词. 返回值:执行成功则返回 0, 失败返回-1, errno 为错误代码. 范例 #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <

  • C语言中lseek()函数和fseek()函数的使用详解

    C语言lseek()函数:移动文件的读写位置 头文件: #include <sys/types.h> #include <unistd.h> 定义函数: off_t lseek(int fildes, off_t offset, int whence); 函数说明: 每一个已打开的文件都有一个读写位置, 当打开文件时通常其读写位置是指向文件开头, 若是以附加的方式打开文件(如O_APPEND), 则读写位置会指向文件尾. 当read()或write()时, 读写位置会随之增加,ls

  • C语言中getchar()的返回类型为什么是int详解

    前言 在C语言中有个重要的库函数getchar(),可从终端获得一个字符的ASCII码值.在终端输入字符时并非输入一个字符就会返回,而是在遇到回车换行前,所有输入的在C语言中有个重要的库函数getchar(),可从终端获得一个字符的ASCII码值.在终端输入字符时并非输入一个字符就会返回,而是在遇到回车换行前,所有输入的字符都会缓冲在键盘缓冲器中,直到回车换行一次性将所有字符按序依次赋给相应的变量,在这里一定要注意最后一个字符即'\n',该字符也会赋给一个相应的变量(当然这要你定义的用来接收字符

  • 详解go语言中sort如何排序

    目录 sort包源码解读 前言 如何使用 基本数据类型切片的排序 自定义Less排序比较器 自定义数据结构的排序 分析下源码 不稳定排序 稳定排序 查找 Interface 总结 参考 sort 包源码解读 前言 我们的代码业务中很多地方需要我们自己进行排序操作,go 标准库中是提供了 sort 包是实现排序功能的,这里来看下生产级别的排序功能是如何实现的. go version go1.16.13 darwin/amd64 如何使用 先来看下 sort 提供的主要功能 对基本数据类型切片的排序

随机推荐