用 Go 语言实现常见的十大排序算法（上）

十大常见的排序算法有：

冒泡排序（Bubble Sort）
选择排序（Selection Sort）
插入排序（Insertion Sort）
希尔排序（Shell Sort）
归并排序（Merge Sort）
桶排序（Bucket Sort）
快速排序（Quick Sort）
堆排序（Heap Sort）
计数排序（Counting Sort）
基数排序（Radix Sort）

一个一个说

冒泡排序

冒泡排序是一种简单的排序算法，通过重复比较相邻元素并交换位置从而确定一个元素的位置，直到没有需要交换的元素

大体有两种写法，一种是从前往后比，每次确定一个较大值；一种是从后往前比，每次确定一个较小值

 func BubbleSort(arr []int) {n := len(arr)// 1、每次确定一个较大值的位置for i := 0; i < n-1; i++ {for j := 0; j < n-i-1; j++ {if arr[j] > arr[j+1] {// 如果当前值大于下一位，就交换arr[j], arr[j+1] = arr[j+1], arr[j]}}}// 2、每次确定一个较小值的位置for i := 0; i < n-1; i++ {for j := n - 1; j > i; j-- {if arr[j] < arr[j-1] {// 当前值小于上一位，就交换arr[j], arr[j-1] = arr[j-1], arr[j]}}}return arr}

冒泡排序是稳定的，稳定是指相同元素在排序完后相对位置不变，例如切片[2, 1, 3, 1, 5]，经过排序后第一个 "1" 还是在第二个 "1" 之前

冒泡排序的平均时间复杂度是O(n^2)，在元素近似有序的情况下，会有很多没有必要的比较和交换，一种优化思路是使用标志位，如果一次循环没有发生任何元素交换，就表示切片已经有序了，直接退出就可以，不需要再往下比较，这在元素近似有序的情况下会很省时间

 func BubbleSort(arr []int) {n := len(arr)// 使用标志位和缩小比较范围优化for i := 0; i < n-1; i++ {swapped := false // 标志位，记录这次外层循环中是否有过交换for j := 0; j < n-i-1; j++ {if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]swapped = true}}// 如果一次交换都没有，说明数组已经有序了，没有必要再循环下去if !swapped {break}}return arr}

选择排序

选择排序的思路是，反复选择未排序部分的最小（大）元素，把它放到已排序部分的末尾

 func selectionSort(arr []int) {n := len(arr)for i := 0; i < n-1; i++ {// 最小元素下标minIndex := ifor j := i + 1; j < n; j++ {// 找出待排序元素中最小的一个if arr[j] < arr[minIndex] {minIndex = j}}// 把找出来的最小元素放到排序好的元素末尾arr[i], arr[minIndex] = arr[minIndex], arr[i]}return arr}

特点：时间复杂度是 O(n^2)、不稳定的(比如待排序元素为 [5, 5, 3]，把 3 和 5 交换就完成了排序，但是原先在之前的 5 变成了后面)、没有明显的优化思路，

插入排序

插入排序的大概思路是，构建一个排序好的数据，把新的元素插入到适当的位置中去

 func insertionSort(arr []int) {n := len(arr)for i := 1; i < n; i++ {// 待排序元素compare := arr[i]// 排序好的元素右边界值，因为 arr[i] 是待比较元素，所以 [0,i-1] 这一段数据是已经排好序的j := i - 1// 如果元素大于待排序元素就往右挪 腾出位置for j >= 0 && arr[j] > compare {arr[j+1] = arr[j]j--}// 把元素放到合适的位置arr[j+1] = compare}}

特点：时间复杂度为 O(n^2)、稳定，适合在元素基本有序时使用，有序时只需要少量判断就可以确定正确的位置

归并排序

归并排序是一种分治算法，把数组逐次对半分，分别对两半进行排序，然后把排序好的两半合并在一起

 // 递归地拆分数组并进行归并func mergeSort(arr []int, l, r int) {// l == r 时退出 因为此时只有一个元素if l < r {// 求中间值m := (r-l)/2 + l// 递归左半边mergeSort(arr, l, m)// 递归右半边mergeSort(arr, m+1, r)// 把排好序地两半合并merge(arr, l, m, r)}}// 把两个已经排好序的子数组合并成一个有序数组func merge(arr []int, l, m, r int) {// 创建切片存放左右两半元素leftSize := m - l + 1 // 把中间值归左半边rightSize := r - mleftArr := make([]int, leftSize)rightArr := make([]int, rightSize)// 复制元素 注意是左开右闭区间copy(leftArr, arr[l:m+1])copy(rightArr, arr[m+1:r+1])// 遍历左右半边元素 挑出小的写回到待排序数组中i, j, k := 0, 0, lfor i < leftSize && j < rightSize {if leftArr[i] <= rightArr[j] {arr[k] = leftArr[i]i++} else {arr[k] = rightArr[j]j++}k++}// 复制剩余元素 不处理两半不均等时会漏元素for i < leftSize {arr[k] = leftArr[i]i++k++}for j < rightSize {arr[k] = rightArr[j]j++k++}}

单看代码有点难理解，用一个例子来看排序的整个过程

比如现在有切片 arr = [2, 3, 1, 5]

通过 mergeSort(arr, 0, len(arr) - 1) 排序，整个流程为：

看图示流程就会比较清晰，先把左半边元素拆到底，逐个合并，使左半边元素有序，再处理右半边，把右半边也处理完，再合并左右半边，最终排序完成

特点：时间复杂度为 O(n log n)、稳定

改进思路：在元素量较小的时候，比如 10 或 20 个元素，使用插入排序比双指针要稍快一点，可以在排序过程中增加一个阈值，当子切片的长度小于该值时，使用插入排序

桶排序

大概思路是生成一些桶，把元素分布到不同的桶中，对每个桶再单独进行排序（可以使用任何排序方法，选择排序、插入排序等等），再将元素依次取出，需要注意，后一个桶中的每一个元素都要大于前一个桶中所有数据

核心点有两个：怎么确定桶的个数？哪个元素放哪个桶如何确定，即桶的索引如何确定？

对于第一个问题，桶排序适用的场景是分布均匀的浮点数，因为浮点数计算桶的索引方便一点，如果分布不均匀，可能会造成某些桶包含大量元素，某些桶只包含很少的元素，导致算法效率降低，一般来说，根据元素个数 n，桶的个数一般在 n^1/2 - n 之间

第二个问题，桶的索引计算一般基于最小值和最大值来完成，一个简单的索引计算方法：

 index := int((value - minValue) / (maxValue - minValue) * float64(bucketCount))

value: 当前要处理的元素
minValue: 在整个数组中的最小值
maxValue: 在整个数组中的最大值
bucketCount: 总的桶的数量

简单解释这条公式，(value - minValue) / (maxValue - minValue) 意思是当前值减去最小值并除以范围(最大值和最小值的差值)，把元素的值定位到 [0, 1] 的范围中，这样就可以获得元素相对于整个数据的位置，拿这个值乘以桶的总数，然后用 int() 转换为 int 类型作为桶的下标索引，这样就完成了简单的定位操作

完整代码：

 func bucketSort(arr []float64, bucketCount int) []float64 {if len(arr) == 0 {return arr}// 找最大值和最小值minValue, maxValue := arr[0], arr[0]for _, value := range arr {if value < minValue {minValue = value}if value > maxValue {maxValue = value}}// 初始化桶 用切片表示buckets := make([][]float64, bucketCount)// 把元素分配到桶里for _, value := range arr {// 用公式计算桶的索引index := int((value - minValue) / (maxValue - minValue) * float64(bucketCount))// 如果计算出的索引越界了 手动减一if index >= bucketCount {index = bucketCount - 1}// 把元素追加到对应的桶里buckets[index] = append(buckets[index], value)}//  对每个桶进行排序 用哪种排序方法都可以 这里用自带的排序函数sortedArr := make([]float64, 0)for _, bucket := range buckets {sort.Float64s(bucket)sortedArr = append(sortedArr, bucket...)}return sortedArr}