golang中sort包用法
本文内容纲要:
-typeInterface
golang中也实现了排序算法的包sort包.
sort包中实现了3种基本的排序算法:插入排序.快排和堆排序.和其他语言中一样,这三种方式都是不公开的,他们只在sort包内部使用.所以用户在使用sort包进行排序时无需考虑使用那种排序方式,sort.Interface定义的三个方法:获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法,就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。
typeInterface
typeInterfaceinterface{
Len()int//Len为集合内元素的总数
Less(i,jint)bool//如果index为i的元素小于index为j的元素,则返回true,否则返回false
Swap(i,jint)//Swap交换索引为i和j的元素
}
任何实现了sort.Interface的类型(一般为集合),均可使用该包中的方法进行排序。这些方法要求集合内列出元素的索引为整数。
funcFloat64s(a[]float64)//Float64s将类型为float64的slicea以升序方式进行排序
funcFloat64sAreSorted(a[]float64)bool//判定是否已经进行排序funcInts(a[]int)
funcInts(a[]int)//Ints以升序排列int切片。
funcIntsAreSorted(a[]int)bool//IntsAreSorted判断int切片是否已经按升序排列。
funcIsSorted(dataInterface)boolIsSorted判断数据是否已经排序。包括各种可sort的数据类型的判断.
funcStrings(a[]string)//Strings以升序排列string切片。
funcStringsAreSorted(a[]string)bool//StringsAreSorted判断string切片是否已经按升序排列。
packagemain
import(
"fmt"
"sort"
)
//定义interface{},并实现sort.Interface接口的三个方法
typeIntSlice[]int
func(cIntSlice)Len()int{
returnlen(c)
}
func(cIntSlice)Swap(i,jint){
c[i],c[j]=c[j],c[i]
}
func(cIntSlice)Less(i,jint)bool{
returnc[i]<c[j]
}
funcmain(){
a:=IntSlice{1,3,5,7,2}
b:=[]float64{1.1,2.3,5.3,3.4}
c:=[]int{1,3,5,4,2}
fmt.Println(sort.IsSorted(a))//false
if!sort.IsSorted(a){
sort.Sort(a)
}
if!sort.Float64sAreSorted(b){
sort.Float64s(b)
}
if!sort.IntsAreSorted(c){
sort.Ints(c)
}
fmt.Println(a)//[12357]
fmt.Println(b)//[1.12.33.45.3]
fmt.Println(c)//[12345]
}
funcSearch(nint,ffunc(int)bool)int
search使用二分法进行查找,Search()方法回使用“二分查找”算法来搜索某指定切片[0:n],并返回能够使f(i)=true的最小的i(0<=i<n)值,并且会假定,如果f(i)=true,则f(i+1)=true,即对于切片[0:n],i之前的切片元素会使f()函数返回false,i及i之后的元素会使f()函数返回true。但是,当在切片中无法找到时f(i)=true的i时(此时切片元素都不能使f()函数返回true),Search()方法会返回n(而不是返回-1)。
Search常用于在一个已排序的,可索引的数据结构中寻找索引为i的值x,例如数组或切片。这种情况下,实参f,一般是一个闭包,会捕获所要搜索的值,以及索引并排序该数据结构的方式。
为了查找某个值,而不是某一范围的值时,如果slice以升序排序,则ffunc中应该使用>=,如果slice以降序排序,则应该使用<=.例子如下:packagemain
packagemain
import(
"fmt"
"sort"
)
funcmain(){
a:=[]int{1,2,3,4,5}
b:=sort.Search(len(a),func(iint)bool{returna[i]>=30})
fmt.Println(b)//5,查找不到,返回aslice的长度5,而不是-1
c:=sort.Search(len(a),func(iint)bool{returna[i]<=3})
fmt.Println(c)//0,利用二分法进行查找,返回符合条件的最左边数值的index,即为0
d:=sort.Search(len(a),func(iint)bool{returna[i]==3})
fmt.Println(d)//2
}
官网上面有趣的例子:
funcGuessingGame(){
varsstring
fmt.Printf("Pickanintegerfrom0to100.\n")
answer:=sort.Search(100,func(iint)bool{
fmt.Printf("Isyournumber<=%d?",i)
fmt.Scanf("%s",&s)
returns!=""&&s[0]=='y'
})
fmt.Printf("Yournumberis%d.\n",answer)
}
funcSearchFloat64s(a[]float64,xfloat64)int//SearchFloat64s在float64s切片中搜索x并返回索引如Search函数所述.返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列
funcSearchInts(a[]int,xint)int//SearchInts在ints切片中搜索x并返回索引如Search函数所述.返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列
funcSearchStrings(a[]string,xstring)int//SearchFloat64s在strings切片中搜索x并返回索引如Search函数所述.返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列
其中需要注意的是,以上三种search查找方法,其对应的slice必须按照升序进行排序,否则会出现奇怪的结果.
packagemain
import(
"fmt"
"sort"
)
funcmain(){
a:=[]string{"a","c"}
i:=sort.SearchStrings(a,"b")
fmt.Println(i)//1
b:=[]string{"a","b","c","d"}
i=sort.SearchStrings(b,"b")
fmt.Println(i)//1
c:=[]string{"d","c"}
i=sort.SearchStrings(c,"b")
fmt.Println(i)//0
d:=[]string{"c","d","b"}
i=sort.SearchStrings(d,"b")
fmt.Println(i)//0,由于d不是以升序方式排列,所以出现奇怪的结果,这可以根据SearchStrings的定义进行解释.见下方.
}
<pre>funcSearchStrings(a[]string,xstring)int{
<spanid="L202"class="ln"></span> returnSearch(len(a),func(iint)bool{<spanstyle="color:#FF0000;">returna[i]>=x}</span>)
<spanid="L203"class="ln"></span>}
由此可见,为了精确查找,必须对[]string以升序方式进行排序.
funcSort(dataInterface)//Sort对data进行排序。它调用一次data.Len来决定排序的长度n,调用data.Less和data.Swap的开销为O(n*log(n))。此排序为不稳定排序。他根据不同形式决定使用不同的排序方式(插入排序,堆排序,快排)
funcStable(dataInterface)
Stable对data进行排序,不过排序过程中,如果data中存在相等的元素,则他们原来的顺序不会改变,即如果有两个相等元素num,他们的初始index分别为i和j,并且i<j,则利用Stable对data进行排序后,i依然小于j.直接利用sort进行排序则不能够保证这一点.
golang自身实现的interface有三种,Float64Slice,IntSlice,StringSlice,具体如下所示:
typeFloat64Slice
typeFloat64Slice[]float64
Float64Slice针对[]float6实现接口的方法,以升序排列。
func(pFloat64Slice)Len()int//求长度
func(pFloat64Slice)Less(i,jint)bool//比大小
func(pFloat64Slice)Search(xfloat64)int//查找
func(pFloat64Slice)Sort()//排序
func(pFloat64Slice)Swap(i,jint)//交换位置
typeIntSlice
typeIntSlice[]int
IntSlice针对[]int实现接口的方法,以升序排列。
func(pIntSlice)Len()int
func(pIntSlice)Less(i,jint)bool
func(pIntSlice)Search(xint)int
func(pIntSlice)Sort()
func(pIntSlice)Swap(i,jint)
typeStringSlice
typeStringSlice[]string
StringSlice针对[]string实现接口的方法,以升序排列。
func(pStringSlice)Len()int
func(pStringSlice)Less(i,jint)bool
func(pStringSlice)Search(xstring)int
func(pStringSlice)Sort()
func(pStringSlice)Swap(i,jint)
funcReverse(dataInterface)Interface
funcReverse(dataInterface)Interface
Reverse实现对data的逆序排列
packagemain
import(
"fmt"
"sort"
)
funcmain(){
a:=[]int{1,2,5,3,4}
fmt.Println(a)//[12534]
sort.Sort(sort.Reverse(sort.IntSlice(a)))
fmt.Println(a)//[54321]
}
本文内容总结:typeInterface,
原文链接:https://www.cnblogs.com/msnsj/p/4242578.html