算法快学笔记(三):选择排序的原理与实现

栏目: 编程工具 · 发布时间: 6年前

内容简介:选择排序是个简单的排序,思路主要通过多次遍历待排序的集合,每次弹出最大/小值并放入新的集合,直到原始集合为空。举个例子:假设要对A=[1,2,5,9,3]按照升序的方式进行排序,步骤与结果如下从上面的过程可以看出,要对A进行排序,必须要执行N轮操作,每一轮操作必须检查列表中的每个元素。随着排序的进行,每次需要检查的元素数在逐渐减少,最后一次需要检查的元素都只有一个。平均每次检查的元素数为1/2 × n, 因此运行时间为O(n × 1/2 × n),但大O表示法省略诸如1/2这样的常数,因此简单地写作O(n

1. 原理介绍

选择 排序 是个简单的排序,思路主要通过多次遍历待排序的集合,每次弹出最大/小值并放入新的集合,直到原始集合为空。举个例子:

假设要对A=[1,2,5,9,3]按照升序的方式进行排序,步骤与结果如下

  1. 从A中找出最大值,将其pop,并放入B中,执行后的结果如下:
A=[2,5,9,3]
B=[1]
  1. 重复执行第一部
A=[5,9,3]
B=[1,2]
  1. 重复执行第一部
A=[5,9]
B=[1,2,3]
  1. 重复执行第一部
A=[9]
B=[1,2,3,5]
  1. 重复执行第一部
A=[]
B=[1,2,3,5,9]
  1. 此时A为空,返回B

2. 运行时间分析

从上面的过程可以看出,要对A进行排序,必须要执行N轮操作,每一轮操作必须检查列表中的每个元素。随着排序的进行,每次需要检查的元素数在逐渐减少,最后一次需要检查的元素都只有一个。平均每次检查的元素数为1/2 × n, 因此运行时间为O(n × 1/2 × n),但大O表示法省略诸如1/2这样的常数,因此简单地写作O(n × n)或O(n^2)。

3. 代码实现

Go语言实现的过程如下:

// 对int数组的选择排序
func SelectSort(items []int) []int {
	result := make([]int,len(items))
	for i:=0;i< len(result);i++{
		tmpIndex := getMinItemIndex(&items)
		result[i]=items[tmpIndex]
		//从原始数组中删除掉被选择的元素
		items = append(items[:tmpIndex], items[tmpIndex+1:]...)
	}
	return result
}

//获取一个数组中,最小元素的位置
func getMinItemIndex(ints *[]int) int {
	//默认假设第一个元素作为临时最小值
	min := (*ints)[0]
	smallestIndex :=0
	for index,item := range *ints {
		if item < min {
			min = item
			smallestIndex =index
		}
	}
	return smallestIndex
}

4. 总结

  • 选择排序的时间复杂度为:O(n^2)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

重新定义公司

重新定义公司

[美]埃里克·施密特 / 靳婷婷、陈序、何晔 / 中信出版社 / 2015-8 / 49.00

谷歌高管手绘风漫画视频: http://v.youku.com/v_show/id_XMTMxMzQ3NjMyMA==.html?from=y1.7-1.2 Google掌门人第一本国内引进作品 首次公开谷歌内部的管理与运营方法 全面解密执掌谷歌10余年的内幕故事 谷歌 创始人拉里•佩奇作序推荐 今日的谷歌是全球最具标志性的企业,在各个领域都有创新突破,并向技术......一起来看看 《重新定义公司》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试