package main import ( "fmt" ) func main() { arr := []int{11, 8, 3, 9, 7, 1, 2, 5} n := len(arr) // newArr := insertionSort(arr, n) // newArr := bubbleSort(arr, n) // newArr := mergeSort(arr, n) newArr := quickSort(arr, n) fmt.Println(newArr) } // 冒泡 func bubbleSort(arr []int, n int) []int { if n <= 1 { return arr } for i := 0; i < n; i++ { flag := false for j := 0; j < n-1-i; j++ { if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] flag = true } } if !flag { break } fmt.Print(flag) fmt.Println(arr) } return arr } //插入排序 func insertionSort(arr []int, n int) []int { if n <= 1 { return arr } for i := 1; i < n; i++ { //外层循环控制每次需要插入的数 j := i val := arr[i] //这次循环需要加入的数 for ; j > 0; j-- { //内层循环遍历排好序的一侧 // //类似冒泡排序,交换位置 // if val < arr[j-1] {//小于则交换位置 // arr[j], arr[j-1] = arr[j-1], arr[j] // } //整体位移,找到位置后赋值 if val < arr[j-1] { arr[j] = arr[j-1] } else { break } } arr[j] = val } return arr } //选择 //归并排序 func mergeSort(arr []int, n int) []int { mergeSortC(arr, 0, n-1) return arr } //归并函数 func mergeSortC(a []int, p, r int) { //终止条件 if p >= r { return } //取pr中间值q q := 0 if (r-p+1)%2 == 0 { q = (p + r - 1) / 2 } else { q = (p + r) / 2 } //分治递归 mergeSortC(a, p, q) mergeSortC(a, q+1, r) //合并 merge(a, p, r, q) } func merge(a []int, p, r, q int) { i := p j := q + 1 k := 0 tem := make([]int, len(a)) for i <= q && j <= r { if a[i] <= a[j] { //稳定排序 tem[k] = a[i] k++ i++ } else { tem[k] = a[j] k++ j++ } } //判断子数组中是否有剩余 if i-1 == q { //j中存在剩余 for j <= r { tem[k] = a[j] k++ j++ } } else if j-1 == r { //i中存在剩余 for i <= q { tem[k] = a[i] k++ i++ } } //将tem拷贝回a for i := 0; p+i <= r; i++ { a[p+i] = tem[i] } } //快速排序 func quickSort(a []int, n int) []int { quickSortC(a, 0, n-1) return a } func quickSortC(a []int, p, r int) { if p >= r { return } q := partition(a, p, r) quickSortC(a, p, q) quickSortC(a, q+1, r) } func partition(a []int, p, r int) int { povit := a[r] //取最后一位作为povit,后期优化的点 i := p for j := p; j <= r-1; j++ { if a[j] < povit { a[j], a[i] = a[i], a[j]//涉及位置交换,不稳定 i++ } } if i == r { return i - 1 } a[r], a[i] = a[i], a[r] return i }