1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| func main() { array := []int{31,16,37,2,13,32,10,27,7,42,29,18,28,12,9,} BucketSort(array) fmt.Println("BucketSort:",array) } func sortInBucket(bucket []int) { length := len(bucket) if length == 1 {return} for i := 1; i < length; i++ { backup := bucket[i] j := i -1; for j >= 0 && backup < bucket[j] { bucket[j+1] = bucket[j] j -- } bucket[j + 1] = backup } }
func getMaxInArr(arr []int) int{ max := arr[0] for i := 1; i < len(arr); i++ { if arr[i] > max{ max = arr[i]} } return max }
func BucketSort(arr []int) []int { num := len(arr) max := getMaxInArr(arr) buckets := make([][]int, num) index := 0 for i := 0; i < num; i++ { index = arr[i] * (num-1) /max buckets[index] = append(buckets[index], arr[i]) } tmpPos := 0 for i := 0; i < num; i++ { bucketLen := len(buckets[i]) if bucketLen > 0{ sortInBucket(buckets[i]) copy(arr[tmpPos:], buckets[i]) tmpPos += bucketLen } } return arr
|