经典算法巡礼(二) -- 排序之选择排序
原创经典算法巡礼(二) -- 排序之选择排序
原创
jiezhu
修改于 2018-09-17 11:54:53
修改于 2018-09-17 11:54:53
选择排序，如冒泡排序一样，从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大（小）的元素，将其放置至数组的首（尾）部，重复此过程直至没有未排序的子数组。
当然，在分析该排序算法前还是先将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 删除。
评论
登录后参与评论
推荐阅读