Go实战--golang中各种排序算法实现以及生成随机数
生命不止,继续 go go go !!! 排序,对于每种编程语言都是要面对的。这里跟大家一起分享golang实现一些排序算法,并且说明如何生成随机数。 还要说明一下,这里不会详细介绍各种排序算法的原理,如需探索自行Google。 sort packagePackage sort provides primitives for sorting slices and user-defined collections. type Interface type Interface interface {
Len() int // Len 为集合内元素的总数
Less(i,j int) bool //如果index为i的元素小于index为j的元素,则返回true,否则返回false
Swap(i,j int) // Swap 交换索引为 i 和 j 的元素
}
sort相关的一些方法: func Float64sAreSorted(a []float64) bool func Ints(a []int) func IntsAreSorted(a []int) bool func IsSorted(data Interface) bool func Strings(a []string) func StringsAreSorted(a []string) bool func Sort(data Interface) func Stable(data Interface) func Reverse(data Interface) Interface 应用: package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
func (p Person) String() string {
return fmt.Sprintf("%s: %d",p.Name,p.Age)
}
// ByAge implements sort.Interface for []Person based on
// the Age field.
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Swap(i,j int) { a[i],a[j] = a[j],a[i] }
func (a ByAge) Less(i,j int) bool { return a[i].Age < a[j].Age }
func main() {
people := []Person{
{"Bob", 31},{"John", 42},{"Michael", 17},{"Jenny", 26},}
fmt.Println(people)
sort.Sort(ByAge(people))
fmt.Println(people)
}
search相关的方法 func Search(n int,f func(int) bool) int
search使用二分法进行查找 Search 常用于在一个已排序的,可索引的数据结构中寻找索引为 i 的值 x,例如数组或切片。这种情况下,实参 f,一般是一个闭包,会捕获所要搜索的值,以及索引并排序该数据结构的方式。 func SearchFloat64s(a []float64,x float64) int
SearchFloat64s 在float64s切片中搜索x并返回索引如Search函数所述. 返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列 func SearchInts(a []int,x int) int
SearchInts 在ints切片中搜索x并返回索引如Search函数所述. 返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列 func SearchStrings(a []string,x string) int
SearchFloat64s 在strings切片中搜索x并返回索引如Search函数所述. 返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列 应用: func main() {
a := sort.StringSlice{"hello","world","golang","sort","nice"}
a.Sort() // 二分法必须先排序
// 获取首字母大于 n 的元素中最小的
i := sort.Search(len(a),func(i int) bool {
return len(a[i]) > 0 && a[i][0] > 'n'
})
// 显示找到的元素
fmt.Println(a[i]) // sort
}
math/rand packagePackage rand implements pseudo-random number generators. 下面介绍一下应用: func generateRandomNumber(start int,end int,count int) []int {
if end < start || (end-start) < count {
return nil
}
nums := make([]int, 0)
r := rand.New(rand.NewSource(time.Now().UnixNano()))
for len(nums) < count {
num := r.Intn((end - start)) + start
exist := false
for _,v := range nums {
if v == num {
exist = true
break
}
}
if !exist {
nums = append(nums,num)
}
}
return nums
}
各种排序算法时间及比较冒泡排序 func bubbleSort(items []int) {
var (
n = len(items)
swapped = true
)
for swapped {
swapped = false
for i := 0; i < n-1; i++ {
if items[i] > items[i+1] {
items[i+1],items[i] = items[i],items[i+1]
swapped = true
}
}
n = n - 1
}
}
使用sort包: func bubbleSortUsingSortPackage(data sort.Interface) {
r := data.Len() - 1
for i := 0; i < r; i++ {
for j := r; j > i; j-- {
if data.Less(j,j-1) {
data.Swap(j,j-1)
}
}
}
}
插入排序 func insertionSort(items []int) {
var n = len(items)
for i := 1; i < n; i++ {
j := i
for j > 0 {
if items[j-1] > items[j] {
items[j-1],items[j] = items[j],items[j-1]
}
j = j - 1
}
}
}
使用sort包: func insertionSortUsingSortPackage(data sort.Interface) {
r := data.Len() - 1
for i := 1; i <= r; i++ {
for j := i; j > 0 && data.Less(j,j-1); j-- {
data.Swap(j,j-1)
}
}
}
选择排序 func selectionSort(items []int) {
var n = len(items)
for i := 0; i < n; i++ {
var minIdx = i
for j := i; j < n; j++ {
if items[j] < items[minIdx] {
minIdx = j
}
}
items[i],items[minIdx] = items[minIdx],items[i]
}
}
使用sort包: func selectionSortUsingSortPackage(data sort.Interface) {
r := data.Len() - 1
for i := 0; i < r; i++ {
min := i
for j := i + 1; j <= r; j++ {
if data.Less(j,min) {
min = j
}
}
data.Swap(i,min)
}
}
快速排序 func QuickSort(src []int,first,last int) {
flag := first
left := first
right := last
if first >= last {
return
}
for first < last {
for first < last {
if src[last] >= src[flag] {
last -= 1
continue
} else {
tmp := src[last]
src[last] = src[flag]
src[flag] = tmp
flag = last
break
}
}
for first < last {
if src[first] <= src[flag] {
first += 1
continue
} else {
tmp := src[first]
src[first] = src[flag]
src[flag] = tmp
flag = first
break
}
}
}
QuickSort(src,left,flag-1)
QuickSort(src,flag+1,right)
}
希尔排序 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 1、插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 2、但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位> func shellshort(items []int) {
var (
n = len(items)
gaps = []int{1}
k = 1
)
for {
gap := pow(2,k) + 1
if gap > n-1 {
break
}
gaps = append([]int{gap},gaps...)
k++
}
for _,gap := range gaps {
for i := gap; i < n; i += gap {
j := i
for j > 0 {
if items[j-gap] > items[j] {
items[j-gap],items[j-gap]
}
j = j - gap
}
}
}
}
func pow(a,b int) int {
p := 1
for b > 0 {
if b&1 != 0 {
p *= a
}
b >>= 1
a *= a
}
return p
}
梳排序 func combsort(items []int) {
var (
n = len(items)
gap = len(items)
shrink = 1.3
swapped = true
)
for swapped {
swapped = false
gap = int(float64(gap) / shrink)
if gap < 1 {
gap = 1
}
for i := 0; i+gap < n; i++ {
if items[i] > items[i+gap] {
items[i+gap],items[i+gap]
swapped = true
}
}
}
}
归并排序 func mergeSort(items []int) []int {
var n = len(items)
if n == 1 {
return items
}
middle := int(n / 2)
var (
left = make([]int,middle)
right = make([]int,n-middle)
)
for i := 0; i < n; i++ {
if i < middle {
left[i] = items[i]
} else {
right[i-middle] = items[i]
}
}
return merge(mergeSort(left),mergeSort(right))
}
func merge(left,right []int) (result []int) {
result = make([]int,len(left)+len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
完整代码 package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func main() {
rand_numbs := generateRandomNumber(0, 30000, 10000)
items_bubble := rand_numbs
items_bubble2 := rand_numbs
items_selection := rand_numbs
items_selection2 := rand_numbs
items_insertion := rand_numbs
items_insertion2 := rand_numbs
items_quick := rand_numbs
items_quick2 := rand_numbs
items_shell := rand_numbs
items_comb := rand_numbs
items_merge := rand_numbs
start := time.Now()
bubbleSort(items_bubble)
elapsed := time.Since(start)
fmt.Printf("Cost time bubbleSort %vn",elapsed)
start = time.Now()
bubbleSortUsingSortPackage(sort.IntSlice(items_bubble2))
end := time.Now()
fmt.Printf("Cost time bubbleSortUsingSortPackage %vn",end.Sub(start))
start = time.Now()
selectionSort(items_selection)
end = time.Now()
fmt.Printf("Cost time selectionSort %vn",end.Sub(start))
start = time.Now()
selectionSortUsingSortPackage(sort.IntSlice(items_selection2))
end = time.Now()
fmt.Printf("Cost time selectionSortUsingSortPackage %vn",end.Sub(start))
start = time.Now()
insertionSort(items_insertion)
end = time.Now()
fmt.Printf("Cost time insertionSort %vn",end.Sub(start))
start = time.Now()
insertionSortUsingSortPackage(sort.IntSlice(items_insertion2))
end = time.Now()
fmt.Printf("Cost time insertionSortUsingSortPackage %vn",end.Sub(start))
start = time.Now()
QuickSort(items_quick, 0,len(items_quick)-1)
end = time.Now()
fmt.Printf("Cost time QuickSort %vn",end.Sub(start))
start = time.Now()
sort.Ints(items_quick2)
end = time.Now()
fmt.Printf("Cost time sort.Ints %vn",end.Sub(start))
start = time.Now()
shellshort(sort.IntSlice(items_shell))
end = time.Now()
fmt.Printf("Cost time shellshort %vn",end.Sub(start))
start = time.Now()
combsort(sort.IntSlice(items_comb))
end = time.Now()
fmt.Printf("Cost time combsort %vn",end.Sub(start))
start = time.Now()
mergeSort(sort.IntSlice(items_merge))
end = time.Now()
fmt.Printf("Cost time mergeSort %vn",end.Sub(start))
}
func bubbleSort(items []int) {
var (
n = len(items)
swapped = true
)
for swapped {
swapped = false
for i := 0; i < n-1; i++ {
if items[i] > items[i+1] {
items[i+1],items[i+1]
swapped = true
}
}
n = n - 1
}
}
func bubbleSortUsingSortPackage(data sort.Interface) {
r := data.Len() - 1
for i := 0; i < r; i++ {
for j := r; j > i; j-- {
if data.Less(j,j-1)
}
}
}
}
func selectionSort(items []int) {
var n = len(items)
for i := 0; i < n; i++ {
var minIdx = i
for j := i; j < n; j++ {
if items[j] < items[minIdx] {
minIdx = j
}
}
items[i],items[i]
}
}
func selectionSortUsingSortPackage(data sort.Interface) {
r := data.Len() - 1
for i := 0; i < r; i++ {
min := i
for j := i + 1; j <= r; j++ {
if data.Less(j,min)
}
}
func insertionSort(items []int) {
var n = len(items)
for i := 1; i < n; i++ {
j := i
for j > 0 {
if items[j-1] > items[j] {
items[j-1],items[j-1]
}
j = j - 1
}
}
}
func insertionSortUsingSortPackage(data sort.Interface) {
r := data.Len() - 1
for i := 1; i <= r; i++ {
for j := i; j > 0 && data.Less(j,j-1)
}
}
}
func QuickSort(src []int,right)
}
func shellshort(items []int) {
var (
n = len(items)
gaps = []int{1}
k = 1
)
for {
gap := pow(2,b int) int {
p := 1
for b > 0 {
if b&1 != 0 {
p *= a
}
b >>= 1
a *= a
}
return p
}
func combsort(items []int) {
var (
n = len(items)
gap = len(items)
shrink = 1.3
swapped = true
)
for swapped {
swapped = false
gap = int(float64(gap) / shrink)
if gap < 1 {
gap = 1
}
for i := 0; i+gap < n; i++ {
if items[i] > items[i+gap] {
items[i+gap],items[i+gap]
swapped = true
}
}
}
}
func mergeSort(items []int) []int {
var n = len(items)
if n == 1 {
return items
}
middle := int(n / 2)
var (
left = make([]int,len(left)+len(right))
i := 0
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
i++
}
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
for j := 0; j < len(left); j++ {
result[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
result[i] = right[j]
i++
}
return
}
func generateRandomNumber(start int, 0)
r := rand.New(rand.NewSource(time.Now().UnixNano()))
for len(nums) < count {
num := r.Intn((end - start)) + start
exist := false
for _,num)
}
}
return nums
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |