桶排序 基数排序 go代码

### 关于桶排序和基数排序的Go语言实现

#### 桶排序 (Bucket Sort)

桶排序是一种分配排序算法，工作原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用不同的排序算法或是以递归方式继续使用桶排序）。这种分割的结果是一个非常快速有效的排序方法。

package main

import (
	"fmt"
	"math"
)

func bucketSort(slice []float64) {
	if len(slice) == 0 {
		return
	}

	minValue := slice[0]
	maxValue := slice[0]

	for _, value := range slice { // 找出最大最小值
		if value < minValue {
			minValue = value
		} else if value > maxValue {
			maxValue = value
		}
	}

	bucketCount := int(math.Floor(maxValue - minValue)) + 1
	buckets := make([][]float64, bucketCount)

	for _, value := range slice { // 将元素放入对应的桶中
		index := int(math.Floor(value - minValue))
		buckets[index] = append(buckets[index], value)
	}

	result := make([]float64, 0, len(slice))

	for _, bucket := range buckets { // 对每一个桶中的元素进行排序并合并结果
		if len(bucket) != 0 {
			insertionSort(bucket)
			result = append(result, bucket...)
		}
	}

	copy(slice, result)
}

// 插入排序用于对各个桶内元素排序
func insertionSort(nums []float64) {
	for i := 1; i < len(nums); i++ {
		key := nums[i]
		j := i - 1
		for j >= 0 && nums[j] > key {
			nums[j+1] = nums[j]
			j--
		}
		nums[j+1] = key
	}
}

func main() {
	slice := []float64{0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}
	fmt.Println("Original Slice:", slice)
	bucketSort(slice)
	fmt.Println("Sorted Slice :", slice)
}

此代码实现了浮点数类型的桶排序[^1]。

#### 基数排序 (Radix Sort)

基数排序基于这样的想法：通过比较数字的不同位上的数值来进行排序；它可以从最低有效位(LSD)开始或最高有效位(MSD)，这里展示的是LSD版本。

package main

import "fmt"

const base = 10

func countingSortByDigit(array []int, exp int) {
	n := len(array)
	output := make([]int, n)
	count := make([]int, base)

	for i := 0; i < n; i++ {
		index := (array[i] / exp) % base
		count[index]++
	}

	for i := 1; i < base; i++ {
		count[i] += count[i-1]
	}

	for i := n - 1; i >= 0; i-- {
		index := (array[i] / exp) % base
		output[count[index]-1] = array[i]
		count[index]--
	}

	for i := range output {
		array[i] = output[i]
	}
}

func radixSort(array []int) {
	maxElement := getMax(array)

	exp := 1
	for maxElement/exp > 0 {
		countingSortByDigit(array, exp)
		exp *= base
	}
}

func getMax(array []int) int {
	max := array[0]
	for _, element := range array {
		if element > max {
			max = element
		}
	}
	return max
}

func main() {
	arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
	fmt.Printf("Unsorted Array: %v\n", arr)
	radixSort(arr)
	fmt.Printf("Sorted Array:   %v\n", arr)
}

这段程序展示了如何利用计数排序作为子过程来完成整型数据的基数排序。