经典算法巡礼(二) -- 排序之选择排序

选择排序,如冒泡排序一样,从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大(小)的元素,将其放置至数组的首(尾)部,重复此过程直至没有未排序的子数组。

当然,在分析该排序算法前还是先将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),所以其依然只适用于小型数组的排序,不能满足大量数据的排序

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

Java每日一练(2017/7/5)

1 (单选题)1、下面这三条语句 System.out.println(“is ”+ 100 + 5); System.out.println(100 + 5 ...

3509
来自专栏北京马哥教育

python模块之re正则表达式详解

正则表达式是一种小型的、高度专业化的编程语言,并不是python中特有的,是许多编程语言中基础而又重要的一部分。在python中,主要通过re模块来实现。这篇文...

4019
来自专栏Android机器圈

静态变量和实例变量的区别(配图解释专业术语,通俗易懂)

1:首先在语法定义上区别:静态变量前面要加static,实例变量不用 2:在程序运行时:实例变量输入对象的属性,必须创建了实例对象(如 new)才会被分配空间...

34613
来自专栏进击的君君的前端之路

面向对象、this

1203
来自专栏Python数据科学

Python 内建函数大全

Python 解释器内置了许多函数和类型,列表如下(按字母排序)(省略了几个我没用过或者不常用的)。

2373
来自专栏王磊的博客

JS性能优化

下面是一些关于客户端JS性能的一些优化的小技巧: 1.关于JS的循环,循环是一种常用的流程控制。JS提供了三种循环:for(;;)、while()、for(in...

5768
来自专栏黑泽君的专栏

c语言基础学习07_指针

=============================================================================

1840
来自专栏琯琯博客

PHP 操作 Redis

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。

2031
来自专栏null的专栏

挑战数据结构与算法面试题——统计上排数在下排出现的次数

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 本题应该是一个确定的问题,即上排的是个数是题目中给定的...

3206
来自专栏西安-晁州

js数组去重

对于如下对象数组 [{id: 0, name: "name1"}, {id: 1, name: "name2"},{id: 1, name: "name2"},...

2400

扫码关注云+社区

领取腾讯云代金券