12. 进阶排序算法——木桶排序（golang）

木桶排序

木桶排序的核心思想

关键词：分桶

将数组分到有限数量的桶子里，每个桶子再个别排序。

其实木桶排序和基数排序很相似，区别在于基数排序需要多趟桶排序，并且记录当前排序的结果。

代码实现

// 获取数组最大值
func SelectSortMax(arr []int) (max int, err error) {

	// 数组长度
	length := len(arr)

	// 空数组
	if length == 0 {
		//err = errors.New("空数组")
		return
	}

	// 初始化最大值
	max = arr[0]

	// 遍历，比较
	for i := 1; i < length; i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}

	return
}

// 选择排序
func SelectSort(arr []int) []int {

	// 数组长度
	length := len(arr)

	// 数组为空或者只有一个元素
	if length <= 1 {
		return arr
	}

	// 遍历，比较
	for i := 0; i < length-1; i++ {

		// 标记索引
		min := i

		// 找到最小值的索引
		for j := i + 1; j < length; j++ {
			if arr[min] > arr[j] {
				min = j
			}
		}

		// 交换
		if i != min {
			arr[i], arr[min] = arr[min], arr[i]
		}
		//fmt.Println(arr)
	}

	return arr
}


func BucketSort(arr []int) []int {

	// 数组长度
	length := len(arr)
	if length <= 1 {
		return arr
	}

	// 桶的数量
	num := length

	max,_ := SelectSortMax(arr)

	index := 0

	// 创造二维数组
	buckets := make([][]int, num)

	for i := 0; i < length; i++ {
		index = arr[i] * (num-1) / max
		// 木桶计数加1
		buckets[index] = append(buckets[index], arr[i])
	}
	fmt.Println(buckets)

	// 木桶排序
	tmppose := 0
	for i := 0; i < num; i++ {

		// 某一段的长度
		bucketslen := len(buckets[i])

		// 桶里有内容，追加到数组里面
		if bucketslen > 0 {
			buckets[i] = SelectSort(buckets[i])
			copy(arr[tmppose:], buckets[i])
			tmppose += bucketslen
		}
	}

	return arr
}