4.2.4.排序和查找切片
标准库中的sort包提供了对int类型、float64类型和string类型的切片进行排序的函数，检查切片是否已排序的函数和使用二分查找法在已排序的切片中查找特定元素的函数。同时标准库也提供了通用的用于自定义数据的sort.Sort() 和sort.Search()函数。表4.2列出了这些函数。
正如我们在之面的章节中看到的那样，Go语言对数值的排序方式并不稀奇。但是，对字符串的排序完全是按字节的形式。这意味着字符串的排序是大小写敏感的。下面是几个字符串排序的例子和产生的结果。
1 2 3 4 5 6 7 8 9 10 | files := []string{"Test.conf", "util.go", "Makefile", "misc.go", "main.go"} fmt.Printf("Unsorted: %q\n", files) sort.Strings(files) // Standard library sort function fmt.Printf("Underlying bytes: %q\n", files) SortFoldedStrings(files) // Custom sort function fmt.Printf("Case insensitive: %q\n", files) Unsorted: ["Test.conf" "util.go" "Makefile" "misc.go" "main.go"] Underlying bytes: ["Makefile" "Test.conf" "main.go" "misc.go" "util.go"] Case insensitive: ["main.go" "Makefile" "misc.go" "Test.conf" "util.go"] |
表4.2 sort包中的函数
| sort.Float64s(fs) | 将[]float64类型的fs升序排序 |
| sort.Float64sAreSorted(fs) | 如果[]float64类型的fs已排好序，则返回true |
| sort.Ints(is) | []int类型的is升序排序 |
| sort.IntsAreSorted(is) | 如果[]int类型的is已排好序，则返回true |
| sort.IsSorted(d) | 如果sort.Interface类型的d已排好序，则返回true |
| sort.Search(size, fn) | 具有func(int) bool签名的函数fn，以给定的范围size在已排好序的切片中做查找操作返回true时的索引位置 |
| sort.SearchFloat64s(fs, f) | 返回已排好序的[]float64类型的fs中float64类型的f的索引位置 |
| sort.SearchInts(is, i) | 返回已排好序的[]int类型的is中int类型的i的索引位置 |
| sort.SearchStrings(ss, s) | 返回已排好序的[]string类型的ss中string类型的s的索引位置 |
| sort.Sort(d) | 对sort.Interface类型的d进行排序 |
| sort.Strings(ss) | 将[]string类型的ss升序排序 |
| sort.StringsAreSorted(ss) | 如果[]string类型的ss已排好序，则返回true |
标准库中的sort.Strings()函数接受一个[]string切片作为参数，并对该切片中的字符串按照底层字节进行就地升序排序。如果字符串是使用相同的字符到字节映射进行编码（例如，它们都是在当前程序或其它Go程序中创建的），则会按码点进行排序。自定义的 SortFoldedStrings() 函数以同样的方式工作，不同之处是它使用的是sort包中通用的sort.Sort()函数进行排序且是区分大小写的。
sort.Sort()函数可以对具有sort.Interface方法的任何类型进行排序，也就是说，类型根据所需的签名实现了Len()、Less()和 Swap() 方法。这里我们创建了一个实现了上述这些方法的自定义类型FoldedStrings。下面是完整的SortFoldedStrings()函数、FoldedStrings类型和相应的方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | func SortFoldedStrings(slice []string) { sort.Sort(FoldedStrings(slice)) } type FoldedStrings []string func (slice FoldedStrings) Len() int { return len(slice) } func (slice FoldedStrings) Less(i, j int) bool { return strings.ToLower(slice[i]) < strings.ToLower(slice[j]) } func (slice FoldedStrings) Swap(i, j int) { slice[i], slice[j] = slice[j], slice[i] } |
SortFoldedStrings()函数只是简单的调用了标准库中的sort.Sort()函数，并使用Go语言的标准转换语法将给定的[]string转换（代价很小）成一个FoldedStrings类型的值。一般情况下，每当我们创建一个基于内置类型的自定义类型时，我们就可以通过这种方式将内置类型的值转换成一个自定义类型的值。
FoldedStrings类型提供了三个满足sort. Interface接口的方法。这三个方法都比较短小；并通过在Less()方法中使用strings.ToLower()函数来达到不区分大小写的目的。（如果我们希望按降序排序，我们可以简单地将Less()方法中的小于号<替换为大于号>。）
正如我们在之前的章节中讨论的那样，SortFoldedStrings()函数对于7位ASCII编码的（即英语）字符串来说是完全能够胜任的，但是对于非英语语言，排序结果却不尽人如意。对于非英语语言，要完全正确的将Unicode编码的字符串进行排序不是一个简单的任务。这在Unicode 排序规则算法文档 (unicode.org/reports/tr10) 中有详细的解释。
如果我们想要在一个切片中查找某个特定元素的（如果该切片含有元素）的索引位置，我们可以使用for … range来做到这一点。
1 2 3 4 5 6 7 8 9 10 | files := []string{"Test.conf", "util.go", "Makefile", "misc.go", "main.go"} target := "Makefile" for i, file := range files { if file == target { fmt.Printf("found \"%s\" at files[%d]\n", file, i) break } } found "Makefile" at files[2] |
对于未排序的数据，使用简单的线性查找是唯一的选择，对于小的切片（多至数百个元素）来说也是可以使用的。但是对于较大的切片来说，尤其是当我们重复执行查找操作时，线性查找的效率是很低的，平均每次都需要将一半的元素进行比较。
Go语言提供了一个sort.Search()方法，该方法使用的是二分查找算法：每次只需要进行log2(n)个元素（其中n是元素的个数）的比较。具体来说，1000000个元素的线性查找平均需要500000次比较，最坏的情况下是1000000次比较；而二分查找算法即使在最坏的情况下也最多需要20次比较。
1 2 3 4 5 6 7 8 9 10 | sort.Strings(files) fmt.Printf("%q\n", files) i := sort.Search(len(files), func(i int) bool { return files[i] >= target }) if i < len(files) && files[i] == target { fmt.Printf("found \"%s\" at files[%d]\n", files[i], i) } ["Makefile" "Test.conf" "main.go" "misc.go" "util.go"] found "Makefile" at files[0] |
sort.Search()函数接受两个参数：要处理的切片的长度和一个比较函数，其中比较函数用于对一个有序切片中的元素和目标元素进行比较，对于按升序排序的切片使用>=操作符来比较，对于按降序排序的切片则使用<=操作符进行比较。该函数必须是一个闭包，也就是说，必须要在要处理的切片的作用域中创建，因为它必须要将该切片作为其状态的一部分。sort.Search()函数返回一个整型值；只有当该返回值小于切片的长度且在该索引位置的元素匹配目标元素时，这样我们才能确定找到了我们要查找的元素。
下面的函数用于在一个有序的不区分大小写的[]string切片中查找一个小写的目标字符串。
1 2 3 4 5 6 7 8 9 10 11 12 | target := "makefile" SortFoldedStrings(files) fmt.Printf("%q\n", files) caseInsensitiveCompare := func(i int) bool { return strings.ToLower(files[i]) >= target } i := sort.Search(len(files), caseInsensitiveCompare) if i < len(files) && strings.EqualFold(files[i], target) { fmt.Printf("found \"%s\" at files[%d]\n", files[i], i) } ["main.go" "Makefile" "misc.go" "Test.conf" "util.go"] found "Makefile" at files[1] |
这里我们在sort.Search()函数的外部创建了比较函数。但是需要注意的是，就像之前的例子中演示的那样，比较函数必须是一个闭包且必须要在要处理的切片的作用域中创建。我们本可以使用strings.ToLower( files[i])==target来比较字符串。但是这里我们使用了更方便的strings.EqualFold()函数以不区分大小写的方式比较两个字符串。
Go语言的切片是一种如此的方便、功能强大且用途广泛的数据结构，很难想象会有哪个Go语言程序不会使用到它们。
虽然切片适用于大多数使用场景，但是在某些情况下，我们需要将数据保存为键值对的形式并能够按键进行快速查找。Go语言的映射类型提供了该功能，我们将在下一节介绍。
