package main
import (
"fmt"
"math"
"math/rand"
"unsafe"
)
const (
size = 100
)
func main() {
test_sort()
}
func test_sort() {
arr := make([]int, size) // int占4字节,100个就占用占用400字节,3200位
for i := 0; i < len(arr); i++ {
arr[i] = rand.Intn(size)
}
print_array(arr)
newarr := bitmap_sort(arr)
print_result(newarr)
}
func print_array(arr []int) {
fmt.Printf("array:")
for i := 0; i < len(arr); i++ {
fmt.Printf(" %d", arr[i])
}
fmt.Printf("\n")
}
//内存少数据最大值小可以采用方式,位排序
func bitmap_sort(arr []int) (newarr []int) {
var left uint32
size := int(unsafe.Sizeof(arr[0]) * 4)
newarr = make([]int, len(arr))
for i := 0; i < len(arr); i++ {
index := arr[i] / size
left = uint32(arr[i] % size)
leftvalue := newarr[index] & (int(math.Pow(2.0, float64(left))) - 1)
newarr[index] = (newarr[index] >> left)
if (newarr[index] & 1) == 0 {
newarr[index] += 1
}
newarr[index] = (newarr[index] << left) + leftvalue
}
return newarr
}
func print_result(arr []int) {
index := 0
size := int(unsafe.Sizeof(arr[0]) * 4)
fmt.Printf("new array:")
for i := 0; i < len(arr); i++ {
for j := 0; j < size; j++ {
bit := arr[i] & 1
if bit != 0 {
fmt.Printf(" %d", index)
}
arr[i] = arr[i] >> 1
index++
}
}
}