golang排序算法

1.冒泡排序

rand.Seed(time.Now().UnixNano()) var a [10]int n := len(a) for i := 0; i < n; i++ { a[i] = rand.Intn(100) fmt.Println(a[i]) } for i := 0; i < n-1; i++ { for j := 0; j < n-1-i; j++ { if a[j] > a[j+1] { //从小到大。从大到小用< a[j], a[j+1] = a[j+1], a[j] } } } fmt.Println(a)

2. 选择排序

package main import "fmt" //找出最大值,再查找剩下的最大值 func Selectsort(arr *[6]int) { for j := 0; j < len(arr); j++ { max := arr[j] maxIndex := j for i := j + 1; i < len(arr); i++ { if max < arr[i] { //如果假设的最大值不是最大值 max = arr[i] maxIndex = i } } if maxIndex != j { arr[j], arr[maxIndex] = arr[maxIndex], arr[j] } fmt.Printf("第%d次 %v\n", j+1, *arr) } } func main() { arr := [6]int{10, 34, 89, 24, 65, 79} fmt.Println(arr) Selectsort(&arr) }

3.插入排序

package main import "fmt" func Insertsort(arr *[6]int) { //完成第一次,给第2个元素找到合适的位置并插入 for i := 1; i < len(arr); i++ { insertVal := arr[i] inserIndex := i - 1 //从大到小 for inserIndex >= 0 && arr[inserIndex] < insertVal { arr[inserIndex+1] = arr[inserIndex] //数据后移 inserIndex-- } //插入 if inserIndex+1 != i { arr[inserIndex+1] = insertVal } fmt.Printf("第%d次插入后%v\n", i, *arr) } } func main() { arr := [6]int{10, 34, 89, 24, 65, 79} fmt.Println(arr) Insertsort(&arr) }

4.快速排序

package main import "fmt" //left数组左边的下标,right右边的下标 func Quicksort(left int, right int, array *[7]int) { l := left r := right pivot := array[(left+right)/2] temp := 0 for l < r { //从pivot左边找到大于等于pivot的值 for array[l] < pivot { l++ } //从pivot右边找到小于等于pivot的值 for array[r] > pivot { r-- } if l >= r { break } //交换 temp = array[l] array[l] = array[r] array[r] = temp //优化 if array[l] == pivot { r-- } if array[r] == pivot { l++ } } if l == r { l++ r-- } if left < r { Quicksort(left, r, array) } if right > l { Quicksort(l, right, array) } } func findKthLargest(arr []int,k int) int { return findK(arr, k, 0, len(arr)-1) } func findK(array []int, k, start, end int) int { l := start r := end pivot := array[l] for l < r { for l < r && array[r] <= pivot { r-- } array[l] = array[r] for l < r && array[l] >= pivot { l++ } array[r] = array[l] } array[r] = pivot if r == k-1 { return pivot } else if r > k-1 { return findK(array, k, start, r-1) } else { return findK(array, k, r+1, end) } } func main() { arr := []int{10, 34, 89, 24, 65, -5, 79} k := findKthLargest(arr,1) fmt.Println(k) //fmt.Println(arr) //Quicksort(0, len(arr)-1, &arr) //fmt.Println(arr) }