冒泡排序
func BubbleSort(vector []int) {
fmt.Println("BubbleSort")
fmt.Println(vector)
for i := 0; i < len(vector); i++ {
tag := true // 为了剪枝
// 每一趟将最大的数冒泡
for j := 0; j < len(vector)-i-1; j++ {
if vector[j] > vector[j+1] { /*vector[j] < vector[j+1]*/
temp := vector[j]
vector[j] = vector[j+1]
vector[j+1] = temp
tag = false
}
}
if tag {
break //0~len(vector)-i没有发生交换说明已经有序
}
fmt.Println(vector)
}
}
插入排序
func InsertSort(vector []int) {
fmt.Println("InsertSort")
fmt.Println(vector)
for i := 1; i < len(vector); i++ {
// 每一趟不满足条件就选择i为哨兵保存，将哨兵插入0~i-1有序序列（0~i-1始终是有序的）
if vector[i] < vector[i-1] { /*vector[i] > vector[i-1]*/
temp := vector[i]
//后移直到找到哨兵合适的位置
j := i - 1
for ; j >= 0 && vector[j] > temp; j-- { /*vector[j] < temp*/
vector[j+1] = vector[j]
}
//插入位置前后都是有序的，最后也是有序的
vector[j+1] = temp
}
fmt.Println(vector)
}
}
选择排序
func SelectSort(vector []int) {
fmt.Println("SelectSort")
fmt.Println(vector)
for i := 0; i < len(vector); i++ {
// 选择最小的元素
k := i
for j := i + 1; j < len(vector); j++ {
if vector[k] > vector[j] {
k = j
}
}
// 交换
if k != i {
temp := vector[i]
vector[i] = vector[k]
vector[k] = temp
}
fmt.Println(vector)
}
}
二元选择排序
func BinarySelectSort(vector []int) {
fmt.Println("SelectSort")
fmt.Println(vector)
n := len(vector)
for i := 0; i < n/2; i++ {
// 选择最小的元素和最大元素
k := i
t := n - i - 1
for j := i + 1; j <= n-i-1; j++ {
if vector[k] > vector[j] {
k = j
}
if vector[t] < vector[j] {
t = j
}
}
// 交换
if k != i {
temp := vector[i]
vector[i] = vector[k]
vector[k] = temp
}
if t != n-i-1 {
temp := vector[n-i-1]
vector[n-i-1] = vector[t]
vector[t] = temp
}
fmt.Println(vector)
}
}
有疑问加站长微信联系（非本文作者）
