golang 实现二分查找、插入排序、冒泡排序、选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 二分
func binarySearch(list []int, key int) int {<!-- -->
    low, high := 0, len(list)-1
    for low <= high {<!-- -->
        mid := (low + high) / 2
        if key < list[mid] {<!-- -->
            high = mid - 1
            continue
        }
        if key > list[mid] {<!-- -->
            low = mid + 1
            continue
        }
        return mid
    }
    return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 插入排序
func InsertionSort(a []int) {<!-- -->
    n := len(a)
    if n <= 1 {<!-- -->
        return
    }
    for i := 1; i < n; i++ {<!-- -->
        value := a[i]
        j := i - 1
        //查找要插入的位置并移动数据
        for ; j >= 0; j-- {<!-- -->
            if a[j] < value {<!-- -->
                a[j+1] = a[j]
            } else {<!-- -->
                break
            }
        }
        a[j+1] = value
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 冒泡排序
func BubbleSort(a []int) {<!-- -->
    length := len(a)
    if length < 1 {<!-- -->
        return
    }
    for i := 0; i < length; i++ {<!-- -->
        // 提前退出标志
        flag := false
        for j := 0; j < length-i-1; j++ {<!-- -->
            if a[j] > a[j+1] {<!-- -->
                a[j], a[j+1] = a[j+1], a[j]
                //此次冒泡有数据交换
                flag = true
            }
        }
        // 如果没有交换数据，提前退出
        if !flag {<!-- -->
            break
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 选择排序
func SelectionSort(a []int) {<!-- -->
    n := len(a)
    if n <= 1 {<!-- -->
        return
    }
    for i := 0; i < n; i++ {<!-- -->
        // 查找最小值
        minIndex := i
        for j := i + 1; j < n; j++ {<!-- -->
            if a[j] < a[minIndex] {<!-- -->
                minIndex = j
            }
        }
        // 交换
        a[i], a[minIndex] = a[minIndex], a[i]

    }
}