go 桶排序

338次阅读

共计 1124 个字符,预计需要花费 3 分钟才能阅读完成。

概念

桶排序的基本思想是将待排序数据分成一些有序的桶,每个桶里的数据再进行排序,最后将所有的桶中的数据依次取出,构成有序序列。步骤如下:

  1. 首先,我们需要确定桶的数量和每个桶的范围。这里我们选择桶的数量等于待排序数据的数量,并且每个桶的范围是一个固定的值。
  2. 接下来,我们需要将待排序数据分配到对应的桶中。
  3. 然后,对每个桶中的数据进行排序。
  4. 最后,我们将所有桶中的数据依次取出,构成有序序列。

代码实现

package main

import ("fmt")

func bucketSort(arr []int, bucketSize int) []int {if len(arr) == 0 {return arr}

    // 获取最大值和最小值
    minVal, maxVal := arr[0], arr[0]
    for _, val := range arr {
        if val < minVal {minVal = val} else if val > maxVal {maxVal = val}
    }

    // 计算桶的数量
    bucketCount := (maxVal-minVal)/bucketSize + 1
    buckets := make([][]int, bucketCount)

    // 将数据分配到对应的桶中
    for _, val := range arr {index := (val - minVal) / bucketSize
        buckets[index] = append(buckets[index], val)
    }

    // 对每个桶中的数据进行排序
    result := make([]int, 0)
    for _, bucket := range buckets {if len(bucket) > 0 {if len(bucket) > 1 {bucket = bucketSort(bucket, bucketSize)
            }
            result = append(result, bucket...)
        }
    }

    return result
}

func main() {arr := []int{5, 3, 1, 7, 9, 4, 6, 8, 2}
    fmt.Println("Unsorted array:", arr)

    sortedArr := bucketSort(arr, 2)
    fmt.Println("Sorted array:", sortedArr)
}

在上面的代码中,我们首先获取待排序数据的最大值和最小值,然后计算桶的数量。接下来,我们将待排序数据分配到对应的桶中,再对每个桶中的数据进行排序。最后,我们将所有桶中的数据依次取出,构成有序序列。

bucketSort 函数中,我们首先检查待排序数据是否为空,如果是,则直接返回。然后,我们计算每个桶的范围,并创建相应数量的桶。接下来,我们将待排序数据分配到对应的桶中,再对每个桶中的数据进行排序。最后,我们将排序后的数据添加到结果数组中,并返回结果数组。

正文完
 
dkp
版权声明:本站原创文章,由 dkp 2023-04-16发表,共计1124字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。