选择排序,如冒泡排序一样,从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大(小)的元素,将其放置至数组的首(尾)部,重复此过程直至没有未排序的子数组。
当然,在分析该排序算法前还是先将golang实现版本放置出来献下丑:
// Sort方法从数组头开始,将未排序的元素做为子数组,并在子数组中选择中最小的元素,将其放置子数组的最首位置做为已排序元素,重复此过程,直到所有数组元素排序完成为止
// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
func (this *SelectSort) Sort(a []Comparable, compare Compare) {
for i := 0; i < len(a); i++ {
min := i
for j := i + 1; j < len(a); j++ {
if this.less(a[j], a[min], compare) == true {
min = j
}
}
this.exch(a, i, min)
}
}
同样,我们用与冒泡排序相同的方法分析其效率。观察选择排序的代码实现,明显她也是时间复杂度为O(N^2)的排序算法。同样以元素比较作为单元操作,完成一个长度为N的数组的排序工作需要N-1 + N-2 + ... + 2 + 1次比较操作,简化后为(N-1)/2*N = (N^2-N)/2 ~ N^2。
与冒泡排序不同的是,虽然两种排序算法的比较次数是相同的,但是其元素交换操作数目并不是相同的。选择排序的交换操作最多为N次,而冒泡排序的交换操作却与数组中不满足顺序的元素对数量相同,即与被排序数组相关,在最差情况下,其次数与比较次数相同,即N^2。
虽然选择排序在元素交换方面比冒泡排序具有一定的优势,但是其时间复杂度依然是万恶的平方级别的,即O(N^2),所以其依然只适用于小型数组的排序,不能满足大量数据的排序。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有