基础算法之排序算法
程序员文章站
2024-02-05 18:53:40
排序算法的Golang实现 ~~~go package main import ( "fmt" ) //冒泡排序:升序 func BubbleSort(s []int) { for i:= 0;i s[j+1] { temp := s[j] s[j] = s[j+1] s[j+1] = temp } ......
排序算法的golang实现
package main import ( "fmt" ) //冒泡排序:升序 func bubblesort(s []int) { for i:= 0;i < len(s);i++{ for j := 0;j < len(s) - 1 - i;j++{ if s[j] > s[j+1] { temp := s[j] s[j] = s[j+1] s[j+1] = temp } } } } //选择排序:升序 func selectsort(nums []int) { for i := 0;i < len(nums);i++{ min := nums[i] minindex := i for j := i + 1;j < len(nums);j++{ if min > nums[j] { min = nums[j] minindex = j } } nums[minindex] = nums[i] nums[i] = min } } //快速排序 func quicksort(s []int,left,right int) { sort := func(s []int,low,high int)int { tmp := s[low] for low < high{ for low < high && s[high] >= tmp{ high-- } s[low],s[high] = s[high],s[low] for low < high && s[low] <= tmp{ low++ } s[low],s[high] = s[high],s[low] } return low } if left < right { index := sort(s,left,right) quicksort(s,left,index-1) quicksort(s,index+1,right) } } //堆排序 func heapsort(s []int) { heapadjust := func(s []int,parent,len int) { var i int for 2 * parent + 1 < len{ lchild := 2 * parent + 1 rchild := lchild + 1 i = lchild //取出两个子节点中最大的一个 if rchild < len && s[rchild] > s[lchild]{ i = rchild } //如果最大节点大于父节点则交换,否则退出循环 if s[i] > s[parent] { s[parent],s[i] = s[i],s[parent] parent = i }else { break } } } //从最后一个非叶子节点开始调整(len(s)/2 - 1) for i := len(s)/2 - 1;i >= 0;i--{ heapadjust(s,i,len(s)) } for i := len(s) - 1;i > 0;i--{ s[0],s[i] = s[i],s[0] heapadjust(s,0,i) } } //归并排序 func merge(left,right []int) []int { result := make([]int,0) m,n := 0,0 l,r := len(left),len(right) for m < l && n < r { if left[m] > right[n] { result = append(result,right[n]) n++ continue } result = append(result,left[m]) m++ } result = append(result,right[n:]...) result = append(result,left[m:]...) return result } func mergesort(arr []int) []int { if len(arr) < 2 { return arr } i := len(arr)/2 left := mergesort(arr[0:i]) right := mergesort(arr[i:]) result := merge(left,right) return result } func main() { //数组是属于值类型,方法传递的话应该是副本 array := []int{9,20,1,3,2,80,76} //bubblesort(array) //selectsort(array) //quicksort(array,0,len(array) - 1) //堆排序 //heapsort(array) //归并排序 array = mergesort(array) fmt.println(array) }