Hello Golang

计数排序（Counting Sort）

计数排序是一种非比较排序算法，适用于对整数范围有限的元素进行排序。它的基本思想是通过统计数组中每个元素的出现次数来进行排序。计数排序的时间复杂度为 $O(n+k)$，其中 $n$ 是待排序的元素个数，$k$ 是元素的取值范围。由于不需要比较元素之间的大小关系，计数排序在某些情况下可以非常高效。

1. 计数排序的基本概念

计数排序的基本步骤如下：

1. 确定范围: 找出待排序数组中的最大值和最小值，确定元素的取值范围。
2. 统计出现次数: 创建一个计数数组，用于记录每个元素的出现次数。
3. 累加计数: 将计数数组中的元素进行累加，以确定每个元素在排序后的数组中的位置。
4. 构建排序结果: 根据累加后的计数数组，重新构建排序后的数组。

2. 计数排序的算法步骤

以下是计数排序的详细步骤：

1. 确定范围:

   • 找到待排序数组的最大值和最小值。
   • 计算元素的取值范围 $k=\text{最大值}-\text{最小值}+1$。

2. 统计出现次数:

   • 创建一个大小为 $k$ 的计数数组 count，初始化为 0。
   • 遍历待排序数组，对每个元素在计数数组中对应的位置进行计数。

3. 累加计数:

   • 对计数数组进行累加，计算每个元素在排序后的数组中的位置。
   • 累加的计数数组可以用于确定元素在排序后的数组中的最终位置。

4. 构建排序结果:

   • 遍历待排序数组，将元素放入排序后的数组中，根据累加后的计数数组确定位置。

3. 计数排序的时间复杂度和空间复杂度

• 时间复杂度:

  • 最坏情况: $O(n+k)$，其中 $n$ 是待排序元素的个数，$k$ 是元素的取值范围。
  • 最佳情况: $O(n+k)$，在任何情况下，计数排序的时间复杂度为 $O(n+k)$。
  • 平均情况: $O(n+k)$，时间复杂度不受输入数据分布的影响。

• 空间复杂度:

  • 空间复杂度: $O(n+k)$，需要额外的空间来存储计数数组和排序结果数组。

4. 计数排序的代码示例

以下是使用 Go 语言实现的计数排序算法：

package main

import "fmt"

// CountingSort 对整数切片进行计数排序
func CountingSort(arr []int) {
    if len(arr) == 0 {
        return
    }

    // 找到最大值和最小值
    maxVal, minVal := arr[0], arr[0]
    for _, v := range arr {
        if v > maxVal {
            maxVal = v
        }
        if v < minVal {
            minVal = v
        }
    }

    // 创建计数数组
    rangeSize := maxVal - minVal + 1
    count := make([]int, rangeSize)

    // 统计出现次数
    for _, v := range arr {
        count[v-minVal]++
    }

    // 计算累加计数
    for i := 1; i < len(count); i++ {
        count[i] += count[i-1]
    }

    // 构建排序结果
    output := make([]int, len(arr))
    for i := len(arr) - 1; i >= 0; i-- {
        output[count[arr[i]-minVal]-1] = arr[i]
        count[arr[i]-minVal]--
    }

    // 将排序结果复制到原数组
    copy(arr, output)
}

func main() {
    arr := []int{4, 2, 2, 8, 3, 3, 1}
    fmt.Println("Original array:", arr)
    CountingSort(arr)
    fmt.Println("Sorted array:", arr)
}

5. 计数排序的优缺点

优点:

• 线性时间复杂度: 当元素的取值范围 $k$ 不远大于元素个数 $n$ 时，计数排序可以实现线性时间复杂度 $O(n+k)$。
• 稳定排序: 计数排序是稳定的排序算法，相同值的元素保持原有的相对位置。
• 简单实现: 计数排序的实现较为简单，不需要复杂的比较操作。

缺点:

• 空间复杂度高: 对于取值范围很大的情况，计数排序需要大量的额外空间，可能不适用于大范围的值。
• 不适用于浮点数或负数: 计数排序主要用于处理整数，处理浮点数或负数时需要额外的处理步骤。
• 受限于取值范围: 当取值范围 $k$ 很大时，计数排序的空间复杂度会显著增加，影响性能。

总结

计数排序是一种高效的非比较排序算法，特别适用于整数范围有限的场景。其时间复杂度为 $O(n+k)$，并且可以实现稳定排序。虽然计数排序在处理大范围的值时空间复杂度较高，但其简单易实现和高效的性能使其在特定应用场景中非常有用。