排序与查找（Go实现）

排序和查找应该是平时用得最多的算法了，虽然可能很多时候是直接使用的sort包封装好的方法，但是掌握简单的算法实现，可以更好地理解排序和查找，在需要的时候更加灵活地使用排序查找，或者封装更适合具体业务场景的排序查找。

在下文的练习中所提到的整数除法，默认都是向下取整的：

  fmt.Println(3 / 2)     // 整数除法，只取整数部分，结果为1
  fmt.Println(3.0 / 2.0) // 小数除法的结果才是小数，结果为1.5

使用包提供的方法

用sort.Sort或sort.Slice排序

go的sort包中的sort.Sort()和sort.Slice()中的排序实现是基于模式识别的快速排序算法（pattern-defeating quicksort，pdqsort）。

package sortdata

import (
	"fmt"
	"sort"
)

func init() {
	data := []int{10, 2, 5, 9, 1}
	sort.Slice(data, func(i, j int) bool { return data[i] < data[j] })
	fmt.Println(data) // [1 2 5 9 10]
}

可以直接使用Slice方法，或者为切片类型定义好方法集，然后使用Sort方法：

package sortdata

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func (p Person) String() string {
	return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

/*
ByAge实现了sort.Interface接口 基于Age字段对[]Person进行排序
*/
type ByAge []Person

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 init() {
	people := []Person{
		{"张三", 31},
		{"李四", 42},
		{"王五", 17},
		{"赵六", 26},
	}

	fmt.Println(people) // [张三: 31 李四: 42 王五: 17 赵六: 26]
	// 有两种方式排序切片，一种方式是为slice类型定义好方法集，比如为ByAge类型定义好方法集，然后调用sort.Sort。
	sort.Sort(ByAge(people))
	fmt.Println(people) // [王五: 17 赵六: 26 张三: 31 李四: 42]

	// 第二种方式是调用sort.Slice方法，包含一个自定义的Less方法
	sort.Slice(people, func(i, j int) bool {
		return people[i].Age > people[j].Age
	})
	fmt.Println(people) // [李四: 42 张三: 31 赵六: 26 王五: 17]
}

用sort.Search查找

sort.Search是使用的二分查找，这意味着在查找前要确保数据是已经排序好的。

package searchdata

import (
  "fmt"
  "sort"
)

func init() {
  target := 23
  data := []int{1, 10, 20, 199, 122, 123}

  i := sort.Search(len(data), func(i int) bool { return data[i] >= target })
  if i < len(data) && data[i] == target {
    fmt.Println("data中找到了目标值", data[i])
  } else {
    fmt.Printf("data中没有找到目标值, 如果要将目标值放入data中, 可以放在索引%v中的位置\n", i)
  }
}

用slices.IndexFunc查找

引入golang.org/x/exp/slice…包，slices.IndexFunc 如果找到值会返回匹配的第一个索引，没找到值会返回-1。

  target1 := 23
  data1 := []int{199, 122, 1, 10, 20, 123}
  idx := slices.IndexFunc(data1, func(item int) bool { return item == target1 })
  if idx == -1 {
    fmt.Println("没有找到目标值")
  } else {
    fmt.Printf("找到了目标值，在索引%v的位置\n", idx)
  }

以上就是使用已有的包进行排序查找的方法，接下来简单了解下一些排序和查找算法的具体实现。

排序

冒泡排序

将相邻的元素两两比较，需要的时候进行交换，这个过程中最大的数字会像冒泡一样“漂”到列表的顶端。

以升序排序为例，把相邻的元素两两比较，如果前一个元素大于后一个元素，就交换它们的位置，否则位置不变。

降序排序就反过来，如果前一个元素小于后一个元素，就交换它们的位置，否则位置不变。

实现方式v1

func BubbleSortV1(list []int) {
  // 一共循环n-1次，每次循环后，最大的数字会到列表最右端
  // 将后n-1个数字都移动到合适的位置后，最后剩下的第一个元素自然是最小的，所以只用循环n-1次
  for i := 0; i < len(list)-1; i++ {
    // 每个循环比较n-1次，n个数字两两比较只需要比较n-1次
    for j := 0; j < len(list)-1; j++ {
      left := j
      right := j + 1
      if list[left] > list[right] {
        swap(list, left, right)
      }
    }
    fmt.Printf("第%v次外循环后的结果 %v\n", i+1, list)
  }
}

func swap(list []int, i, j int) {
  if i == j {
    return
  }
  list[i], list[j] = list[j], list[i]
}

外层循环需要循环n - 1次，每次循环后，最大的数字会到列表的右端，将后n - 1个数字都放到合适的位置后，剩下的第一个元素自然是最小的，所以只需要循环n-1次而不是n次。

内层循环比较n-1次，因为n个数字两两比较只需要比较n-1次，比如3个数字ABC，AB比较，BC比较，只需要比较2次。

所以时间复杂度为(n−1)×(n−1)(n - 1) \times (n - 1)(n−1)×(n−1) ，是O(n2)O(n^2)O(n2)。

调用冒泡排序函数：

func init() {
  list := []int{5, 6, 9, 8, 1, 7, 2}
  BubbleSortV1(list)
  fmt.Printf("最终结果 %v\n", list)
}

打印的结果为：

第1次外循环后的结果 [5 6 8 1 7 2 9]
第2次外循环后的结果 [5 6 1 7 2 8 9]
第3次外循环后的结果 [5 1 6 2 7 8 9]
第4次外循环后的结果 [1 5 2 6 7 8 9]
第5次外循环后的结果 [1 2 5 6 7 8 9]
第6次外循环后的结果 [1 2 5 6 7 8 9]
最终结果 [1 2 5 6 7 8 9]

实现方式v2

在v1的实现方式中，内层循环无论如何都会执行n - 1次，这其实是没必要的，因为在第k次循环的时候，右边的k - 1个数字是已经排序好了的。

比如在第3次外循环开始执行的时候，前两个的外循环是已经把8、9排好序了的，内层循环只需要对索引0到索引4的元素进行两两比较就可以了，第3次循环的时候i等于2，也就是需要比较索引0 到 len(list) - 1 - i的元素。

func BubbleSortV2(list []int) {
  for i := 0; i < len(list)-1; i++ {
    // 内层循环只需循环len(list)-1-i次
    for j := 0; j < len(list)-1-i; j++ {
      left := j
      right := j + 1
      if list[left] > list[right] {
        swap(list, left, right)
      }
    }
    fmt.Printf("第%v次外循环后的结果 %v\n", i+1, list)
  }
}

所以时间复杂度为∑i=0i=n−1(n−1−i)<(n−1)2\sum_{i=0}^{i = n -1}(n - 1 - i) < (n - 1)^2∑i=0i=n−1​(n−1−i)<(n−1)2，还是O(n2)O(n^2)O(n2)的时间复杂度，但是比v1要稍微高效些。

实现方式v3

观察执行v2的冒泡排序打印的结果：

第1次外循环后的结果 [5 6 8 1 7 2 9]
第2次外循环后的结果 [5 6 1 7 2 8 9]
第3次外循环后的结果 [5 1 6 2 7 8 9]
第4次外循环后的结果 [1 5 2 6 7 8 9]
第5次外循环后的结果 [1 2 5 6 7 8 9]
第6次外循环后的结果 [1 2 5 6 7 8 9]

在5次比较之后，列表其实就已经排好序，可以通过一个标志来判断列表是否已经排好序了，如果在内层循环中一次都没有交换，说明列表已经排好序了，不需要进行后续的外循环。

func BubbleSortV3(list []int) {
	for i := 0; i < len(list)-1; i++ {
		isSorted := true
		for j := 0; j < len(list)-1-i; j++ {
			left := j
			right := j + 1
			if list[left] > list[right] {
				swap(list, left, right)
				isSorted = false
			}
		}
		// 如果已经全部都排好序了，就结束循环
		if isSorted {
			break
		}
		fmt.Printf("第%v次外循环后的结果 %v\n", i+1, list)
	}
}

时间复杂度依然是O(n2)O(n^2)O(n2)。

第5次执行之后列表已经排好序了，但是要在第6次外循环中判断列表是否已经排好序，所以第6次循环依然是会执行的，不会执行第6次外循环之后的代码。

选择排序

选择排序在冒泡排序的基础上进行了优化，只在每个外循环中进行一次交换，而不是在内循环中进行多次交换。

以升序排序为例，在未排序的元素中找出最小的元素，和第1个位置的元素交换，第1个位置就排好了，从剩下的元素中继续找到最小元素，放到第2个位置，以此类推，直到所有元素都排好序为止。

降序排序相反，先找到最大的元素放在第1个位置。

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2}
	SelectionSort(list)
	fmt.Printf("最终结果 %v\n", list)
}

func SelectionSort(list []int) {
	for i := 0; i < len(list)-1; i++ {
		minIndex := i
		for j := i + 1; j < len(list); j++ {
			if list[j] < list[minIndex] {
				minIndex = j
			}
		}
		swap(list, i, minIndex)
		fmt.Printf("第%v次外循环后的结果 %v\n", i+1, list)
	}
}

外层循环需要循环n - 1次，每次循环后，最小的数字会到列表的左端，将前n - 1个数字都放到合适的位置后，剩下的最后一个元素自然是最大的，所以只需要循环n-1次而不是n次。

内层循环要寻找应该放在第i个位置的最小值，先假设索引i所在的元素是最小的，如果i + 1之后没有更小的元素，说明i位置的元素就是最小的，保持不变；如果i+1之后存在更小的元素，更新minIndex为更小的元素的索引，通过与minIndex索引位置的元素反复比较，找到最小的元素，与位置i的元素进行交换。

打印的结果：

第1次外循环后的结果 [1 6 9 8 5 7 2]
第2次外循环后的结果 [1 2 9 8 5 7 6]
第3次外循环后的结果 [1 2 5 8 9 7 6]
第4次外循环后的结果 [1 2 5 6 9 7 8]
第5次外循环后的结果 [1 2 5 6 7 9 8]
第6次外循环后的结果 [1 2 5 6 7 8 9]
最终结果 [1 2 5 6 7 8 9]

选择排序的时间复杂度也是O(n2)O(n^2)O(n2)。

插入排序

插入排序就像是打牌的时候，手里的牌是排好序的，每次从桌上摸一张牌，从右到左一张牌一张牌地比较，插入合适的位置。

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2}
	InsertionSort(list)
	fmt.Printf("最终结果 %v\n", list)
}

func InsertionSort(list []int) {
	for i, cur := range list {
		// 将preIdx 设置为已排序序列的最右边元素的索引
		preIdx := i - 1

		/*
			第1次外循环时，preIdx为-1, 不满足preIdx >= 0 的条件，所以以下for循环中的代码块不会执行
			直接执行 list[preIdx+1] = cur 将索引0的元素设置为当前元素，相当于将索引0的元素当作已排序序列的第1个元素
		*/

		/*
			从右到左依次比较元素，如果cur比已排序序列中的元素小，就将已排序的元素往后挪动一位
			重复比较，直到找到一个合适的位置放置cur
		*/
		for preIdx >= 0 && list[preIdx] > cur {
			list[preIdx+1] = list[preIdx]
			preIdx -= 1
		}

		list[preIdx+1] = cur
		fmt.Printf("第%v次外循环后的结果 %v\n", i+1, list)
	}
}

p1指针在每次插入元素前都会指向已经排序的序列的最后一个元素。

最后一次外循环的时候，p1指向索引为5的元素，将要往有序序列中插入元素2，最后一次循环结束，整个列表中的元素就都被排好序了。

第一次外循环的时候，p1指向索引-1，为一个不存在的索引值。从索引-1到索引5，需要遍历len(list)次。

插入排序的时间复杂度为1+1+2+3+...+(n−2)1 + 1 + 2 + 3 + ... + (n - 2)1+1+2+3+...+(n−2) ，也是O(n^2)。（第1个外循环的时候，内层循环的代码块不执行，第2个外循环的时候，内层循环代码块最多执行1次，第3个外循环的时候，内层代码块最多执行2次，依此类推。）

希尔排序

希尔排序是对插入排序的优化，插入排序每次只能移动一个元素到合适的位置，希尔排序将列表分为多个子列表，对每一个子列表进行插入排序，等整个序列中的记录“基本有序”的时候，再对所有元素进行直接插入排序，这样能减少总的移动次，提高效率。

比如上述插入排序例子中，第5次外循环开始要放元素1的时候，列表是这样的[5, 6, 8, 9, 1, 7, 2]，需要把前面的4个元素都往后移动一位，希尔排序就是先将列表处理成大部分都是从小到大排序，减少这种移动，从而提高效率。

希尔排序的时间复杂度在O(nlogn)O(nlogn)O(nlogn)和O(n2)O(n^2)O(n2)之间，根据概率统计得到的时间复杂度是O(n23)O(n^{\frac{2}{3}})O(n32​)。

希尔排序按照一定的gap值，将列表分成子列表，经典的希尔算法的gap值是n21、n22、n23...\frac{n}{2^1}、\frac{n}{2^2}、\frac{n}{2^3}...21n​、22n​、23n​...直到gap的值为1，gap值为1时会对整个列表进行插入排序。gap值不一定是这样变化，也可以是从n/3开始。

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2, -5}
	ShellSort(list)
	fmt.Printf("最终结果 %v\n", list)
}

func ShellSort(list []int) {
	for gap := len(list) / 2; gap > 0; gap /= 2 {
		for i := gap; i < len(list); i++ {
			cur := list[i]
			preIdx := i - gap
			for preIdx >= 0 && list[preIdx] > cur {
				list[preIdx+gap] = list[preIdx]
				preIdx -= gap
			}
			list[preIdx+gap] = cur
		}
	}
}

数组的长度为8，第一次最外层循环的时候gap为8/2 = 4，第二次最外层循环的时候gap为8/4 = 2，第三次最外层循环的时候gap为8/8=1。

下图为gap为4时分的子列表，其中黄色框框中的是一个个拆分出来的子列表，对子列表中的元素进行快速排序。

下图是gap为2时拆分的子列表，同样对子列表中的元素进行快速排序。

gap为1时，直接对整个列表，也就是[1 -5 2 6 5 7 9 8]进行快速排序，排序后的结果为：

[-5 1 2 5 6 7 8 9]。

归并排序

归并排序基于分治法。

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可以得到原问题的解。

归并排序的实现有两种方法：

• 自上而下的递归
• 自下而上的迭代

用递归实现从代码上看比较直观一些，但是需要使用调用栈，需要使用一定的调用栈空间。

递归方式实现

先用递归的方式实现：

func init() {
  list := []int{5, 6, 9, 8, 1, 7, 2}
  sortedList := MergeSort(list)
  fmt.Printf("最终结果 %v\n", sortedList) // 最终结果 [1 2 5 6 7 8 9]
}

func MergeSort(list []int) []int {
  dst := make([]int, len(list))
  copy(dst, list)
  merge(list, dst, 0, len(list))
  return dst
}

func merge(src, dst []int, start, end int) {
  // 如果只有一个元素，直接返回
  if start+1 >= end {
    return
  }

  // 将列表从中间分为两部分，分别进行归并排序
  mid := (start + end) / 2

  merge(dst, src, start, mid) // [start, mid)
  merge(dst, src, mid, end)   // [mid, end)

  var (
    i = start
    j = mid
    k = start
  )

  // 当包含的元素个数 > 1 时，从左右两个子列表中取具体的值放到目标数组中
  for i < mid || j < end {
    /*
      如果右侧的子列表已经遍历完毕，或者
      左侧的子列表没有遍历完毕，并且左侧的子列表的元素小于右侧的子列表的元素
      将目标列表的值设置为左侧子列表的元素。
      否则，设置为右侧子列表的元素。
    */
    if (j == end) || (i < mid && src[i] < src[j]) {
      dst[k] = src[i]
      k += 1
      i += 1
    } else {
      dst[k] = src[j]
      k += 1
      j += 1
    }
  }
}

先分成子问题：

再依次处理子问题（注意箭头的方向是从下到上的）：

因为函数调用栈先进后出的特点，代码的执行的过程可以看作是上图二叉树的后序遍历，先遍历左子树，再遍历右子树，再遍历根节点。

叶子节点只有一个元素，所以在执行merge函数的时候直接返回了，非叶子节点的处理是怎样的呢，以合并[1, 8]和[2, 7] 为例：

具体的排序过程如下：

归并排序的时间复杂度为O(nlogn)O(nlogn)O(nlogn)，空间复杂度为函数调用栈需要的O(logn)O(logn)O(logn)的空间以及辅助列表需要占用的O(n)O(n)O(n)空间，所以空间复杂度为O(n)O(n)O(n)。

迭代方式实现

递归的方式是自上而下的，将整个列表分成两个较小的子列表，子列表再分子列表。

而迭代的方式是自下而上的，先处理小的子列表，再合并成较大的子列表，最后合并成总的列表。

func MergeSortV1(list []int) []int {
	length := len(list)
	src := list
	dst := make([]int, length)
	copy(dst, list)
	for seg := 1; seg < length; seg += seg {
		for start := 0; start < length; start += seg * 2 {
			mid := min(start+seg, length)
			end := min(start+seg*2, length)
			var (
				i = start
				j = mid
				k = start
			)
			for i < mid || j < end {
				if j == end || (i < mid && src[i] < src[j]) {
					dst[k] = src[i]
					k++
					i++
				} else {
					dst[k] = src[j]
					k++
					j++
				}
			}
		}
		src, dst = dst, src
	}
	return src
}

func min(num1, num2 int) int {
	if num1 < num2 {
		return num1
	}
	return num2
}

迭代的代码没有递归的直观。

快速排序

快速排序也是基于分治法的。快速排序选择一个元素作为基准值，然后把比基准值小的元素放在基准值的前面，把比基准值大的元素放在基准值后面，然后对基准值左右两侧的子列表也进行同样的操作，直到子列表中只有一个数字为止。

package sortdata

import (
	"fmt"
	"math/rand"
)

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2}
	sortedList := QuickSort(list)
	fmt.Printf("最终结果 %v\n", sortedList) // 最终结果 [1 2 5 6 7 8 9]
}

func QuickSort(list []int) []int {
	return quickSort(list, 0, len(list)-1)
}

func quickSort(list []int, left, right int) []int {
	if left < right {
		pivot := partition(list, left, right)
		quickSort(list, left, pivot-1)
		quickSort(list, pivot+1, right)
	}
	return list
}

func partition(list []int, start, end int) int {
	random := rand.Intn(end-start+1) + start
	swap(list, random, end)

	small := start - 1
	for i := start; i < end; i++ {
		if list[i] < list[end] {
			small++
			swap(list, i, small)
		}
	}
	small++
	swap(list, small, end)
	return small
}

swap函数最开始写冒泡排序的时候已经定义过：

func swap(list []int, i, j int) {
  if i == j {
    return
  }
  list[i], list[j] = list[j], list[i]
}

如果每次选取的基准值在排序数组中靠近中间的位置，那么时间复杂度就是O(nlogn)O(nlogn)O(nlogn)，如果每次选择的基准值都是最小值或者最大值，时间复杂度为O(n2)O(n^2)O(n2)，在随机选取基准值的情况下，快速排序的平均时间复杂度是O(nlogn)O(nlogn)O(nlogn)。

关于较好的时间复杂度和较差的时间复杂度，可以脑补以下两棵二叉搜索树进行类比：

左边的树选择的基准值依次是4、2、6，右边的树选择的基准值依次是1、2、3、4、5、6。

对[5, 6, 9, 8, 1, 7, 2] 进行快速排序的过程如下：

以对列表[5, 6, 9, 8, 1, 7, 2]进行排序为例，每个子列表的排序过程都是这样的，随机选择一个元素作为基准值，把比基准值小的元素都放到基准值的前面，把比基准值大的元素都放到基准值的后面。

堆排序

堆排序是利用堆这种数据结构的特点来设计的一种排序算法，

堆是一棵完全二叉树，当每个节点的值都大于或等于其子节点的值时，为最大堆（大根堆），当每个节点的值都小于或等于其子节点的值时，为最小堆（小根堆）。

升序排序使用最大堆，降序排序使用最小堆。

完全二叉树可以用数组实现，如果数组中的一个元素的下标为iii，那么它在堆中对应节点的父节点在数组中的下标是(i−1)/2(i - 1)/2(i−1)/2，它的左右子节点在数组中的下标为2i+12i+12i+1和2i+22i+22i+2。

堆排序的平均时间复杂度为O(nlogn)O(nlogn)O(nlogn)。

下面以升序排序为例说明问题，使用的是最大堆。

简单了解下是堆这种数据结构是如何新增节点和删除节点的：

• 新增节点

往堆中新增了一个节点之后，如果这个节点的值小于或等于其父节点的值，那么就是满足最大堆条件的，算法完成；如果这个节点的值大于其父节点的值，就将这个节点与父节点进行交换，再次判断交换后这个节点的值是否大于其父节点的值，如果大于，又与父节点进行交换，直到这个节点的值小于或等于父节点的值，或者这个节点已经成为了根节点。

• 删除节点

删除根节点，为了避免直接删除节点后一棵树变成两棵无连接的树，所以不能最直接删除根节点。

先将最后一个节点A复制到根节点，此时最后一个节点成为了新的根节点，如果此时树只包含一个节点，算法完成；否则判断节点A的值是否大于或等于其左右子节点，如果是，算法完成；如果节点A只包含左子节点，左子节点的值比节点A大，那么将节点A与它的左子节点交换，如果节点A包含左右子节点，就将节点A和左右子节点中较大的那个值交换，直到节点A的值大于或等于其左右子节点，或者节点A成为叶子节点，算法终止。

堆排序的代码实现：

package sortdata

import "fmt"

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2}
	sortedList := HeapSort(list)
	fmt.Printf("最终结果 %v\n", sortedList) // 最终结果 [1 2 5 6 7 8 9]
}

func HeapSort(list []int) []int {
	length := len(list)
	buildMaxHeap(list, length)
	for i := length - 1; i >= 1; i-- {
		swap(list, 0, i)
		length -= 1
		heapify(list, 0, length)
	}
	return list
}

func buildMaxHeap(list []int, length int) {
	for i := length/2 - 1; i >= 0; i-- {
		heapify(list, i, length)
	}
}

func heapify(list []int, i, length int) {
	left := 2*i + 1
	right := 2*i + 2
	largest := i
	if left < length && list[left] > list[largest] {
		largest = left
	}
	if right < length && list[right] > list[largest] {
		largest = right
	}
	if largest != i {
		swap(list, i, largest)
		heapify(list, largest, length)
	}
}

整体的排序过程：

以将[5, 6, 9, 8, 1, 7, 2] 构造为最大堆[9 8 7 6 1 5 2]为例，heapify方法构造最大堆的过程为：

图中p1一开始指向的是索引2(即7/2 - 1)的位置，从length/2 - 1的位置开始，逐个往前遍历元素，判断是否需要交换元素，为什么不从最后一个元素开始，而是从中间位置的元素开始呢，因为叶子节点没有子节点，所以每个叶子节点都是满足最大堆条件的，不需要构建堆。最后一个元素的索引为length - 1，它的父节点就是最后一个非叶子节点（索引为(length - 1) - 1 / 2 = length/2 - 1 ），从最后一个非叶子节点开始逐个往前遍历元素即可。

计数排序

如果整数的范围比较小，比如年龄这种数值，就可以用计数排序。利用数组的索引是有顺序的，通过数组中索引的大小对应数字的大小，数组中存储元素出现的次数，然后按照顺序将对应的元素取出来。

package sortdata

import (
	"fmt"
	"math"
)

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2}
	sortedList := CountingSort(list)
	fmt.Printf("最终结果 %v\n", sortedList) // 最终结果 [1 2 5 6 7 8 9]
}

func CountingSort(list []int) []int {
	minNum := math.MaxInt
	maxNum := math.MinInt
	for _, val := range list {
		minNum = min(minNum, val)
		maxNum = max(maxNum, val)
	}
	counts := make([]int, maxNum-minNum+1)
	for _, val := range list {
		counts[val-minNum] += 1
	}

	i := 0
	for num := minNum; num <= maxNum; num++ {
		for counts[num-minNum] > 0 {
			list[i] = num
			i++
			counts[num-minNum] -= 1
		}
	}
	return list
}

func max(num1, num2 int) int {
	if num1 > num2 {
		return num1
	}
	return num2
}

如果数组的长度为nnn，数组的范围为kkk，那么计数排序的时间复杂度是O(n+k)O(n+k)O(n+k)。由于需要创建一个长度为O(k)O(k)O(k)的辅助数组，因此空间复杂度为O(k)O(k)O(k)。

找出最大值和最小值的循环需要花费n的时间，组织计数数组counts需要花费n的时间，将元素从计数数组中取出来，外层循环需要花费k的时间，内层循环总共加起来需要花费n的时间，所以计数排序的时间复杂度为O(n+k)O(n+k)O(n+k)。

桶排序

桶排序是计数排序的升级版，它利用了函数的映射关系，将数组分到有限数量的桶里，每个桶再分别排序（可以继续使用桶排序，也可以使用别的排序算法）。

package sortdata

import (
	"fmt"
	"math"
)

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2, 26, 12}
	sortedList := BucketSort(list)
	fmt.Printf("最终结果 %v\n", sortedList) // 最终结果 [1 2 5 6 9 8 7 12 26]
}

func BucketSort(list []int) []int {
	length := len(list)
	maxNum := getMaxInList(list)
	buckets := make([][]int, length)

	var index int
	for _, val := range list {
		index = (length - 1) * val / maxNum
		buckets[index] = append(buckets[index], val)
	}

	pos := 0
	for i := 0; i < length; i++ {
		bl := len(buckets[i])
		if bl > 0 {
			buckets[i] = sortInBucket(buckets[i])
			copy(list[pos:], buckets[i])
			pos += bl
		}
	}
	return list
}

// 桶内的排序选择使用插入排序
func sortInBucket(bucket []int) []int {
	for i, cur := range bucket {
		preIdx := i - 1
		for preIdx >= 0 && bucket[i] > cur {
			bucket[preIdx+1] = bucket[preIdx]
			preIdx -= 1
		}
		bucket[preIdx+1] = cur
	}
	return bucket
}

func getMaxInList(list []int) int {
	maxNum := math.MinInt
	for _, val := range list {
		if val > maxNum {
			maxNum = val
		}
	}
	return maxNum
}

index = (length - 1) * val / maxNum这个方法得到的值是0 ~ (length - 1)范围内的数字，对应着数组的索引。

桶排序的时间复杂度接近O(n)O(n)O(n)。把n个数字分在m个桶里，每个桶里的数据就是k=nmk = \frac{n}{m}k=mn​，每个桶内排序的时间复杂度是O(klogk)O(klogk)O(klogk)，总的时间复杂度为m×O(klogk)=m×O(nm×log(nm))=O(nlog(nm))m \times O(klogk) = m \times O(\frac{n}{m} \times log(\frac{n}{m})) = O(nlog(\frac{n}{m}))m×O(klogk)=m×O(mn​×log(mn​))=O(nlog(mn​))，桶的个数接近数字的个数时，log(nm)log(\frac{n}{m})log(mn​)是一个很小的常数，所以桶排序的时间复杂度接近O(n)O(n)O(n)。

基数排序

基数排序将整数按位数切割成不同的数字，然后按照每个位数分别进行比较。

计数排序、桶排序和基数排序都使用了桶的概念，基数排序根据值的每位的数字来分配桶，计数排序每个桶只存储单一键值，桶排序每个桶存储一定范围的数值。

package sortdata

import (
	"fmt"
	"strconv"
)

func init() {
	list := []int{5, 16, 9, 18, 15, 7, 2, 26, 12}
	sortedList := RadixSort(list)
	fmt.Printf("最终结果 %v\n", sortedList) // 最终结果 [2 5 7 9 12 15 16 18 26]
}

func RadixSort(list []int) []int {
	maxDigit := maxBit(list)
	mod, div := 10, 1
	for i := 0; i < maxDigit; i++ {
		buckets := [10][]int{}
		for _, num := range list {
			bucket := (num % mod) / div
			buckets[bucket] = append(buckets[bucket], num)
		}
		index := 0
		for _, bucket := range buckets {
			for _, num := range bucket {
				list[index] = num
				index++
			}
		}

		mod *= 10
		div *= 10
	}
	return list
}

func maxBit(list []int) int {
	maxVal := 0
	for _, val := range list {
		if val > maxVal {
			maxVal = val
		}
	}
	return len(strconv.Itoa(maxVal))
}

基数排序的时间复杂度是O(d(n+k))O(d(n+k))O(d(n+k))，nnn是元素的个数，ddd是数字的位数（比如代码中使用的数字列表中的数字最多有2位），kkk是每个数字的取值范围（比如10进制数的kkk值就是10，取值范围是0～9）。

查找

顺序查找

最好情况目标位于列表的第一个位置，只比较一次；最坏情况是目标位于列表的最后位置，要比较nnn次；平均情况下在列表的中间找到，需要比较n/2n/2n/2次，所以顺序搜索算法的时间复杂度是O(n)O(n)O(n)。

package searchdata

import "fmt"

func init() {
	list := []int{5, 6, 9, 8, 1, 7, 2}
	sr := SequentialSearch(list, 20)
	fmt.Printf("最终结果 %v\n", sr)
	list1 := []int{10, 20, 30, 40, 50, 60, 70}
	sr1 := OrderedSequentialSearch(list1, 211)
	fmt.Printf("最终结果 %v\n", sr1)
}

func SequentialSearch(list []int, target int) bool {
	pos := 0
	found := false
	for pos < len(list) && !found {
		if list[pos] == target {
			return true
		}
		pos += 1
	}
	return found
}

// 如果列表是有序的，只要遇到大于目标的元素，就知道后续的元素都不会再等于目标了，直接返回
func OrderedSequentialSearch(list []int, target int) bool {
	pos := 0
	found := false
	for pos < len(list) && !found {
		if list[pos] == target {
			return true
		}
		if list[pos] > target {
			return false
		}
		pos += 1
	}
	return found
}

二分查找

如果要进行查找的列表是排序的，可以使用二分查找。

二分查找先比较列表中间的位置的元素是否等于目标元素，如果等于就返回true，如果中间的元素大于目标元素，就在后半部分找，中间的元素小于目标元素就在前半部分找。二分查找的时间复杂度是O(logn)O(logn)O(logn)。

package searchdata

import "fmt"

func init() {
	list := []int{10, 20, 30, 40, 50, 60, 70}
	sr := BinarySearch(list, 31)
	fmt.Printf("最终结果 %v\n", sr)
}

func BinarySearch(list []int, target int) bool {
	left := 0
	right := len(list) - 1
	found := false
	for left <= right && !found {
		mid := (left + right) / 2
		if list[mid] == target {
			return true
		} else {
			if target < list[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
	}
	return found
}

哈希（散列）查找

哈希查找就是从哈希表中查找数据时用的查找方法。

使用求余的哈希函数，选择线性探测的方式简单实现一个哈希表：

package searchdata

import "fmt"

func init() {
	ht := NewHashTable[string, int]()
	ab := "ab"
	ba := "ba"
	c := "c"
	d := "d"
	e := "e"
	ht.Put(&ab, 5)
	ht.Put(&ba, 6)
	ht.Put(&c, 9)
	ht.Put(&d, 8)
	fmt.Println(ht.GetKeys(), ht.Vals)
	found, val := ht.Get(&c)
	fmt.Printf("键是否存在 %v 对应的值是 %v\n", found, val)
	found1, val1 := ht.Get(&e)
	fmt.Printf("键是否存在 %v 对应的值是 %v\n", found1, val1)
}

type HashTable[K string, V any] struct {
	Size int  // 初始容量
	Keys []*K // 存储键
	Vals []V  // 存储值
	Len  int  // 键值对的个数
}

// 为了简化流程，只支持字符串类型的键值，假如需要扩展其他类型，可以修改类型参数
func NewHashTable[K string, V any]() HashTable[K, V] {
	size := 3 // 容器的初始尺寸设置为3
	ht := HashTable[K, V]{
		Size: size,
		Keys: make([]*K, size), // 这里为了区分空值和值不存在的情况，使用的指针类型的数据，这样的设计有些奇怪，但是又找不到什么更好的办法
		Vals: make([]V, size),
		Len:  0, // 初始的元素个数为0
	}
	return ht
}

// 扩容
func (h *HashTable[K, V]) Resize(newSize int) {
	newKeys := make([]*K, newSize)
	newVals := make([]V, newSize)
	h.Size = newSize

	copy(newKeys, h.Keys)
	copy(newVals, h.Vals)

	h.Keys = make([]*K, newSize)
	h.Vals = make([]V, newSize)

	h.Len = 0
	for i, key := range newKeys {
		if key != nil {
			h.Put(key, newVals[i])
		}
	}
}

func (h *HashTable[K, V]) Put(key *K, val V) {
	if h.Size == h.Len { // 元素个数达到容量时，需要先进行扩容
		h.Resize(h.Size * 2)
	}

	hashVal := h.Hash(key, h.Size)
	// hashVal的位置没有值的时候直接把值放在这个位置
	if h.Keys[hashVal] == nil {
		h.Keys[hashVal] = key
		h.Vals[hashVal] = val
		h.Len += 1
	} else {
		// 如果 hashVal位置已经有值了，就继续往后找，直到找到一个空位，或者已经存储的同样名字的key
		next := h.ReHash(hashVal, h.Size)
		for h.Keys[next] != nil && h.Keys[next] != key {
			next = h.ReHash(next, h.Size)
		}
		// 有空位就将键值放在空位
		if h.Keys[next] == nil {
			h.Keys[next] = key
			h.Vals[next] = val
			h.Len += 1
		} else { // 已经有这个键就覆盖这个键对应的值
			h.Vals[next] = val
		}
	}
}

func (h *HashTable[K, V]) Hash(key *K, size int) int {
	sum := 0
	k := *key
	for _, a := range k {
		sum += int(a)
	}
	return sum % size
}

// 通过线性探测的方式来处理冲突
func (h *HashTable[K, V]) ReHash(oldHash int, size int) int {
	return (oldHash + 1) % size
}

func (h *HashTable[K, V]) Get(key *K) (found bool, val V) {
	start := h.Hash(key, len(h.Keys))

	pos := start
	// 一直往后查找，直到找到，或者找了一圈都没找到
	for h.Keys[pos] != nil {
		if h.Keys[pos] == key {
			found = true
			val = h.Vals[pos]
			return found, val
		} else {
			pos = h.ReHash(pos, len(h.Keys))
			if pos == start {
				return found, val
			}
		}
	}
	return found, val
}

func (h *HashTable[K, V]) GetKeys() []K {
	keys := []K{}
	for _, key := range h.Keys {
		if key != nil {
			keys = append(keys, *key)
		} else {
			keys = append(keys, "-")
		}
	}
	return keys
}

哈希查找的时间复杂度一般是O(1)O(1)O(1)。

哈希表的存储过程。为了看起来直观，图中keys列表中写的是字符串（其实存储的是字符串的地址）：

哈希查找的过程，以查找键c为例子吧：

源码地址

参考文章

1. 十大经典排序算法：www.runoob.com/w3cnote/bub…
2. 希尔排序：www.runoob.com/data-struct…
3. 桶排序：www.bookstack.cn/read/For-le…
4. 基数排序：www.lifezb.com/golang/17.h…
5. 《剑指offer专项突破版》