排序算法-桶排序

桶排序很适用于有 0~100 个数, 然后打乱顺序, 重新分配. 不过如果给定的数据范围差距很大, 桶排序的算法效率变低.

步骤

申请 n 个桶,根据需求
遍历一个给定的数组,找到最大值和最小值
遍历数组,假设遍历的值为num,按照公式floor((num - min) / n)即可得知放入哪个桶
如果桶中已存在元素,拉出一个链表,并且按照从小到大的顺序
重复 3,4 直至把所有元素装入桶中
遍历所有桶中的链表, 直接把每一个元素载入数组,排序即可完成

package main

import (
    "fmt"
    "math"
)

func main()  {


    data := []int{111, 9, 2, 4, 9, 3, 3, 5, 7, 1, 8, 2, 11, 22, 99, 192}

    fmt.Println(BucketSort(data, 4))
}

func BucketSort(data []int, buckets int) []int {

    if len(data) == 0 {
        return data
    }

    // find min and max number
    min, max := data[0], data[0]
    for _, number := range data {

        if number < min {
            min = number
            continue
        }

        if number > max {
            max = number
        }
    }


    bucketChunk := (max - min + 1) / buckets
    bucketLinks := make([]*LinkList, buckets)

    // 把所有数字放入桶中并且排序
    for _, number := range data {

        // 找到放入的桶中
        bucketIndex := int(math.Floor(float64((number - min) / bucketChunk)))

        if bucketLinks[bucketIndex] == nil {
            bucketLinks[bucketIndex] = &LinkList{}
        }

        bucketLinks[bucketIndex].put(number)
    }

    // 再遍历所有桶直接连接
    index := 0
    sortData := make([]int, len(data))
    for _, bucket := range bucketLinks {

        if bucket == nil {
            continue
        }


        head := bucket.head
        for head != nil {

            sortData[index] = head.data
            index ++
            head = head.next
        }
    }

    return sortData
}

type LinkList struct {

    head *Node
}

type Node struct {

    data int
    next *Node
}

func (b *LinkList) put(num int)  {

    if b.head == nil {

        b.head = &Node{num, nil}
        return
    }

    if b.head.data > num {
        b.head = &Node{num, b.head}
        return
    }

    // 排序插入
    head := b.head
    for head.next != nil {

        if head.next.data > num {

            // 连接链表
            head.next = &Node{num, head.next};
            return
        }

        head = head.next;
    }

    head.next = &Node{num, nil}
}