排序算法
冒泡排序
func BubbleSort(data []int) {
n := len(data)
if data == nil || n < 2 {
return
}
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {
// 冒泡排序是一种交换排序，核心是冒泡，排序过程中两两比较相邻记录的元素，每轮确定一个元素的位置。
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
}
}
}
}
快速排序
package main
import "fmt"
func main() {
nums := []int{4, 7, 3, 1, 0, 9, 2, 8, 6, 5}
QuickSort(nums, 0, 9)
fmt.Println(nums)
}
func QuickSort(data []int, left, right int) {
val := data[(left+right)/2]
i, j := left, right
for data[j] > val {
j--
}
for data[i] < val {
i++
}
data[i], data[j] = data[j], data[i]
i++
j--
// 递归的方式
if i < right {
QuickSort(data, i, right)
}
if j > left {
QuickSort(data, left, j)
}
}
插入排序
func InsertSort(data []int) {
n := len(data)
for i := 0; i < n; i++ {
t := data[i]
// 类似于洗扑克牌，把每个元素插入到前面合适的位置上
for j := i - 1; j >= 0; j-- {
if t < data[j] {
// 比较并插入
data[j+1], data[j] = data[j], t
} else {
//前面已经是排好序的，如果比最后一个还大，则此元素无需继续比较
break
}
}
}
}
希尔排序
希尔排序的实质就是分组插入排序。
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
func ShellSort(data []int) {
n := len(data)
h := 1
for h < n/3 { //寻找合适的间隔h
h = 3*h + 1
}
for h >= 1 {
//将数组变为间隔h个元素有序
for i := h; i < n; i++ {
//间隔h插入排序
for j := i; j >= h && data[j] < data[j-h]; j -= h {
data[j], data[j-h] = data[j-h], data[j]
}
}
h /= 3
}
}
选择排序
func SelectionSort(data []int) {
n := len(data)
for i := 0; i < n; i++ {
// 循环找到最小元素的坐标，每轮交换一个
m := i
for j := i + 1; j < n; j++ {
if data[j] < data[m] {
m = j
}
}
data[i], data[m] = data[m], data[i]
}
}
