Go 数据结构和算法篇(六):选择排序
今天继续介绍排序算法 —— 选择排序。
实现原理
选择排序算法的实现思路有点类似,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。这样一来,当遍历完未排序区间,就意味着已经完成整个序列的排序了。图示如下:
同样,可以在 VisuAlgo 上看动态图:https://visualgo.net/zh/sorting。
示例代码
选择排序的实现逻辑非常简单,对应的 Go 实现代码如下:
package main
import "fmt"
func selectionSort(nums []int) {
if len(nums) <= 1 {
return
}
// 已排序区间初始化为空,未排序区间初始化待排序切片
for i := 0; i < len(nums); i++ {
// 未排序区间最小值初始化为第一个元素
min := i
// 从未排序区间第二个元素开始遍历,直到找到最小值
for j := i + 1; j < len(nums); j++ {
if nums[j] < nums[min] {
min = j
}
}
// 将最小值与未排序区间第一个元素互换位置(等价于放到已排序区间最后一个位置)
if min != i {
nums[i],nums[min] = nums[min], nums[i]
}
}
}
func main() {
nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
selectionSort(nums)
fmt.Println(nums)
}
由于传递到 selectionSort
函数的参数是 []int
类型的切片,而切片是,所以其实不必定义返回值,运行上述代码,打印结果如下:
表明排序算法可以正常工作。
性能分析
接下来,我们来看看选择排序的性能和稳定性:
很显然,选择排序的时间复杂度也是 O(n2)
由于不涉及额外的存储空间,所以是原地排序;
由于涉及非相邻元素的位置交换,所以是不稳定的排序算法。
综合比较前面介绍的三种排序算法,时间复杂度都是一样的,也都是原地排序,但是选择排序是不稳定的排序算法,此外,插入排序和冒泡排序相比较的话,插入排序只需要执行一条语句,而冒泡排序需要三条,因此在同等条件下,或者数据量很大的情况下,插入排序性能是要略优于冒泡排序的,所以综合比较下来,三者的优先级是插入排序 > 冒泡排序 >> 选择排序。
不过三者的时间复杂度都是 O(n2),在数据量很大的情况下性能表现其实都不理想,还可以进一步进行优化,这就是我们接下来要介绍的归并排序和快速排序算法。
(本文完)
学习过程中有任何问题,可以通过下面的评论功能或加入「Go 语言研习社」与学院君讨论:
本系列教程首发在 geekr.dev,你可以点击页面左下角阅读原文链接查看最新更新的教程。