敞开生长之旅！这是我参与「日新方案 12 月更文应战」的第18天，点击检查活动详情

耐心和耐久胜过激烈和疯狂。

哈喽大家好，我是陈明勇，今天共享的内容是运用 Go 实现挑选排序算法。假如本文对你有帮助，无妨点个赞，假如你是 Go 言语初学者，无妨点个关注，一同生长一同前进，假如本文有错误的地方，欢迎指出！

挑选排序

挑选排序是一种简略的比较排序算法，它的算法思路是首先从数组中寻觅最小（大）的元素，然后放到数组中的第一位，接下来持续从未排序的元素中寻觅最小（大）元素，然后放到已排序元素的末尾，顺次类推，直到一切元素被排序。

图片演示

Go 实现选择排序算法及优化

普通算法

import "fmt"
func main() {
    nums := [8]int{8, 2, 3, 1, 6, 5, 7, 4}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    SelectionSort(nums)
}
func SelectionSort(nums [8]int) {
    for i := 0; i < len(nums)-1; i++ {
        minPos := i
        for j := i + 1; j < len(nums); j++ {
            if nums[minPos] > nums[j] {
                    minPos = j
            }
        }
        nums[i], nums[minPos] = nums[minPos], nums[i]
        fmt.Printf("第 %d 轮后：%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

履行成果：

原数组： [8 2 3 1 6 5 7 4]
--------------------------------
第 1 轮后：[1 2 3 8 6 5 7 4]
第 2 轮后：[1 2 3 8 6 5 7 4]
第 3 轮后：[1 2 3 8 6 5 7 4]
第 4 轮后：[1 2 3 4 6 5 7 8]
第 5 轮后：[1 2 3 4 5 6 7 8]
第 6 轮后：[1 2 3 4 5 6 7 8]
第 7 轮后：[1 2 3 4 5 6 7 8]
--------------------------------
排序后的数组： [1 2 3 4 5 6 7 8]
  • 升序排序。
  • 运用 i 变量表明最小元素的待放方位。
  • minPos 变量记载最小元素的的下标值，默认为 i。
  • 经过变量 j 去寻觅最小元素，j 从 i + 1 的方位开端寻觅。
  • 找到比 nums[minPos] 还小的元素，则将 j 的下标值赋给 minPos。
  • 一轮下来，将最小元素的方位 minPos 与 i 的方位互换，然后持续下一轮寻觅，直到一切元素都被排序。
  • 该算法的时刻复杂度为 O(N)。

优化算法

普通算法是寻觅最小值或最大值，然后放到指定方位。优化算法的改善点是同时寻觅最小值和最大值。

import (
    "fmt"
)
func main() {
    nums := [4]int{3, 1, 4, 2}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    SelectionSort(nums)
}
func SelectionSort(nums [4]int) {
    for left, right := 0, len(nums)-1; left <= right; {
        minPos := left
        maxPos := left
        for i := left + 1; i <= right; i++ {
            if nums[minPos] > nums[i] {
                minPos = i
            }
            if nums[maxPos] < nums[i] {
                maxPos = i
            }
        }
        nums[left], nums[minPos] = nums[minPos], nums[left]
        // 假如最大值刚好是在 left，待放最小值的方位，那么最大值就会被换走，所以需求判别一下
        if maxPos == left {
            maxPos = minPos
        }
        nums[right], nums[maxPos] = nums[maxPos], nums[right]
        fmt.Printf("第 %d 轮后：%v\n", left+1, nums)
        left++
        right--
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

履行成果：

原数组： [8 2 3 1 6 5 7 4]
--------------------------------
第 1 轮后：[1 2 3 4 6 5 7 8]
第 2 轮后：[1 2 3 4 6 5 7 8]
第 3 轮后：[1 2 3 4 5 6 7 8]
第 4 轮后：[1 2 3 4 5 6 7 8]
--------------------------------
排序后的数组： [1 2 3 4 5 6 7 8]
  • left 变量表明待放最小值的方位，right 变量表明待放最大值的方位。minPos 记载最小值的下标值，maxPos 记载最大值的下标值，经过变量 i 去寻觅最小值和最大值，寻觅完毕后将它们进行交流。
  • 有一个注意的地方是，假如最大值刚好是在 left ，待放最小值的方位，那么最大值就会被换到 minPos 的方位，所以需求判别一下，纠正下标值。
  • 从履行成果来看，优化后的算法功率快了一倍，可是时刻复杂度仍为 O(N)。

小结

本文简略介绍了什么是挑选排序，然后经过图片的方法演示挑选排序的过程，接下来是实现 O(N) 时刻复杂度的算法，最后优化算法，从成果来看，优化后的算法功率快了一倍，可是时刻复杂度仍为 O(N)。