-
Notifications
You must be signed in to change notification settings - Fork 44
/
BucketSort_test.go
117 lines (106 loc) · 2.76 KB
/
BucketSort_test.go
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// BucketSort_test
/*
------------------------------------------------------
作者 : Black Ghost
日期 : 2019-03-06
版本 : 0.0.0
------------------------------------------------------
桶排序法
理论：
时间复杂度: O(n+k)
最好情况 : O(n)
最坏情况 : O(n^2)
空间复杂度: O(n+k)
稳定性 : 稳定
------------------------------------------------------
输入 :
in 输入矩阵, 1xn
bucketSize 桶中元素数
输出 :
sol 排序结果
err 解出标志：false-未解出或达到步数上限；
true-全部解出
------------------------------------------------------
注意：
仅对整数排序有效
------------------------------------------------------
*/
package goNum_test
import (
"math"
"testing"
"github.com/chfenger/goNum"
)
// IntMin 整数切片中最小数
func IntMin(in []int) int {
min := in[0]
for i := 1; i < len(in); i++ {
if min > in[i] {
min = in[i]
}
}
return min
}
// bucketSort_sort
func bucketSort_sort(temp0 []int, bucketSize int) []int {
if (temp0 == nil) || (len(temp0) < 2) {
return temp0
}
temp2 := make([]int, 0)
min := IntMin(temp0)
max := IntMax(temp0)
bucketCount := int(math.Floor(float64((max-min)/bucketSize))) + 1
bucket := make([][]int, bucketCount) //第一维为桶数量，第二维为桶容量|| (bucketSize == 0)
//排序开始
//利用映射函数将数据分配到各个桶中
for i := 0; i < len(temp0); i++ {
indi := int(math.Floor(float64((temp0[i] - min) / bucketSize)))
bucket[indi] = append(bucket[indi], temp0[i])
}
//桶中排序
for i := 0; i < bucketCount; i++ {
if bucketCount == 1 {
bucketSize--
}
temp1 := bucketSort_sort(bucket[i], bucketSize)
for j := 0; j < len(temp1); j++ {
temp2 = append(temp2, temp1[j])
}
}
return temp2
}
// BucketSort 桶排序法
func BucketSort(in []int, bucketSize int) ([]int, bool) {
/*
桶排序法
输入 :
in 输入矩阵, 1xn
bucketSize 桶中元素数
输出 :
sol 排序结果
err 解出标志：false-未解出或达到步数上限；
true-全部解出
*/
//判断初值维数
if len(in) < 1 {
panic("Error in goNum.BucketSort: Empty input Matrix")
} else if len(in) == 1 {
return in, true
}
n := len(in)
var err bool = false
soltemp := make([]int, n)
for i := 0; i < n; i++ {
soltemp[i] = in[i]
}
//排序开始
sol := bucketSort_sort(soltemp, bucketSize)
err = true
return sol, err
}
func BenchmarkBucketSort(b *testing.B) {
x66 := []int{20, 50, 12, 80, 5, 36}
for i := 0; i < b.N; i++ {
goNum.BucketSort(x66，2)
}
}