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
}
golang冒泡、插入、递归、快速排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
